樹形結(jié)構(gòu)的數(shù)據(jù)庫(kù)表Schema設(shè)計(jì)

那么某個(gè)節(jié)點(diǎn)到底有多少的子孫節(jié)點(diǎn)呢？通過該節(jié)點(diǎn)的左、右我們可以將其子孫節(jié)點(diǎn)圈進(jìn)來(lái)，則子孫總數(shù) = (右 – 左– 1) / 2，以Fruit為例，其子孫總數(shù)為：(11 –2 – 1) / 2 = 4。同時(shí)，為了更為直觀地展現(xiàn)樹形結(jié)構(gòu)，我們需要知道節(jié)點(diǎn)在樹中所處的層次，通過左

那么某個(gè)節(jié)點(diǎn)到底有多少的子孫節(jié)點(diǎn)呢？通過該節(jié)點(diǎn)的左、右值我們可以將其子孫節(jié)點(diǎn)圈進(jìn)來(lái)，則子孫總數(shù) = (右值 – 左值– 1) / 2，以Fruit為例，其子孫總數(shù)為：(11 –2 – 1) / 2 = 4。同時(shí)，為了更為直觀地展現(xiàn)樹形結(jié)構(gòu)，我們需要知道節(jié)點(diǎn)在樹中所處的層次，通過左、右值的SQL查詢即可實(shí)現(xiàn)，以Fruit為例：SELECTCOUNT(*) FROM Tree WHERE Lft <= 2 AND Rgt >=11。為了方便描述，我們可以為Tree建立一個(gè)視圖，添加一個(gè)層次數(shù)列，該列數(shù)值可以寫一個(gè)自定義函數(shù)來(lái)計(jì)算，函數(shù)定義如下：

CREATE FUNCTION dbo.CountLayer
(
 @node_id int
)
RETURNS int
AS
begin
	declare @result int
	set @result = 0
	declare @lft int
	declare @rgt int
	if exists(select Node_id from Tree where Node_id = @node_id)
	begin
	select @lft = Lft, @rgt = Rgt from Tree where node_id = @node_id
	select @result = count(*) from Tree where Lft <= @lft and Rgt >= @rgt
	end
	return @result
end
GO

基于層次計(jì)算函數(shù)，我們創(chuàng)建一個(gè)視圖，添加了新的記錄節(jié)點(diǎn)層次的數(shù)列：

CREATE VIEW dbo.TreeView
AS
SELECT Node_id, Name, Lft, Rgt, dbo.CountLayer(Node_id) AS Layer FROM dbo.Tree ORDER BY Lft
GO

創(chuàng)建存儲(chǔ)過程，用于計(jì)算給定節(jié)點(diǎn)的所有子孫節(jié)點(diǎn)及相應(yīng)的層次：

CREATE PROCEDURE [dbo].[GetChildrenNodeList]
(
	@node_id int
)
AS
declare @lft int
declare @rgt int
if exists(select Node_id from Tree where node_id = @node_id)
	begin
	select @lft = Lft, @rgt = Rgt from Tree where Node_id = @node_id
	select * from TreeView where Lft between @lft and @rgt order by Lft ASC
	end
GO

現(xiàn)在，我們使用上面的存儲(chǔ)過程來(lái)計(jì)算節(jié)點(diǎn)Fruit所有子孫節(jié)點(diǎn)及對(duì)應(yīng)層次，查詢結(jié)果如下：

從上面的實(shí)現(xiàn)中，我們可以看出采用左右值編碼的設(shè)計(jì)方案，在進(jìn)行樹的查詢遍歷時(shí)，只需要進(jìn)行2次數(shù)據(jù)庫(kù)查詢，消除了遞歸，再加上查詢條件都是數(shù)字的比較，查詢的效率是極高的，隨著樹規(guī)模的不斷擴(kuò)大，基于左右值編碼的設(shè)計(jì)方案將比傳統(tǒng)的遞歸方案查詢效率提高更多。當(dāng)然，前面我們只給出了一個(gè)簡(jiǎn)單的獲取節(jié)點(diǎn)子孫的算法，真正地使用這棵樹我們需要實(shí)現(xiàn)插入、刪除同層平移節(jié)點(diǎn)等功能。

（2）獲取某節(jié)點(diǎn)的族譜路徑

假定我們要獲得某節(jié)點(diǎn)的族譜路徑，則根據(jù)左、右值分析只需要一條SQL語(yǔ)句即可完成，以Fruit為例：SELECT* FROM Tree WHERE Lft < 2 AND Rgt > 11 ORDER BY Lft ASC ，相對(duì)完整的存儲(chǔ)過程：

CREATE PROCEDURE [dbo].[GetParentNodePath]
(
	@node_id int
)
AS
declare @lft int
declare @rgt int
if exists(select Node_id from Tree where Node_id = @node_id)
	begin
	select @lft = Lft, @rgt = Rgt from Tree where Node_id = @node_id
	select * from TreeView where Lft < @lft and Rgt > @rgt order by Lft ASC
	end
GO

（3）為某節(jié)點(diǎn)添加子孫節(jié)點(diǎn)

假定我們要在節(jié)點(diǎn)“Red”下添加一個(gè)新的子節(jié)點(diǎn)“Apple”，該樹將變成如下圖所示，其中紅色節(jié)點(diǎn)為新增節(jié)點(diǎn)。

仔細(xì)觀察圖中節(jié)點(diǎn)左右值變化，相信大家都應(yīng)該能夠推斷出如何寫SQL腳本了吧。我們可以給出相對(duì)完整的插入子節(jié)點(diǎn)的存儲(chǔ)過程：

CREATE PROCEDURE [dbo].[AddSubNode]
(
	@node_id int,
	@node_name varchar(50)
)
AS
declare @rgt int
if exists(select Node_id from Tree where Node_id = @node_id)
	begin
	SET XACT_ABORT ON
	BEGIN TRANSCTION
	select @rgt = Rgt from Tree where Node_id = @node_id
	update Tree set Rgt = Rgt + 2 where Rgt >= @rgt
	update Tree set Lft = Lft + 2 where Lft >= @rgt
	insert into Tree(Name, Lft, Rgt) values(@node_name, @rgt, @rgt + 1)
	COMMIT TRANSACTION
	SET XACT_ABORT OFF
	end
GO

（4）刪除某節(jié)點(diǎn)

如果我們想要?jiǎng)h除某個(gè)節(jié)點(diǎn)，會(huì)同時(shí)刪除該節(jié)點(diǎn)的所有子孫節(jié)點(diǎn)，而這些被刪除的節(jié)點(diǎn)的個(gè)數(shù)為：(被刪除節(jié)點(diǎn)的右值 – 被刪除節(jié)點(diǎn)的左值+ 1) / 2，而剩下的節(jié)點(diǎn)左、右值在大于被刪除節(jié)點(diǎn)左、右值的情況下會(huì)進(jìn)行調(diào)整。來(lái)看看樹會(huì)發(fā)生什么變化，以Beef為例，刪除效果如下圖所示。

則我們可以構(gòu)造出相應(yīng)的存儲(chǔ)過程：

CREATE PROCEDURE [dbo].[DelNode]
(
	@node_id int
)
AS
declare @lft int
declare @rgt int
if exists(select Node_id from Tree where Node_id = @node_id)
	begin
	SET XACT_ABORT ON
	BEGIN TRANSCTION
	select @lft = Lft, @rgt = Rgt from Tree where Node_id = @node_id
	delete from Tree where Lft >= @lft and Rgt <= @rgt
	update Tree set Lft = Lft – (@rgt - @lft + 1) where Lft > @lft
	update Tree set Rgt = Rgt – (@rgt - @lft + 1) where Rgt > @rgt
	COMMIT TRANSACTION
	SET XACT_ABORT OFF
	end
GO

五、總結(jié)

我們可以對(duì)這種通過左右值編碼實(shí)現(xiàn)無(wú)限分組的樹形結(jié)構(gòu)Schema設(shè)計(jì)方案做一個(gè)總結(jié)：

（1）優(yōu)點(diǎn)：在消除了遞歸操作的前提下實(shí)現(xiàn)了無(wú)限分組，而且查詢條件是基于整形數(shù)字的比較，效率很高。

（2）缺點(diǎn)：節(jié)點(diǎn)的添加、刪除及修改代價(jià)較大，將會(huì)涉及到表中多方面數(shù)據(jù)的改動(dòng)。

當(dāng)然，本文只給出了幾種比較常見的CRUD算法的實(shí)現(xiàn)，我們同樣可以自己添加諸如同層節(jié)點(diǎn)平移、節(jié)點(diǎn)下移、節(jié)點(diǎn)上移等操作。有興趣的朋友可以自己動(dòng)手編碼實(shí)現(xiàn)一下，這里不在列舉了。值得注意的是，實(shí)現(xiàn)這些算法可能會(huì)比較麻煩，會(huì)涉及到很多條update語(yǔ)句的順序執(zhí)行，如果順序調(diào)度考慮不周詳，出現(xiàn)Bug的話將會(huì)對(duì)整個(gè)樹形結(jié)構(gòu)表產(chǎn)生驚人的破壞。因此，在對(duì)樹形結(jié)構(gòu)進(jìn)行大規(guī)模修改的時(shí)候，可以采用臨時(shí)表做中介，以降低代碼的復(fù)雜度，同時(shí)，強(qiáng)烈推薦在做修改之前對(duì)表進(jìn)行完整備份，以備不時(shí)之需。在以查詢?yōu)橹鞯慕^大多數(shù)基于數(shù)據(jù)庫(kù)的應(yīng)用系統(tǒng)中，該方案相比傳統(tǒng)的由父子繼承關(guān)系構(gòu)建的數(shù)據(jù)庫(kù)Schema更為適用。

參考文獻(xiàn)：《Storing Hierarchical Data in a Database Article》

聲明：本網(wǎng)頁(yè)內(nèi)容旨在傳播知識(shí)，若有侵權(quán)等問題請(qǐng)及時(shí)與本網(wǎng)聯(lián)系，我們將在第一時(shí)間刪除處理。TEL:177 7030 7066 E-MAIL:11247931@qq.com