我們在設(shè)計數(shù)據(jù)庫的時候居砖，是否會突破常規(guī)，找到最適合自己需求的設(shè)計方案岳链，下面來舉個例子：
常用的鄰接表設(shè)計，都會添加 一個 parent_id 字段劲件，比如區(qū)域表（國掸哑、省约急、市、區(qū)）：
CREATE TABLE Area (
[id] [int] NOT NULL,
[name] [nvarchar] (50) NULL,
[parent_id] [int] NULL,
[type] [int] NULL
);
name：地域的名稱苗分， parent_id 是父 ID厌蔽，省的父 ID 是國，市的父 ID 為省俭嘁，以此類推躺枕。
type 是區(qū)域的階級： 1：國服猪，2：省供填，3：市，4：區(qū)
在層級比較確定的情況下罢猪，這么設(shè)計表格沒有什么問題近她，調(diào)用起來也很方便。
但是使用這種鄰接表設(shè)計方式膳帕，并不能滿足所有的需求粘捎，當(dāng)我們不確定層級的情況下，假設(shè)我有下面一個評論結(jié)構(gòu)：
用鄰接表記錄這個評論的數(shù)據(jù)（comments 表）：
大家有沒發(fā)現(xiàn)危彩，這么設(shè)計表攒磨，如果要查詢一個節(jié)點的所有后代，是很難實現(xiàn)的汤徽，你可以使用關(guān)聯(lián)查詢來獲取一條評論和他的后代：
SELECT c1.*, c2.* FROM comments c1 LEFT OUTER JOIN comments c2 ON c2.parent_id = c1.comment_id;
然而這個查詢只能獲取兩層的數(shù)據(jù)娩缰。這種樹的特性就是可以任意深地拓展，你需要有相應(yīng)的方法來獲取它的深度數(shù)據(jù)谒府。比如拼坎，可能需要計算一個評論分支的數(shù)量，或者計算一個機械設(shè)備的所有的總開銷完疫。
某些情況下泰鸡，在項目中使用鄰接表正好適用。鄰接表設(shè)計的優(yōu)勢在于能快速的獲取一個給定節(jié)點的直接父子節(jié)點壳鹤，它也很容易插入新節(jié)點盛龄。如果這樣的需求就是你的項目對于分層數(shù)據(jù)的全部操作，那使用鄰接表就可以很好的工作了芳誓。
遇到上述的樹模型余舶，有幾種方案是可以考慮下的：路徑枚舉、嵌套集以及閉包表兆沙。這些解決方案通撑费浚看上去比鄰接表復(fù)雜很多，但它們的確使得某些使用鄰接表比較復(fù)雜或很低效的操作變得更簡單葛圃。如果你的項目確實需要提供這些操作千扔，那么這些設(shè)計會是鄰接表更好的選擇憎妙。
一、路徑枚舉
在 comments 表中曲楚，我們使用類型 varchar 的 path 字段來替代原來的
parent_id 字段厘唾。這個 path 字段所存儲的內(nèi)容為當(dāng)前節(jié)點的最頂層祖先到它的自己的序列，就像 UNIX 的路徑一樣龙誊，你甚至可以使用 ‘/’ 作為路徑的分隔符抚垃。
你可以通過比較每個節(jié)點的路徑來查詢一個節(jié)點祖先。比如：要找到評論
#7趟大， 路徑是 1/4/5/7一 的祖先鹤树，可以這么做：
SELECT * FROM comments AS c WHERE '1/4/5/7' LIKE c.path || '%' ;
這句話查詢語句會匹配到路徑為 1/4/5/%，1/4/% 以及 1/% 的節(jié)點逊朽，而這些節(jié)點就是評論 #7 的祖先罕伯。
同時還可以通過將LIKE 關(guān)鍵字兩邊的參數(shù)互換，來查詢一個給定節(jié)點的所有后代叽讳。比如查詢評論 #4追他，路徑path為 ‘1/4’ 的所有后代，可以使用如下語句：
SELECT * FROM comemnts AS c WHERE c.path LIKE '1/4' || '%' ;
這句查詢語句所有能找到的后臺路徑分別是：1/4/5岛蚤、1/4/5/6邑狸、1/4/5/7。
一旦你可以很簡單地獲取一棵子樹或者從子孫節(jié)點到祖先節(jié)點的路徑涤妒，你就可以很簡單地實現(xiàn)更多的查詢单雾，如查詢一顆子樹所有節(jié)點上值的總和。
插入一個節(jié)點也可以像使用鄰接表一樣地簡單届腐。你所需要做的只是復(fù)制一份要插入節(jié)點的父親節(jié)點路徑铁坎，并將這個新節(jié)點的 ID 追加到路徑末尾即可。
路徑枚舉也存在一些缺點犁苏，比如數(shù)據(jù)庫不能確保路徑的格式總是正確或者路徑中的節(jié)點確實存在硬萍。依賴于應(yīng)用程序的邏輯代碼來維護路徑的字符串，并且驗證字符串的正確性開銷很大围详。無論將 varchar 的長度設(shè)定為多大朴乖，依舊存在長度的限制，因而并不能夠支持樹結(jié)構(gòu)無限擴展助赞。
二买羞、 嵌套集
嵌套集解決方案是存儲子孫節(jié)點的相關(guān)信息，而不是節(jié)點的直接祖先雹食。我們使用兩個數(shù)字來編碼每個節(jié)點畜普，從而表示這一信息，可以將這兩個數(shù)字稱為 nsleft 和 nsright群叶。
每個節(jié)點通過如下的方式確定 nsleft 和 nsright 的值：nsleft的數(shù)值小于該節(jié)點所有后代 ID吃挑，同時 nsright 的值大于該節(jié)點的所有后代的 ID钝荡。這些數(shù)字和 comment_id 的值并沒有任何關(guān)聯(lián)。
確定這三個值（nsleft舶衬，comment_id埠通，nsright）的簡單方法是對樹進行一次深度優(yōu)先遍歷，在逐層深入的過程中依次遞增地分配 nsleft 的值逛犹，并在返回時依次遞增地分配 nsright 的值端辱。得到數(shù)據(jù)如下:
一旦你為每個節(jié)點分配了這些數(shù)字，就可以使用它們來找到指定節(jié)點的祖先和后代虽画。比如搜索評論 #4 及其所有后代舞蔽，可以通過搜索哪些節(jié)點的 ID 在評論 #4 的 nsleft 和 nsright 范圍之間，例：
SELECT c2.* FROM comments AS c1 JOIN comments AS c2 ON c2.nsleft BETWEEN c1.nsleft
AND c1.nsright WHERE c1.comment_id = 4;
比如搜索評論 #6 及其所有祖先狸捕，可以通過搜索 #6 的 ID 在哪些節(jié)點的
nsleft 和 nsright 范圍之間喷鸽，例：
SELECT c2.* FROM comments AS c1 JOIN comments AS c2 ON c1.nsleft BETWEEN c2.nsleft
AND c2.nsright WHERE c1.comment_id = 6;
使用嵌套集設(shè)計的主要優(yōu)勢是众雷，當(dāng)你想要刪除一個非葉子節(jié)點時灸拍，它的后代會自動替代被刪除的節(jié)點，成為其直接祖先節(jié)點的直接后代砾省。就是說已經(jīng)自動減少了一層鸡岗。
然而，某些在鄰接表的設(shè)計中表現(xiàn)得很簡單的查詢编兄，比如獲取一個節(jié)點的直接父親或者直接后代轩性，在嵌套集設(shè)計中會變得比較復(fù)雜。在嵌套集中狠鸳，如果需要查詢一個節(jié)點的直接父親揣苏，我們會這么做，比如要找到評論 #6 的直接父親：
SELECT parent.* FROM comments AS c JOIN comments AS parent ON c.nsleft BETWEEN parent.nsleft AND parent.nsright
LEFT OUTER JOIN comments AS in_between ON c.nsleft BETWEEN in_between.nsleft AND in_between.nsright
AND in_between.nsleft BETWEEN parent.nsleft AND parent.nsright WHERE c.comment_id = 6
AND in_between.comment_id IS NULL;
總之有些復(fù)雜件舵。
對樹進行操作卸察，比如插入和移動節(jié)點，使用嵌套集會比其它設(shè)計復(fù)雜很多铅祸。當(dāng)插入一個新節(jié)點時坑质，你需要重新計算新插入節(jié)點的相鄰兄弟節(jié)點、祖先節(jié)點和它祖先節(jié)點的兄弟临梗，來確保他們的左右值都比這個新節(jié)點的左值大涡扼。同時，如果這個新節(jié)點時一個非葉子節(jié)點盟庞，你還要檢查它的子孫節(jié)點吃沪。
如果簡單快速查詢是整個程序中最重要的部分，嵌套集是最好的選擇什猖，比操作單獨的節(jié)點要方便快捷很多票彪。然而萎津，嵌套集的插入和移動節(jié)點是比較復(fù)雜的，因為需要重新分配左右值抹镊，如果你的應(yīng)用程序需要頻繁的插入锉屈、刪除節(jié)點，那么嵌套集可能并不合適垮耳。
三颈渊、閉包表
閉包表是解決分級存儲的一個簡單而優(yōu)雅的解決方案，它記錄了樹中所有節(jié)點間的關(guān)系终佛，而不僅僅只有那些直接的父子節(jié)點俊嗽。
在設(shè)計評論系統(tǒng)時，我們額外創(chuàng)建了一個叫 tree_paths 表铃彰，它包含兩列绍豁，每一列都指向 comments 中的外鍵。
我們不再使用 comments 表存儲樹的結(jié)構(gòu)牙捉，而是將樹中任何具有（祖先 一 后代）關(guān)系的節(jié)點對都存儲在 treepaths 表里竹揍，即使這兩個節(jié)點之間不是直接的父子關(guān)系；同時邪铲，我們還增加一行指向節(jié)點自己芬位。
通過 treepaths 表來獲取祖先和后代比使用嵌套集更加的直接。例如要獲取評論#4的后代带到，只需要在 treepaths 表中搜索祖先是評論 #4的行就行了昧碉。同樣獲取后代也是如此。
要插入一個新的葉子節(jié)點揽惹，比如評論#6的一個子節(jié)點被饿，應(yīng)首先插入一條自己到自己的關(guān)系，然后搜索 treepaths 表中后代是評論 #6 的節(jié)點搪搏，增加該節(jié)點和新插入節(jié)點的“祖先一后代”關(guān)系（新節(jié)點 ID 應(yīng)該為 8）：
INSERT INTO treepaths (ancestor, descendant)
SELECT t.ancestor, 8
FROM treepaths AS t
WHERE t.descendant = 6
UNION ALL SELECT 8, 8;
要刪除一個葉子節(jié)點狭握，比如評論 #7， 應(yīng)刪除所有 treepaths 表中后代為評論 #7 的行：
DELETE FROM treepaths WHERE descendant = 7;
要刪除一顆完整的子樹慕嚷，比如評論 #4 和它所有的后代哥牍，可刪除所有在 treepaths 表中后代為 #4 的行，以及那些以評論 #4 后代為后代的行喝检。
閉包表的設(shè)計比嵌套集更加的直接嗅辣，兩者都能快捷地查詢給定節(jié)點的祖先和后代，但是閉包表能更加簡單地維護分層信息挠说。這兩個設(shè)計都比使用鄰接表或者路徑枚舉更方便地查詢給定節(jié)點的直接后代和祖先澡谭。
然而你可以優(yōu)化閉包表來使它更方便地查詢直接父親節(jié)點或者子節(jié)點： 在 treepaths 表中添加一個 path_length 字段。一個節(jié)點的自我引用的
path_length 為 0，到它直接子節(jié)點的 path_length 為 1蛙奖，再下一層為 2潘酗，以此類推。這樣查詢起來就方便多了雁仲。
總結(jié)：你該使用哪種設(shè)計仔夺？
每種設(shè)計都各有優(yōu)劣，如何選擇設(shè)計攒砖，依賴于應(yīng)用程序的哪種操作是你最需要性能上的優(yōu)化缸兔。
層級數(shù)據(jù)設(shè)計比較
鄰接表是最方便的設(shè)計，并且很多程序員都了解它
如果你使用的數(shù)據(jù)庫支持 WITH 或者 CONNECT BY PRIOR 的遞歸查詢吹艇，那能使得鄰接表的查詢更高效惰蜜。
枚舉路徑能夠很直觀地展示出祖先到后代之間的路徑，但同時由于它不能確保引用完整性受神，使得這個設(shè)計非常脆弱抛猖。枚舉路徑也使得數(shù)據(jù)的存儲變得比較冗余。
嵌套集是一個聰明的解決方案鼻听，但可能過于聰明财著，它不能確保引用完整性。最好在一個查詢性能要求很高而對其他要求一般的場合來使用它精算。
閉包表是最通用的設(shè)計瓢宦，并且以上的方案也只有它能允許一個節(jié)點屬于多棵樹。它要求一張額外的表來存儲關(guān)系灰羽，使用空間換時間的方案減少操作過程中由冗余的計算所造成的消耗。
這幾種設(shè)計方案只是我們?nèi)粘ＴO(shè)計中的一部分鱼辙，開發(fā)中肯定會遇到更多的選擇方案廉嚼。選擇哪一種方案，是需要切合實際倒戏，根據(jù)自己項目的需求怠噪，結(jié)合方案的優(yōu)劣，選擇最適合的一種杜跷。
我遇到一些開發(fā)人員傍念，為了敷衍了事，在設(shè)計數(shù)據(jù)庫表時葛闷，只考慮能否完成眼下的任務(wù)憋槐，不太注重以后拓展的問題，不考慮查詢起來是否耗性能淑趾⊙糇校可能前期數(shù)據(jù)量不多的時候，看不出什么影響扣泊，但數(shù)據(jù)量稍微多一點的話近范，就已經(jīng)顯而易見了（例如：可以使用外聯(lián)接查詢的嘶摊，偏偏要使用子查詢）。
我覺得設(shè)計數(shù)據(jù)庫是一個很有趣且充滿挑戰(zhàn)的工作评矩，它有時能體現(xiàn)你的視野有多寬廣叶堆，有時它能讓你睡不著覺，總之痛并快樂著斥杜。
