數(shù)據(jù)庫(kù)表設(shè)計(jì)-鄰接表、路徑枚舉、嵌套集、閉包表
發(fā)表時(shí)間：2023-09-02 來(lái)源：明輝站整理相關(guān)軟件相關(guān)文章人氣：
[摘要]我們?cè)谠O(shè)計(jì)數(shù)據(jù)庫(kù)的時(shí)候，是否會(huì)突破常規(guī)，找到最適合自己需求的設(shè)計(jì)方案，下面來(lái)舉個(gè)例子： 常用的鄰接表設(shè)計(jì)，都會(huì)添加 一個(gè) parent_id 字段，比如區(qū)域表（國(guó)、省、市、區(qū)）：CREATE TABLE Area ([id] [int] NOT NULL,[name] [nvarchar]...
我們?cè)谠O(shè)計(jì)數(shù)據(jù)庫(kù)的時(shí)候，是否會(huì)突破常規(guī)，找到最適合自己需求的設(shè)計(jì)方案，下面來(lái)舉個(gè)例子：
常用的鄰接表設(shè)計(jì)，都會(huì)添加 一個(gè) parent_id 字段，比如區(qū)域表（國(guó)、省、市、區(qū)）：
CREATE TABLE Area ([id] [int] NOT NULL,[name] [nvarchar] (50) NULL,[parent_id] [int] NULL,[type] [int] NULL );
name:地域的名稱， parent_id 是父ID，省的父ID是國(guó)，市的父ID 為省，以此類推。
type 是區(qū)域的階級(jí)： 1：國(guó)，2：省，3：市，4：區(qū)
在層級(jí)比較確定的情況下，這么設(shè)計(jì)表格沒(méi)有什么問(wèn)題，調(diào)用起來(lái)也很方便。
但是使用這種鄰接表設(shè)計(jì)方式，并不能滿足所有的需求，當(dāng)我們不確定層級(jí)的情況下，假設(shè)我有下面一個(gè)評(píng)論結(jié)構(gòu)：
用鄰接表記錄這個(gè)評(píng)論的數(shù)據(jù)（comments 表）：
| comment_id | parent_id | author | comment |
| 1 | 0 | 小明 | 我不大認(rèn)同這個(gè)觀點(diǎn) |
| 2 | 1 | 小張 | 我也不認(rèn)同 |
| 3 | 2 | 小紅 | 我同意樓上 |
| 4 | 1 | 小全 | 你為什么不認(rèn)同呢 |
| 5 | 4 | 小明 | 我以前遇到過(guò)這情況 |
| 6 | 5 | 小張 | 那也不代表你所說(shuō)是對(duì)的 |
| 7 | 5 | 小新 | 這個(gè)視情況而定吧 |
大家有沒(méi)發(fā)現(xiàn)，這么設(shè)計(jì)表，如果要查詢一個(gè)節(jié)點(diǎn)的所有后代，是很難實(shí)現(xiàn)的，你可以使用關(guān)聯(lián)查詢來(lái)獲取一條評(píng)論和他的后代：
SELECT c1.*, c2.* FROM comments c1 LEFT OUTER JOIN comments c2 ON c2.parent_id = c1.comment_id;
然而這個(gè)查詢只能獲取兩層的數(shù)據(jù)。這種樹的特性就是可以任意深地拓展，你需要有相應(yīng)的方法來(lái)獲取它的深度數(shù)據(jù)。比如，可能需要計(jì)算一個(gè)評(píng)論分支的數(shù)量，或者計(jì)算一個(gè)機(jī)械設(shè)備的所有的總開銷。
某些情況下，在項(xiàng)目中使用鄰接表正好適用。鄰接表設(shè)計(jì)的優(yōu)勢(shì)在于能快速的獲取一個(gè)給定節(jié)點(diǎn)的直接父子節(jié)點(diǎn)，它也很容易插入新節(jié)點(diǎn)。如果這樣的需求就是你的項(xiàng)目對(duì)于分層數(shù)據(jù)的全部操作，那使用鄰接表就可以很好的工作了。
遇到上述的樹模型，有幾種方案是可以考慮下的：路徑枚舉、嵌套集以及閉包表。這些解決方案通�？瓷先ケ揉徑颖韽�(fù)雜很多，但它們的確使得某些使用鄰接表比較復(fù)雜或很低效的操作變得更簡(jiǎn)單。如果你的項(xiàng)目確實(shí)需要提供這些操作，那么這些設(shè)計(jì)會(huì)是鄰接表更好的選擇。
一、路徑枚舉
在comments 表中，我們使用類型varchar 的path 字段來(lái)替代原來(lái)的parent_id 字段。這個(gè)path 字段所存儲(chǔ)的內(nèi)容為當(dāng)前節(jié)點(diǎn)的最頂層祖先到它的自己的序列，就像UNIX的路徑一樣，你甚至可以使用 '/' 作為路徑的分隔符。
| comment_id | path | author | comment |
| 1 | 1 | 小明 | 我不大認(rèn)同這個(gè)觀點(diǎn) |
| 2 | 1/2 | 小張 | 我也不認(rèn)同 |
| 3 | 1/2/3 | 小紅 | 我同意樓上 |
| 4 | 1/4 | 小全 | 你為什么不認(rèn)同呢 |
| 5 | 1/4/5 | 小明 | 我以前遇到過(guò)這情況 |
| 6 | 1/4/5/6 | 小張 | 那也不代表你所說(shuō)是對(duì)的 |
| 7 | 1/4/5/7 | 小新 | 這個(gè)視情況而定吧 |
你可以通過(guò)比較每個(gè)節(jié)點(diǎn)的路徑來(lái)查詢一個(gè)節(jié)點(diǎn)祖先。比如：要找到評(píng)論#7， 路徑是 1/4/5/7一 的祖先，可以這么做：
SELECT * FROM comments AS c WHERE '1/4/5/7' LIKE c.path '%' ;
這句話查詢語(yǔ)句會(huì)匹配到路徑為 1/4/5/%，1/4/% 以及 1/% 的節(jié)點(diǎn)，而這些節(jié)點(diǎn)就是評(píng)論#7的祖先。
同時(shí)還可以通過(guò)將LIKE 關(guān)鍵字兩邊的參數(shù)互換，來(lái)查詢一個(gè)給定節(jié)點(diǎn)的所有后代。比如查詢?cè)u(píng)論#4，路徑path為 ‘1/4’ 的所有后代，可以使用如下語(yǔ)句：
SELECT * FROM comemnts AS c WHERE c.path LIKE '1/4' '%' ;
這句查詢語(yǔ)句所有能找到的后臺(tái)路徑分別是：1/4/5、1/4/5/6、1/4/5/7。
一旦你可以很簡(jiǎn)單地獲取一棵子樹或者從子孫節(jié)點(diǎn)到祖先節(jié)點(diǎn)的路徑，你就可以很簡(jiǎn)單地實(shí)現(xiàn)更多的查詢，如查詢一顆子樹所有節(jié)點(diǎn)上值的總和。
插入一個(gè)節(jié)點(diǎn)也可以像使用鄰接表一樣地簡(jiǎn)單。你所需要做的只是復(fù)制一份要插入節(jié)點(diǎn)的父親節(jié)點(diǎn)路徑，并將這個(gè)新節(jié)點(diǎn)的ID追加到路徑末尾即可。
路徑枚舉也存在一些缺點(diǎn)，比如數(shù)據(jù)庫(kù)不能確保路徑的格式總是正確或者路徑中的節(jié)點(diǎn)確實(shí)存在。依賴于應(yīng)用程序的邏輯代碼來(lái)維護(hù)路徑的字符串，并且驗(yàn)證字符串的正確性開銷很大。無(wú)論將varchar 的長(zhǎng)度設(shè)定為多大，依舊存在長(zhǎng)度的限制，因而并不能夠支持樹結(jié)構(gòu)無(wú)限擴(kuò)展。
二、 嵌套集
嵌套集解決方案是存儲(chǔ)子孫節(jié)點(diǎn)的相關(guān)信息，而不是節(jié)點(diǎn)的直接祖先。我們使用兩個(gè)數(shù)字來(lái)編碼每個(gè)節(jié)點(diǎn)，從而表示這一信息，可以將這兩個(gè)數(shù)字稱為nsleft 和 nsright。
每個(gè)節(jié)點(diǎn)通過(guò)如下的方式確定nsleft 和nsright 的值：nsleft的數(shù)值小于該節(jié)點(diǎn)所有后代ID，同時(shí)nsright 的值大于該節(jié)點(diǎn)的所有后代的ID。這些數(shù)字和comment_id 的值并沒(méi)有任何關(guān)聯(lián)。
確定這三個(gè)值（nsleft，comment_id，nsright）的簡(jiǎn)單方法是對(duì)樹進(jìn)行一次深度優(yōu)先遍歷，在逐層深入的過(guò)程中依次遞增地分配nsleft的值，并在返回時(shí)依次遞增地分配nsright的值。得到數(shù)據(jù)如下:
| comment_id | nsleft | nsright | author | comment |
| 1 | 1 | 14 | 小明 | 我不大認(rèn)同這個(gè)觀點(diǎn) |
| 2 | 2 | 5 | 小張 | 我也不認(rèn)同 |
| 3 | 3 | 4 | 小紅 | 我同意樓上 |
| 4 | 6 | 13 | 小全 | 你為什么不認(rèn)同呢 |
| 5 | 7 | 12 | 小明 | 我以前遇到過(guò)這情況 |
| 6 | 8 | 9 | 小張 | 那也不代表你所說(shuō)是對(duì)的 |
| 7 | 10 | 11 | 小新 | 這個(gè)視情況而定吧 |
一旦你為每個(gè)節(jié)點(diǎn)分配了這些數(shù)字，就可以使用它們來(lái)找到指定節(jié)點(diǎn)的祖先和后代。比如搜索評(píng)論#4及其所有后代，可以通過(guò)搜索哪些節(jié)點(diǎn)的ID在評(píng)論 #4 的nsleft 和 nsright 范圍之間，例：
SELECT c2.* FROM comments AS c1 JOIN comments AS c2 ON c2.nsleft BETWEEN c1.nsleftAND c1.nsright WHERE c1.comment_id = 4;
比如搜索評(píng)論#6及其所有祖先，可以通過(guò)搜索#6的ID在哪些節(jié)點(diǎn)的nsleft 和 nsright 范圍之間，例：
SELECT c2.* FROM comments AS c1 JOIN comments AS c2 ON c1.nsleft BETWEEN c2.nsleftAND c2.nsright WHERE c1.comment_id = 6;
使用嵌套集設(shè)計(jì)的主要優(yōu)勢(shì)是，當(dāng)你想要?jiǎng)h除一個(gè)非葉子節(jié)點(diǎn)時(shí)，它的后代會(huì)自動(dòng)替代被刪除的節(jié)點(diǎn)，成為其直接祖先節(jié)點(diǎn)的直接后代。就是說(shuō)已經(jīng)自動(dòng)減少了一層。
然而，某些在鄰接表的設(shè)計(jì)中表現(xiàn)得很簡(jiǎn)單的查詢，比如獲取一個(gè)節(jié)點(diǎn)的直接父親或者直接后代，在嵌套集設(shè)計(jì)中會(huì)變得比較復(fù)雜。在嵌套集中，如果需要查詢一個(gè)節(jié)點(diǎn)的直接父親，我們會(huì)這么做，比如要找到評(píng)論#6 的直接父親：
SELECT parent.* FROM comments AS c JOIN comments AS parent ON c.nsleft BETWEEN parent.nsleft AND parent.nsrightLEFT OUTER JOIN comments AS in_between ON c.nsleft BETWEEN in_between.nsleft AND in_between.nsrightAND in_between.nsleft BETWEEN parent.nsleft AND parent.nsright WHERE c.comment_id = 6AND in_between.comment_id IS NULL;
總之有些復(fù)雜。
對(duì)樹進(jìn)行操作，比如插入和移動(dòng)節(jié)點(diǎn)，使用嵌套集會(huì)比其它設(shè)計(jì)復(fù)雜很多。當(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)時(shí)一個(gè)非葉子節(jié)點(diǎn)，你還要檢查它的子孫節(jié)點(diǎn)。
如果簡(jiǎn)單快速查詢是整個(gè)程序中最重要的部分，嵌套集是最好的選擇，比操作單獨(dú)的節(jié)點(diǎn)要方便快捷很多。然而，嵌套集的插入和移動(dòng)節(jié)點(diǎn)是比較復(fù)雜的，因?yàn)樾枰匦路峙渥笥抑担绻愕膽?yīng)用程序需要頻繁的插入、刪除節(jié)點(diǎn)，那么嵌套集可能并不合適。
三、閉包表
閉包表是解決分級(jí)存儲(chǔ)的一個(gè)簡(jiǎn)單而優(yōu)雅的解決方案，它記錄了樹中所有節(jié)點(diǎn)間的關(guān)系，而不僅僅只有那些直接的父子節(jié)點(diǎn)。
在設(shè)計(jì)評(píng)論系統(tǒng)時(shí)，我們額外創(chuàng)建了一個(gè)叫 tree_paths 表，它包含兩列，每一列都指向 comments 中的外鍵。
我們不再使用comments 表存儲(chǔ)樹的結(jié)構(gòu)，而是將樹中任何具有（祖先 一 后代）關(guān)系的節(jié)點(diǎn)對(duì)都存儲(chǔ)在treepaths 表里，即使這兩個(gè)節(jié)點(diǎn)之間不是直接的父子關(guān)系；同時(shí)，我們還增加一行指向節(jié)點(diǎn)自己。
| 祖先 | 后代 | 祖先 | 后代 | 祖先 | 后代 | 祖先 | 后代 |
| 1 | 1 | 1 | 7 | 4 | 6 | 7 | 7 |
| 1 | 2 | 2 | 2 | 4 | 7 | | |
| 1 | 3 | 2 | 3 | 5 | 5 | | |
| 1 | 4 | 3 | 3 | 5 | 6 | | |
| 1 | 5 | 4 | 4 | 5 | 7 | | |
| 1 | 6 | 4 | 5 | 6 | 6 | | |
通過(guò)treepaths 表來(lái)獲取祖先和后代比使用嵌套集更加的直接。例如要獲取評(píng)論#4的后代，只需要在 treepaths 表中搜索祖先是評(píng)論 #4的行就行了。同樣獲取后代也是如此。
要插入一個(gè)新的葉子節(jié)點(diǎn)，比如評(píng)論#6的一個(gè)子節(jié)點(diǎn)，應(yīng)首先插入一條自己到自己的關(guān)系，然后搜索 treepaths 表中后代是評(píng)論#6 的節(jié)點(diǎn)，增加該節(jié)點(diǎn)和新插入節(jié)點(diǎn)的“祖先一后代”關(guān)系（新節(jié)點(diǎn)ID 應(yīng)該為8）：
INSERT INTO treepaths (ancestor, descendant)SELECT t.ancestor, 8FROM treepaths AS tWHERE t.descendant = 6UNION ALL SELECT 8, 8;
要?jiǎng)h除一個(gè)葉子節(jié)點(diǎn)，比如評(píng)論#7， 應(yīng)刪除所有treepaths 表中后代為評(píng)論 #7 的行：
DELETE FROM treepaths WHERE descendant = 7;
要?jiǎng)h除一顆完整的子樹，比如評(píng)論#4 和它所有的后代，可刪除所有在 treepaths 表中后代為 #4的行，以及那些以評(píng)論#4后代為后代的行。
閉包表的設(shè)計(jì)比嵌套集更加的直接，兩者都能快捷地查詢給定節(jié)點(diǎn)的祖先和后代，但是閉包表能更加簡(jiǎn)單地維護(hù)分層信息。這兩個(gè)設(shè)計(jì)都比使用鄰接表或者路徑枚舉更方便地查詢給定節(jié)點(diǎn)的直接后代和祖先。
然而你可以優(yōu)化閉包表來(lái)使它更方便地查詢直接父親節(jié)點(diǎn)或者子節(jié)點(diǎn)： 在 treepaths 表中添加一個(gè) path_length 字段。一個(gè)節(jié)點(diǎn)的自我引用的path_length 為0，到它直接子節(jié)點(diǎn)的path_length 為1，再下一層為2，以此類推。這樣查詢起來(lái)就方便多了。
總結(jié)：你該使用哪種設(shè)計(jì)：
種設(shè)計(jì)都各有優(yōu)劣，如何選擇設(shè)計(jì)，依賴于應(yīng)用程序的哪種操作是你最需要性能上的優(yōu)化。
| 方案 | 表數(shù)量 | 查詢子 | 查詢樹 | 插入 | 刪除 | 引用完整性 |
| 鄰接表 | 1 | 簡(jiǎn)單 | 困難 | 簡(jiǎn)單 | 簡(jiǎn)單 | 是 |
| 枚舉路徑 | 1 | 簡(jiǎn)單 | 簡(jiǎn)單 | 簡(jiǎn)單 | 簡(jiǎn)單 | 否 |
| 嵌套集 | 1 | 困難 | 簡(jiǎn)單 | 困難 | 困難 | 否 |
| 閉包表 | 2 | 簡(jiǎn)單 | 簡(jiǎn)單 | 簡(jiǎn)單 | 簡(jiǎn)單 | 是 |
層級(jí)數(shù)據(jù)設(shè)計(jì)比較
1、鄰接表是最方便的設(shè)計(jì)，并且很多程序員都了解它
2、如果你使用的數(shù)據(jù)庫(kù)支持WITH 或者 CONNECT BY PRIOR 的遞歸查詢，那能使得鄰接表的查詢更高效。
3、枚舉路徑能夠很直觀地展示出祖先到后代之間的路徑，但同時(shí)由于它不能確保引用完整性，使得這個(gè)設(shè)計(jì)非常脆弱。枚舉路徑也使得數(shù)據(jù)的存儲(chǔ)變得比較冗余。
4、嵌套集是一個(gè)聰明的解決方案，但可能過(guò)于聰明，它不能確保引用完整性。最好在一個(gè)查詢性能要求很高而對(duì)其他要求一般的場(chǎng)合來(lái)使用它。
5、閉包表是最通用的設(shè)計(jì)，并且以上的方案也只有它能允許一個(gè)節(jié)點(diǎn)屬于多棵樹。它要求一張額外的表來(lái)存儲(chǔ)關(guān)系，使用空間換時(shí)間的方案減少操作過(guò)程中由冗余的計(jì)算所造成的消耗。
這幾種設(shè)計(jì)方案只是我們?nèi)粘ＴO(shè)計(jì)中的一部分，開發(fā)中肯定會(huì)遇到更多的選擇方案。選擇哪一種方案，是需要切合實(shí)際，根據(jù)自己項(xiàng)目的需求，結(jié)合方案的優(yōu)劣，選擇最適合的一種。
我遇到一些開發(fā)人員，為了敷衍了事，在設(shè)計(jì)數(shù)據(jù)庫(kù)表時(shí)，只考慮能否完成眼下的任務(wù)，不太注重以后拓展的問(wèn)題，不考慮查詢起來(lái)是否耗性能�？赡芮捌跀�(shù)據(jù)量不多的時(shí)候，看不出什么影響，但數(shù)據(jù)量稍微多一點(diǎn)的話，就已經(jīng)顯而易見了（例如：可以使用外聯(lián)接查詢的，偏偏要使用子查詢）。
我覺(jué)得設(shè)計(jì)數(shù)據(jù)庫(kù)是一個(gè)很有趣且充滿挑戰(zhàn)的工作，它有時(shí)能體現(xiàn)你的視野有多寬廣，有時(shí)它能讓你睡不著覺(jué)，總之痛并快樂(lè)著。
以上就是數(shù)據(jù)庫(kù)表設(shè)計(jì)-鄰接表、路徑枚舉、嵌套集、閉包表的詳細(xì)內(nèi)容，更多請(qǐng)關(guān)注php中文網(wǎng)其它相關(guān)文章！
學(xué)習(xí)教程快速掌握從入門到精通的SQL知識(shí)。
