轉載：
邏輯數(shù)據(jù)庫設計 - 單純的樹(遞歸關系數(shù)據(jù))相信有過開發(fā)經驗的朋友都曾碰到過這樣一個需求。假設你正在為一個新聞網站開發(fā)一個評論功能，讀者可以評論原文甚至相互回復。
這個需求并不簡單，相互回復會導致無限多的分支，無限多的祖先-后代關系。這是一種典型的遞歸關系數(shù)據(jù)。
對于這個問題，以下給出幾個解決方案，各位客觀可斟酌后選擇。
一、鄰接表:依賴父節(jié)點
鄰接表的方案如下(僅僅說明問題)：
CREATE TABLE Comments( CommentId int PK, ParentId int, --記錄父節(jié)點 ArticleId int, CommentBody nvarchar(500), FOREIGN KEY (ParentId) REFERENCES Comments(CommentId) --自連接，主鍵外鍵都在自己表內 FOREIGN KEY (ArticleId) REFERENCES Articles(ArticleId) )
由于偷懶，所以采用了書本中的圖了，Bugs就是Articles：
這種設計方式就叫做鄰接表。這可能是存儲分層結構數(shù)據(jù)中最普通的方案了。
下面給出一些數(shù)據(jù)來顯示一下評論表中的分層結構數(shù)據(jù)。示例表：
圖片說明存儲結構：
鄰接表的優(yōu)缺分析
對于以上鄰接表，很多程序員已經將其當成默認的解決方案了，但即便是這樣，但它在從前還是有存在的問題的。
分析1：查詢一個節(jié)點的所有后代(求子樹)怎么查呢？
我們先看看以前查詢兩層的數(shù)據(jù)的SQL語句：
SELECT c1.*,c2.* FROM Comments c1 LEFT OUTER JOIN Comments2 c2 ON c2.ParentId = c1.CommentId
顯然，每需要查多一層，就需要聯(lián)結多一次表。SQL查詢的聯(lián)結次數(shù)是有限的，因此不能無限深的獲取所有的后代。而且，這種這樣聯(lián)結，執(zhí)行Count()這樣的聚合函數(shù)也相當困難。
說了是以前了，現(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é)點樹又如何查呢？例如查節(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
結果如下：
再者，由于公用表表達式能夠控制遞歸的深度，因此，你可以簡單獲得任意層級的子樹。
OPTION(MAXRECURSION 2)
看來哥是為鄰接表平反來的。
分析2：當然，鄰接表也有其優(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é)點。
當然這也能通過一個ON DELETE CASCADE級聯(lián)刪除的外鍵約束來自動完成這個過程。
分析5：刪除中間節(jié)點，并提升子節(jié)點
面對提升子節(jié)點，我們要先修改該中間節(jié)點的直接子節(jié)點的ParentId，然后才能刪除該節(jié)點：
SELECT ParentId FROM Comments WHERE CommentId = 6; --搜索要刪除節(jié)點的父節(jié)點，假設返回4 UPDATE Comments SET ParentId = 4 WHERE ParentId = 6; --修改該中間節(jié)點的子節(jié)點的ParentId為要刪除中間節(jié)點的ParentId DELETE FROM Comments WHERE CommentId = 6; --終于可以刪除該中間節(jié)點了
由上面的分析可以看到，鄰接表基本上已經是很強大的了。
二、路徑枚舉
路徑枚舉的設計是指通過將所有祖先的信息聯(lián)合成一個字符串，并保存為每個節(jié)點的一個屬性。
路徑枚舉是一個由連續(xù)的直接層級關系組成的完整路徑。如"/home/account/login",其中home是account的直接父親，這也就意味著home是login的祖先。
還是有剛才新聞評論的例子，我們用路徑枚舉的方式來代替鄰接表的設計：
CREATE TABLE Comments( CommentId int PK, Path varchar(100), --僅僅改變了該字段和刪除了外鍵 ArticleId int, CommentBody nvarchar(500), FOREIGN KEY (ArticleId) REFERENCES Articles(ArticleId) )
簡略說明問題的數(shù)據(jù)表如下：
CommentId Path CommentBody
1 1/ 這個Bug的成因是什么
2 1/2/ 我覺得是一個空指針
3 1/2/3 不是，我查過了
4 1/4/ 我們需要查無效的輸入
5 1/4/5/ 是的，那是個問題
6 1/4/6/ 好，查一下吧。
7 1/4/6/7/ 解決了
路徑枚舉的優(yōu)點：
對于以上表，假設我們需要查詢某個節(jié)點的全部祖先，SQL語句可以這樣寫(假設查詢7的所有祖先節(jié)點):
SELECT * FROM Comment AS cWHERE '1/4/6/7/' LIKE c.path + '%'
結果如下：
假設我們要查詢某個節(jié)點的全部后代，假設為4的后代：
SELECT * FROM Comment AS cWHERE c.Path LIKE '1/4/%'
結果如下：
一旦我們可以很簡單地獲取一個子樹或者從子孫節(jié)點到祖先節(jié)點的路徑，就可以很簡單地實現(xiàn)更多查詢，比如計算一個字數(shù)所有節(jié)點的數(shù)量(COUNT聚合函數(shù))
插入一個節(jié)點也可以像和使用鄰接表一樣地簡單。可以插入一個葉子節(jié)點而不用修改任何其他的行。你所需要做的只是復制一份要插入節(jié)點的邏輯上的父親節(jié)點路徑，并將這個新節(jié)點的Id追加到路徑末尾就可以了。如果這個Id是插入時由數(shù)據(jù)庫生成的，你可能需要先插入這條記錄，然后獲取這條記錄的Id，并更新它的路徑。
路徑枚舉的缺點:
1、數(shù)據(jù)庫不能確保路徑的格式總是正確或者路徑中的節(jié)點確實存在(中間節(jié)點被刪除的情況，沒外鍵約束)。
2、要依賴高級程序來維護路徑中的字符串，并且驗證字符串的正確性的開銷很大。
3、VARCHAR的長度很難確定。無論VARCHAR的長度設為多大，都存在不能夠無限擴展的情況。
路徑枚舉的設計方式能夠很方便地根據(jù)節(jié)點的層級排序，因為路徑中分隔兩邊的節(jié)點間的距離永遠是1，因此通過比較字符串長度就能知道層級的深淺。
三、嵌套集
嵌套集解決方案是存儲子孫節(jié)點的信息，而不是節(jié)點的直接祖先。我們使用兩個數(shù)字來編碼每個節(jié)點，表示這個信息。可以將這兩個數(shù)字稱為nsleft和nsright。
還是以上面的新聞-評論作為例子，對于嵌套集的方式表可以設計為：
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。
當然，以上兩個數(shù)字和CommentId的值并沒有任何關聯(lián)，確定值的方式是對樹進行一次深度優(yōu)先遍歷，在逐層入神的過程中依次遞增地分配nsleft的值，并在返回時依次遞增地分配nsright的值。
采用書中的圖來說明一下情況：
一旦你為每個節(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;
結果如下：
通過搜索評論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;
這種嵌套集的設計還有一個優(yōu)點，就是當你想要刪除一個非葉子節(jié)點時，它的后代會自動地代替被刪除的節(jié)點，稱為其直接祖先節(jié)點的直接后代。
嵌套集設計并不必須保存分層關系。因此當刪除一個節(jié)點造成數(shù)值不連續(xù)時，并不會對樹的結構產生任何影響。
嵌套集缺點：
1、查詢直接父親。
在嵌套集的設計中，這個需求的實現(xiàn)的思路是，給定節(jié)點c1的直接父親是這個節(jié)點的一個祖先，且這兩個節(jié)點之間不應該有任何其他的節(jié)點，因此，你可以用一個遞歸的外聯(lián)結來查詢一個節(jié)點，它就是c1的祖先，也同時是另一個節(jié)點Y的后代，隨后我們使y=x就查詢，直到查詢返回空，即不存在這樣的節(jié)點，此時y便是c1的直接父親節(jié)點。
比如，要找到評論6的直接父節(jié)點：老實說，SQL語句又長又臭，行肯定是行，但我真的寫不動了。
2、對樹進行操作，比如插入和移動節(jié)點。
當插入一個節(jié)點時，你需要重新計算新插入節(jié)點的相鄰兄弟節(jié)點、祖先節(jié)點和它祖先節(jié)點的兄弟，來確保它們的左右值都比這個新節(jié)點的左值大。同時，如果這個新節(jié)點是一個非葉子節(jié)點，你還要檢查它的子孫節(jié)點。
夠了，夠了。就憑查直接父節(jié)點都困難，這個東西就很冷門了。我確定我不會使用這種設計了。
四、閉包表
閉包表是解決分層存儲一個簡單而又優(yōu)雅的解決方案，它記錄了表中所有的節(jié)點關系，并不僅僅是直接的父子關系。
在閉包表的設計中，額外創(chuàng)建了一張TreePaths的表(空間換取時間)，它包含兩列，每一列都是一個指向Comments中的CommentId的外鍵。
CREATE TABLE Comments( CommentId int PK, ArticleId int, CommentBody int, FOREIGN KEY(ArticleId) REFERENCES Articles(Id))
父子關系表：
CREATE TABLE TreePaths( ancestor int, descendant int, PRIMARY KEY(ancestor,descendant), --復合主鍵 FOREIGN KEY (ancestor) REFERENCES Comments(CommentId), FOREIGN KEY (descendant) REFERENCES Comments(CommentId))
在這種設計中，Comments表將不再存儲樹結構，而是將書中的祖先-后代關系存儲為TreePaths的一行，即使這兩個節(jié)點之間不是直接的父子關系；同時還增加一行指向節(jié)點自己，理解不了？就是TreePaths表存儲了所有祖先-后代的關系的記錄。如下圖:
Comment表：
TreePaths表：
優(yōu)點：
1、查詢所有后代節(jié)點(查子樹)：
SELECT c.* FROM Comment AS c INNER JOIN TreePaths t on c.CommentId = t.descendant WHERE t.ancestor = 4
結果如下：
2、查詢評論6的所有祖先(查祖先樹)：
SELECT c.* FROM Comment AS c INNER JOIN TreePaths t on c.CommentId = t.ancestor WHERE t.descendant = 6
顯示結果如下：
3、插入新節(jié)點：
要插入一個新的葉子節(jié)點，應首先插入一條自己到自己的關系，然后搜索TreePaths表中后代是評論5的節(jié)點，增加該節(jié)點與要插入的新節(jié)點的"祖先-后代"關系。
比如下面為插入評論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í)行以后：
至于Comment表那就簡單得不說了。
4、刪除葉子節(jié)點：
比如刪除葉子節(jié)點7,應刪除所有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é)點，先斷開與原祖先的關系，然后與新節(jié)點建立關系的SQL語句都不難寫。
另外，閉包表還可以優(yōu)化，如增加一個path_length字段，自我引用為0，直接子節(jié)點為1，再一下層為2，一次類推，查詢直接自子節(jié)點就變得很簡單。
總結
其實，在以往的工作中，曾見過不同類型的設計，鄰接表，路徑枚舉，鄰接表路徑枚舉一起來的都見過。
每種設計都各有優(yōu)劣，如果選擇設計依賴于應用程序中哪種操作最需要性能上的優(yōu)化。
下面給出一個表格，來展示各種設計的難易程度：
設計表數(shù)量查詢子查詢樹插入刪除引用完整性
鄰接表1簡單簡單簡單簡單是
枚舉路徑1簡單簡單簡單簡單否
嵌套集1困難簡單困難困難否
閉包表2簡單簡單簡單簡單是
1、鄰接表是最方便的設計，并且很多軟件開發(fā)者都了解它。并且在遞歸查詢的幫助下，使得鄰接表的查詢更加高效。
2、枚舉路徑能夠很直觀地展示出祖先到后代之間的路徑，但由于不能確保引用完整性，使得這個設計比較脆弱。枚舉路徑也使得數(shù)據(jù)的存儲變得冗余。
3、嵌套集是一個聰明的解決方案，但不能確保引用完整性，并且只能使用于查詢性能要求較高，而其他要求一般的場合使用它。
4、閉包表是最通用的設計，并且最靈活，易擴展，并且一個節(jié)點能屬于多棵樹，能減少冗余的計算時間。但它要求一張額外的表來存儲關系，是一個空間換取時間的方案。
