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

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

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

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

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

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

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

image

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

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

image

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

image

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

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

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

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

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

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

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

WITH COMMENT_CTE(CommentId,ParentId,CommentBody,tLevel) AS
(
    --基本語句
    SELECT CommentId,ParentId,CommentBody,0 AS tLevel FROM Comment
    WHERE ParentId = 4
    UNION ALL  --遞歸語句
    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é)點樹又如何查呢？例如查節(jié)點6的所有祖先節(jié)點:

WITH COMMENT_CTE(CommentId,ParentId,CommentBody,tLevel) AS
(
    --基本語句
    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é)果如下：

image

再者，由于公用表表達式能夠控制遞歸的深度，因此，你可以簡單獲得任意層級的子樹。

OPTION(MAXRECURSION 2)

看來哥是為鄰接表平反來的。

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

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

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

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

分析4：刪除子樹

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

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

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

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

SELECT ParentId FROM Comments WHERE CommentId = 6;　　  --搜索要刪除節(jié)點的父節(jié)點，假設(shè)返回4

UPDATE Comments SET ParentId = 4 WHERE ParentId = 6;　　--修改該中間節(jié)點的子節(jié)點的ParentId為要刪除中間節(jié)點的ParentId

DELETE FROM Comments WHERE CommentId = 6;　　　　　　    --終于可以刪除該中間節(jié)點了

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

二、路徑枚舉

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

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

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

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

簡略說明問題的數(shù)據(jù)表如下：

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

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

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

結(jié)果如下：

image

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

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

結(jié)果如下：

image

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

image

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

路徑枚舉的缺點:

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

2、要依賴高級程序來維護路徑中的字符串，并且驗證字符串的正確性的開銷很大。

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

路徑枚舉的設(shè)計方式能夠很方便地根據(jù)節(jié)點的層級排序，因為路徑中分隔兩邊的節(jié)點間的距離永遠是1，因此通過比較字符串長度就能知道層級的深淺。

三、嵌套集

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

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

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

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

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

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

采用書中的圖來說明一下情況：

image

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

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

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

例如，通過搜索那些節(jié)點的ConmentId在評論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é)果如下：

image

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

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

image

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

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

嵌套集缺點：

1、查詢直接父親。

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

比如，要找到評論6的直接父節(jié)點：老實說，SQL語句又長又臭，行肯定是行，但我真的寫不動了。

2、對樹進行操作，比如插入和移動節(jié)點。

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

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

四、閉包表

閉包表是解決分層存儲一個簡單而又優(yōu)雅的解決方案，它記錄了表中所有的節(jié)點關(guān)系，并不僅僅是直接的父子關(guān)系。

在閉包表的設(shè)計中，額外創(chuàng)建了一張TreePaths的表(空間換取時間)，它包含兩列，每一列都是一個指向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è)計中，Comments表將不再存儲樹結(jié)構(gòu)，而是將書中的祖先-后代關(guān)系存儲為TreePaths的一行，即使這兩個節(jié)點之間不是直接的父子關(guān)系；同時還增加一行指向節(jié)點自己，理解不了？就是TreePaths表存儲了所有祖先-后代的關(guān)系的記錄。如下圖:

image

Comment表：

image

TreePaths表：

image

優(yōu)點：

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

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

結(jié)果如下：

image

2、查詢評論6的所有祖先(查祖先樹)：

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

顯示結(jié)果如下：

image

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

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

比如下面為插入評論5的一個子節(jié)點的TreePaths表語句：

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

執(zhí)行以后：

image

至于Comment表那就簡單得不說了。

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

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

DELETE FROM TreePaths WHERE descendant = 7

5、刪除子樹：

要刪除一顆完整的子樹，比如評論4和它的所有后代，可刪除所有在TreePaths表中的后代為4的行，以及那些以評論4的后代為后代的行：

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

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

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

總結(jié)

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

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

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

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

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

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

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

轉(zhuǎn)載自https://www.cnblogs.com/yinggu/p/11498981.html