相信有過開發(fā)經(jīng)驗(yàn)的朋友都曾碰到過這樣一個(gè)需求。假設(shè)你正在為一個(gè)新聞網(wǎng)站開發(fā)一個(gè)評(píng)論功能，讀者可以評(píng)論原文甚至相互回復(fù)。

這個(gè)需求并不簡(jiǎn)單，相互回復(fù)會(huì)導(dǎo)致無(wú)限多的分支，無(wú)限多的祖先-后代關(guān)系。這是一種典型的遞歸關(guān)系數(shù)據(jù)。

對(duì)于這個(gè)問題，以下給出幾個(gè)解決方案，各位客觀可斟酌后選擇。

一、鄰接表:依賴父節(jié)點(diǎn)

鄰接表的方案如下(僅僅說(shuō)明問題)：

CREATE TABLE Comments(
　　　　CommentId　　int　　PK,
　　　　ParentId　　 int,　　　　--記錄父節(jié)點(diǎn)
        ArticleId　　int,
　　　　CommentBody nvarchar(500),
　　　　FOREIGN KEY (ParentId)  REFERENCES Comments(CommentId) 　　--自連接，主鍵外鍵都在自己表內(nèi)　
  　　　FOREIGN KEY (ArticleId) REFERENCES Articles(ArticleId)
　　)

由于偷懶，所以采用了書本中的圖了，Bugs就是Articles：

這種設(shè)計(jì)方式就叫做鄰接表。這可能是存儲(chǔ)分層結(jié)構(gòu)數(shù)據(jù)中最普通的方案了。

下面給出一些數(shù)據(jù)來(lái)顯示一下評(píng)論表中的分層結(jié)構(gòu)數(shù)據(jù)。示例表：

image

圖片說(shuō)明存儲(chǔ)結(jié)構(gòu)：

image

****鄰接表的優(yōu)缺分析****

對(duì)于以上鄰接表，很多程序員已經(jīng)將其當(dāng)成默認(rèn)的解決方案了，但即便是這樣，但它在從前還是有存在的問題的。

　　分析1：查詢一個(gè)節(jié)點(diǎn)的所有后代(求子樹)怎么查呢？

我們先看看以前查詢兩層的數(shù)據(jù)的SQL語(yǔ)句：

SELECT c1.*,c2.*　　FROM Comments c1 LEFT OUTER JOIN Comments2 c2
　　ON c2.ParentId = c1.CommentId

顯然，每需要查多一層，就需要聯(lián)結(jié)多一次表。SQL查詢的聯(lián)結(jié)次數(shù)是有限的，因此不能無(wú)限深的獲取所有的后代。而且，這種這樣聯(lián)結(jié)，執(zhí)行Count()這樣的聚合函數(shù)也相當(dāng)困難。

說(shuō)了是以前了，現(xiàn)在什么時(shí)代了，在SQLServer 2005之后，一個(gè)公用表表達(dá)式就搞定了,順帶解決的還有聚合函數(shù)的問題(聚合函數(shù)如Count()也能夠簡(jiǎn)單實(shí)用)，例如查詢?cè)u(píng)論4的所有子節(jié)點(diǎn)：

WITH COMMENT_CTE(CommentId,ParentId,CommentBody,tLevel)AS(    --基本語(yǔ)句
    SELECT CommentId,ParentId,CommentBody,0 AS tLevel FROM Comment    WHERE ParentId = 4
    UNION ALL  --遞歸語(yǔ)句
    SELECT c.CommentId,c.ParentId,c.CommentBody,ce.tLevel + 1 FROM Comment AS c 
    INNER JOIN COMMENT_CTE AS ce    --遞歸查詢
    ON c.ParentId = ce.CommentId
)SELECT * FROM COMMENT_CTE

顯示結(jié)果如下：

image

那么查詢祖先節(jié)點(diǎn)樹又如何查呢？例如查節(jié)點(diǎn)6的所有祖先節(jié)點(diǎn):

WITH COMMENT_CTE(CommentId,ParentId,CommentBody,tLevel)AS(    --基本語(yǔ)句
    SELECT CommentId,ParentId,CommentBody,0 AS tLevel FROM Comment    WHERE CommentId = 6
    UNION ALL
    SELECT c.CommentId,c.ParentId,c.CommentBody,ce.tLevel - 1  FROM Comment AS c 
    INNER JOIN COMMENT_CTE AS ce　　--遞歸查詢    ON ce.ParentId = c.CommentId    where ce.CommentId <> ce.ParentId
)SELECT * FROM COMMENT_CTE ORDER BY CommentId ASC

結(jié)果如下：

再者，由于公用表表達(dá)式能夠控制遞歸的深度，因此，你可以簡(jiǎn)單獲得任意層級(jí)的子樹。

OPTION(MAXRECURSION 2)

看來(lái)哥是為鄰接表平反來(lái)的。

分析2：****當(dāng)然，鄰接表也有其優(yōu)點(diǎn)的，例如要添加一條記錄是非常方便的。

INSERT INTO Comment(ArticleId,ParentId)...    --僅僅需要提供父節(jié)點(diǎn)Id就能夠添加了。

分析3：修改一個(gè)節(jié)點(diǎn)位置或一個(gè)子樹的位置也是很簡(jiǎn)單.

UPDATE Comment SET ParentId = 10 WHERE CommentId = 6　　--僅僅修改一個(gè)節(jié)點(diǎn)的ParentId，其后面的子代節(jié)點(diǎn)自動(dòng)合理。

分析4：刪除子樹

想象一下，如果你刪除了一個(gè)中間節(jié)點(diǎn)，那么該節(jié)點(diǎn)的子節(jié)點(diǎn)怎么辦(它們的父節(jié)點(diǎn)是誰(shuí))，因此如果你要?jiǎng)h除一個(gè)中間節(jié)點(diǎn)，那么不得不查找到所有的后代，先將其刪除，然后才能刪除該中間節(jié)點(diǎn)。

當(dāng)然這也能通過一個(gè)ON DELETE CASCADE級(jí)聯(lián)刪除的外鍵約束來(lái)自動(dòng)完成這個(gè)過程。

分析5：刪除中間節(jié)點(diǎn)，并提升子節(jié)點(diǎn)

面對(duì)提升子節(jié)點(diǎn)，我們要先修改該中間節(jié)點(diǎn)的直接子節(jié)點(diǎn)的ParentId，然后才能刪除該節(jié)點(diǎn)：

SELECT ParentId FROM Comments WHERE CommentId = 6;　　  --搜索要?jiǎng)h除節(jié)點(diǎn)的父節(jié)點(diǎn)，假設(shè)返回4　　
UPDATE Comments SET ParentId = 4 WHERE ParentId = 6;　　--修改該中間節(jié)點(diǎn)的子節(jié)點(diǎn)的ParentId為要?jiǎng)h除中間節(jié)點(diǎn)的ParentId　　
DELETE FROM Comments WHERE CommentId = 6;　　　　　　    --終于可以刪除該中間節(jié)點(diǎn)了

由上面的分析可以看到，鄰接表基本上已經(jīng)是很強(qiáng)大的了。

二、路徑枚舉

路徑枚舉的設(shè)計(jì)是指通過將所有祖先的信息聯(lián)合成一個(gè)字符串，并保存為每個(gè)節(jié)點(diǎn)的一個(gè)屬性。

路徑枚舉是一個(gè)由連續(xù)的直接層級(jí)關(guān)系組成的完整路徑。如"/home/account/login",其中home是account的直接父親，這也就意味著home是login的祖先。

還是有剛才新聞評(píng)論的例子，我們用路徑枚舉的方式來(lái)代替鄰接表的設(shè)計(jì)：

CREATE TABLE Comments(
　　　　CommentId　　int　　PK,
　　　　Path　　 　　 varchar(100),　　　　--僅僅改變了該字段和刪除了外鍵　　　　ArticleId　　int,
　　　　CommentBody nvarchar(500),
　　　　FOREIGN KEY (ArticleId) REFERENCES Articles(ArticleId)
　　)

簡(jiǎn)略說(shuō)明問題的數(shù)據(jù)表如下：

CommentId　　Path　　　　CommentBody

1　　　　　　　1/ 　　　　這個(gè)Bug的成因是什么

2　　　　　　　1/2/　　　　 我覺得是一個(gè)空指針

3　　　　　　　1/2/3　　　 不是，我查過了

4　　　　　　　1/4/　　　　 我們需要查無(wú)效的輸入

5　　　　　　　1/4/5/　　　 是的，那是個(gè)問題

6　　　　　　　1/4/6/　　　 好，查一下吧。

7　　　　　　　1/4/6/7/　　 解決了

路徑枚舉的優(yōu)點(diǎn)：

對(duì)于以上表，假設(shè)我們需要查詢某個(gè)節(jié)點(diǎn)的全部祖先，SQL語(yǔ)句可以這樣寫(假設(shè)查詢7的所有祖先節(jié)點(diǎn)):

SELECT * FROM Comment AS cWHERE '1/4/6/7/' LIKE c.path + '%'

結(jié)果如下：

假設(shè)我們要查詢某個(gè)節(jié)點(diǎn)的全部后代，假設(shè)為4的后代：

SELECT * FROM Comment AS cWHERE c.Path LIKE '1/4/%'

結(jié)果如下：

一旦我們可以很簡(jiǎn)單地獲取一個(gè)子樹或者從子孫節(jié)點(diǎn)到祖先節(jié)點(diǎn)的路徑，就可以很簡(jiǎn)單地實(shí)現(xiàn)更多查詢，比如計(jì)算一個(gè)字?jǐn)?shù)所有節(jié)點(diǎn)的數(shù)量(COUNT聚合函數(shù))

插入一個(gè)節(jié)點(diǎn)也可以像和使用鄰接表一樣地簡(jiǎn)單?？梢圆迦胍粋€(gè)葉子節(jié)點(diǎn)而不用修改任何其他的行。你所需要做的只是復(fù)制一份要插入節(jié)點(diǎn)的邏輯上的父親節(jié)點(diǎn)路徑，并將這個(gè)新節(jié)點(diǎn)的Id追加到路徑末尾就可以了。如果這個(gè)Id是插入時(shí)由數(shù)據(jù)庫(kù)生成的，你可能需要先插入這條記錄，然后獲取這條記錄的Id，并更新它的路徑。

路徑枚舉的缺點(diǎn):

1、數(shù)據(jù)庫(kù)不能確保路徑的格式總是正確或者路徑中的節(jié)點(diǎn)確實(shí)存在(中間節(jié)點(diǎn)被刪除的情況，沒外鍵約束)。

2、要依賴高級(jí)程序來(lái)維護(hù)路徑中的字符串，并且驗(yàn)證字符串的正確性的開銷很大。

3、VARCHAR的長(zhǎng)度很難確定。無(wú)論VARCHAR的長(zhǎng)度設(shè)為多大，都存在不能夠無(wú)限擴(kuò)展的情況。

路徑枚舉的設(shè)計(jì)方式能夠很方便地根據(jù)節(jié)點(diǎn)的層級(jí)排序，因?yàn)槁窂街蟹指魞蛇叺墓?jié)點(diǎn)間的距離永遠(yuǎn)是1，因此通過比較字符串長(zhǎng)度就能知道層級(jí)的深淺。

三、嵌套集

嵌套集解決方案是存儲(chǔ)子孫節(jié)點(diǎn)的信息，而不是節(jié)點(diǎn)的直接祖先。我們使用兩個(gè)數(shù)字來(lái)編碼每個(gè)節(jié)點(diǎn)，表示這個(gè)信息?？梢詫⑦@兩個(gè)數(shù)字稱為nsleft和nsright。

還是以上面的新聞-評(píng)論作為例子，對(duì)于嵌套集的方式表可以設(shè)計(jì)為：

CREATE TABLE Comments(
　　　　CommentId　　int　　PK,
　　　　nsleft　　　 int,　　--之前的一個(gè)父節(jié)點(diǎn)
       nsright　　　int,　　--變成了兩個(gè)　　
   　　ArticleId　　int,
　　　　CommentBody nvarchar(500),
　　　　FOREIGN KEY (ArticleId) REFERENCES Articles(ArticleId)
　　)

nsleft值的確定：nsleft的數(shù)值小于該節(jié)點(diǎn)所有后代的Id。

nsright值的確定：nsright的值大于該節(jié)點(diǎn)所有后代的Id。

當(dāng)然，以上兩個(gè)數(shù)字和CommentId的值并沒有任何關(guān)聯(lián)，確定值的方式是對(duì)樹進(jìn)行一次深度優(yōu)先遍歷，在逐層入神的過程中依次遞增地分配nsleft的值，并在返回時(shí)依次遞增地分配nsright的值。

采用書中的圖來(lái)說(shuō)明一下情況：

image

一旦你為每個(gè)節(jié)點(diǎn)分配了這些數(shù)字，就可以使用它們來(lái)找到給定節(jié)點(diǎn)的祖先和后代。

嵌套集的優(yōu)點(diǎn)：

我覺得是唯一的優(yōu)點(diǎn)了，查詢祖先樹和子樹方便。

例如，通過搜索那些節(jié)點(diǎn)的ConmentId在評(píng)論4的nsleft與nsright之間就可以獲得其及其所有后代：

SELECT c2.* FROM Comments AS c1   JOIN Comments AS c2　　ON cs.neleft BETWEEN c1.nsleft AND c1.nsright
　　WHERE c1.CommentId = 1;

結(jié)果如下：

通過搜索評(píng)論6的Id在哪些節(jié)點(diǎn)的nsleft和nsright范圍之間，就可以獲取評(píng)論6及其所有祖先：

SELECT c2.* FROM Comment AS c1
　　JOIN Comment AS c2 ON c1.nsleft BETWEEN c2.nsleft AND c2.nsright
　　WHERE c1.CommentId = 6;

這種嵌套集的設(shè)計(jì)還有一個(gè)優(yōu)點(diǎn)，就是當(dāng)你想要?jiǎng)h除一個(gè)非葉子節(jié)點(diǎn)時(shí)，它的后代會(huì)自動(dòng)地代替被刪除的節(jié)點(diǎn)，稱為其直接祖先節(jié)點(diǎn)的直接后代。

嵌套集設(shè)計(jì)并不必須保存分層關(guān)系。因此當(dāng)刪除一個(gè)節(jié)點(diǎn)造成數(shù)值不連續(xù)時(shí)，并不會(huì)對(duì)樹的結(jié)構(gòu)產(chǎn)生任何影響。

嵌套集缺點(diǎn)：

1、查詢直接父親。

在嵌套集的設(shè)計(jì)中，這個(gè)需求的實(shí)現(xiàn)的思路是，給定節(jié)點(diǎn)c1的直接父親是這個(gè)節(jié)點(diǎn)的一個(gè)祖先，且這兩個(gè)節(jié)點(diǎn)之間不應(yīng)該有任何其他的節(jié)點(diǎn)，因此，你可以用一個(gè)遞歸的外聯(lián)結(jié)來(lái)查詢一個(gè)節(jié)點(diǎn)，它就是c1的祖先，也同時(shí)是另一個(gè)節(jié)點(diǎn)Y的后代，隨后我們使y=x就查詢，直到查詢返回空，即不存在這樣的節(jié)點(diǎn)，此時(shí)y便是c1的直接父親節(jié)點(diǎn)。

比如，要找到評(píng)論6的直接父節(jié)點(diǎn)：老實(shí)說(shuō)，SQL語(yǔ)句又長(zhǎng)又臭，行肯定是行，但我真的寫不動(dòng)了。

2、對(duì)樹進(jìn)行操作，比如插入和移動(dòng)節(jié)點(diǎn)。

當(dāng)插入一個(gè)節(jié)點(diǎn)時(shí)，你需要重新計(jì)算新插入節(jié)點(diǎn)的相鄰兄弟節(jié)點(diǎn)、祖先節(jié)點(diǎn)和它祖先節(jié)點(diǎn)的兄弟，來(lái)確保它們的左右值都比這個(gè)新節(jié)點(diǎn)的左值大。同時(shí)，如果這個(gè)新節(jié)點(diǎn)是一個(gè)非葉子節(jié)點(diǎn)，你還要檢查它的子孫節(jié)點(diǎn)。

夠了，夠了。就憑查直接父節(jié)點(diǎn)都困難，這個(gè)東西就很冷門了。我確定我不會(huì)使用這種設(shè)計(jì)了。

四、閉包表

閉包表是解決分層存儲(chǔ)一個(gè)簡(jiǎn)單而又優(yōu)雅的解決方案，它記錄了表中所有的節(jié)點(diǎn)關(guān)系，并不僅僅是直接的父子關(guān)系。
　　在閉包表的設(shè)計(jì)中，額外創(chuàng)建了一張TreePaths的表(空間換取時(shí)間)，它包含兩列，每一列都是一個(gè)指向Comments中的CommentId的外鍵。

CREATE TABLE Comments(
　　CommentId int PK,
　　ArticleId int,
　　CommentBody int,
　　FOREIGN KEY(ArticleId) REFERENCES Articles(Id)
)

父子關(guān)系表：

CREATE TABLE TreePaths(
　　ancestor    int,
　　descendant int,
　　PRIMARY KEY(ancestor,descendant),    --復(fù)合主鍵　
  　FOREIGN KEY (ancestor) REFERENCES Comments(CommentId),
　　FOREIGN KEY (descendant) REFERENCES Comments(CommentId)
)

在這種設(shè)計(jì)中，Comments表將不再存儲(chǔ)樹結(jié)構(gòu)，而是將書中的祖先-后代關(guān)系存儲(chǔ)為TreePaths的一行，即使這兩個(gè)節(jié)點(diǎn)之間不是直接的父子關(guān)系；同時(shí)還增加一行指向節(jié)點(diǎn)自己，理解不了？就是TreePaths表存儲(chǔ)了所有祖先-后代的關(guān)系的記錄。如下圖:

Comment表：

TreePaths表：

優(yōu)點(diǎn)：

1、查詢所有后代節(jié)點(diǎn)(查子樹)：

SELECT c.* FROM Comment AS c    
INNER JOIN TreePaths t on c.CommentId = t.descendant    WHERE t.ancestor = 4

結(jié)果如下：

2、查詢?cè)u(píng)論6的所有祖先(查祖先樹)：

SELECT c.* FROM Comment AS c    
INNER JOIN TreePaths t on c.CommentId = t.ancestor    WHERE t.descendant = 6

顯示結(jié)果如下：

3、插入新節(jié)點(diǎn)：

要插入一個(gè)新的葉子節(jié)點(diǎn)，應(yīng)首先插入一條自己到自己的關(guān)系，然后搜索TreePaths表中后代是評(píng)論5的節(jié)點(diǎn)，增加該節(jié)點(diǎn)與要插入的新節(jié)點(diǎn)的"祖先-后代"關(guān)系。

比如下面為插入評(píng)論5的一個(gè)子節(jié)點(diǎn)的TreePaths表語(yǔ)句：

INSERT INTO TreePaths(ancestor,descendant)    SELECT t.ancestor,8
    FROM TreePaths AS t    WHERE t.descendant = 5
    UNION ALL
    SELECT 8,8

執(zhí)行以后：

至于Comment表那就簡(jiǎn)單得不說(shuō)了。

4、刪除葉子節(jié)點(diǎn)：

比如刪除葉子節(jié)點(diǎn)7,應(yīng)刪除所有TreePaths表中后代為7的行：

DELETE FROM TreePaths WHERE descendant = 7

5、刪除子樹：

要?jiǎng)h除一顆完整的子樹，比如評(píng)論4和它的所有后代，可刪除所有在TreePaths表中的后代為4的行，以及那些以評(píng)論4的后代為后代的行：

DELETE FROM TreePaths
　　WHERE descendant 
　　IN(SELECT descendant FROM TreePaths WHERE ancestor = 4)

另外，移動(dòng)節(jié)點(diǎn)，先斷開與原祖先的關(guān)系，然后與新節(jié)點(diǎn)建立關(guān)系的SQL語(yǔ)句都不難寫。

另外，閉包表還可以優(yōu)化，如增加一個(gè)path_length字段，自我引用為0，直接子節(jié)點(diǎn)為1，再一下層為2，一次類推，查詢直接自子節(jié)點(diǎn)就變得很簡(jiǎn)單。

總結(jié)

其實(shí)，在以往的工作中，曾見過不同類型的設(shè)計(jì)，鄰接表，路徑枚舉，鄰接表路徑枚舉一起來(lái)的都見過。

每種設(shè)計(jì)都各有優(yōu)劣，如果選擇設(shè)計(jì)依賴于應(yīng)用程序中哪種操作最需要性能上的優(yōu)化。

下面給出一個(gè)表格，來(lái)展示各種設(shè)計(jì)的難易程度：

1、鄰接表是最方便的設(shè)計(jì)，并且很多軟件開發(fā)者都了解它。并且在遞歸查詢的幫助下，使得鄰接表的查詢更加高效。

2、枚舉路徑能夠很直觀地展示出祖先到后代之間的路徑，但由于不能確保引用完整性，使得這個(gè)設(shè)計(jì)比較脆弱。枚舉路徑也使得數(shù)據(jù)的存儲(chǔ)變得冗余。

3、嵌套集是一個(gè)聰明的解決方案，但不能確保引用完整性，并且只能使用于查詢性能要求較高，而其他要求一般的場(chǎng)合使用它。

4、閉包表是最通用的設(shè)計(jì)，并且最靈活，易擴(kuò)展，并且一個(gè)節(jié)點(diǎn)能屬于多棵樹，能減少冗余的計(jì)算時(shí)間。但它要求一張額外的表來(lái)存儲(chǔ)關(guān)系，是一個(gè)空間換取時(shí)間的方案。

轉(zhuǎn)自：https://www.phpbloger.com/article/50.html