假設你在做小程序分銷分享,需要統計多級之後的分銷用戶,不使用遞歸方式(因為很慢);
假設你正在為一個新聞網站開發一個評論功能,讀者可以評論原文甚至相互回覆?相互回覆會導致無限多的分支,無限多的祖先-後代關係。你要怎麼設計呢?
解決方案:
一、鄰接表:依賴父節點(採用遞歸方式,默認的方案,不推薦)
鄰接表的方案如下(僅僅說明問題):
CREATE TABLE Comments(
CommentId int PK,
ParentId int, --記錄父節點 ArticleId int,
CommentBody nvarchar(500),
FOREIGN KEY (ParentId) REFERENCES Comments(CommentId) --自連接,主鍵外鍵都在自己表內 FOREIGN KEY (ArticleId) REFERENCES Articles(ArticleId)
)
二、路徑枚舉
CREATE TABLE Comments(
CommentId int PK,
Path varchar(100), --僅僅改變了該字段和刪除了外鍵 ArticleId int,
CommentBody nvarchar(500),
FOREIGN KEY (ArticleId) REFERENCES Articles(ArticleId)
)
<code>SELECT * FROM Comment AS cWHERE c.Path LIKE '1,4,%'/<code>
路徑枚舉的缺點:
1、數據庫不能確保路徑的格式總是正確或者路徑中的節點確實存在(中間節點被刪除的情況,沒外鍵約束)。
2、要依賴高級程序來維護路徑中的字符串,並且驗證字符串的正確性的開銷很大。
3、VARCHAR的長度很難確定。無論VARCHAR的長度設為多大,都存在不能夠無限擴展的情況。
路徑枚舉的設計方式能夠很方便地根據節點的層級排序,因為路徑中分隔兩邊的節點間的距離永遠是1,因此通過比較字符串長度就能知道層級的深淺。
三、嵌套集(不推薦)
CREATE TABLE Comments(
CommentId int PK,
nsleft int, --之前的一個父節點
nsright int, --變成了兩個 ArticleId int,
CommentBody nvarchar(500),
FOREIGN KEY (ArticleId) REFERENCES Articles(ArticleId)
)
sleft值的確定:nsleft的數值小於該節點所有後代的Id。
nsright值的確定:nsright的值大於該節點所有後代的Id。
嵌套集缺點:
1、查詢直接父親。
2、對樹進行操作,比如插入和移動節點。
四、閉包表(推薦)
閉包表是解決分層存儲一個簡單而又優雅的解決方案,它記錄了表中所有的節點關係,並不僅僅是直接的父子關係。
在閉包表的設計中,額外創建了一張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)
)
TreePaths表存儲了所有祖先-後代的關係的記錄
查詢所有後代節點(查子樹):
SELECT c.* FROM Comment AS c INNER JOIN TreePaths t on c.CommentId = t.descendant WHERE t.ancestor = 4
查詢評論6的所有祖先(查祖先樹):
SELECT c.* FROM Comment AS c
INNER JOIN TreePaths t on c.CommentId = t.ancestor WHERE t.descendant = 6要插入一個新的葉子節點,比如評論#6的一個子節點,應首先插入一條自己到自己的關係,然後搜索 treepaths 表中後代是評論#6 的節點,增加該節點和新插入節點的“祖先一後代”關係(新節點ID 應該為8):
<code>INSERT INTO treepaths (ancestor, descendant) SELECT t.ancestor, 8 FROM treepaths AS t WHERE t.descendant = 6 UNION ALL SELECT 8, 8;/<code>
總結:你該使用哪種設計:
種設計都各有優劣,如何選擇設計,依賴於應用程序的哪種操作是你最需要性能上的優化。
方案表數量查詢子查詢樹插入刪除引用完整性鄰接表1簡單困難簡單簡單是枚舉路徑1簡單簡單簡單簡單否嵌套集1困難簡單困難困難否閉包表2簡單簡單簡單簡單是
層級數據設計比較
1、鄰接表是最方便的設計,並且很多程序員都瞭解它
2、如果你使用的數據庫支持WITH 或者 CONNECT BY PRIOR 的遞歸查詢,那能使得鄰接表的查詢更高效。
3、枚舉路徑能夠很直觀地展示出祖先到後代之間的路徑,但同時由於它不能確保引用完整性,使得這個設計非常脆弱。枚舉路徑也使得數據的存儲變得比較冗餘。
4、嵌套集是一個聰明的解決方案,但可能過於聰明,它不能確保引用完整性。最好在一個查詢性能要求很高而對其他要求一般的場合來使用它。
5、閉包表是最通用的設計,並且以上的方案也只有它能允許一個節點屬於多棵樹。它要求一張額外的表來存儲關係,使用空間換時間的方案減少操作過程中由冗餘的計算所造成的消耗。
這幾種設計方案只是我們日常設計中的一部分,開發中肯定會遇到更多的選擇方案。選擇哪一種方案,是需要切合實際,根據自己項目的需求,結合方案的優劣,選擇最適合的一種。
關鍵字: 路徑 無限極 REFERENCES