SQL反模式學習筆記3 單純的樹

• 2019 年 10 月 4 日
• 筆記

2014-10-11

在樹形結構中，實例被稱為節點。每個節點都有多個子節點與一個父節點。

最上層的節點叫做根（root）節點，它沒有父節點。

最底層的沒有子節點的節點叫做葉（leaf）。

中間的節點簡單地稱為非葉節點（nonleaf）。

目標：分成存儲於查詢，比如：系統字典、組織機構、省份區域等樹形結構數據或者以層級方式組織的數據。

反模式：總是依賴父節點，鄰接表。

最簡單的實現方式是添加ParentId欄位，引用同一張表的主鍵ID。

鄰接表維護樹比較方便，但是查詢很笨拙，如果要找一個節點下的所有子節點，要關聯很多次，這個關聯次數取決於樹的深度，

所以，鄰接表不能用於存儲比較深的樹。

如何識別反模式：當出現以下情況時，可能是反模式

（1）我們的數結構要支援多少層

（2）我們總是很害怕接觸那些管理樹結構的程式碼

　　　（3）我需要一個腳本來定期的清理樹中的孤立節點數據

合理使用反模式：

鄰接表設計的優勢在與能快速地獲取一個給定節點的直接父子節點，也很容易插入新節點、維護節點、刪除節點。

如果樹的分層結構不是很深，可以使用這種模式。

【 使用CTE通用表表達式來遞歸查詢樹形結構數據比較方便，詳見「SQL中的CTE通用表表達式」 】

解決方案：使用其他樹模型

　　路徑枚舉：

　　　　用一個path欄位保存當前節點的最頂層的祖先到自己的序列(路徑)

　　　　優點：查詢方便；

　　　　缺點：1、不能保證存儲的值的有效性。

2、增、刪時，要考慮對原位置下的子節點如何處理，比較麻煩。

3、如果還要維護一個排序path，那就更麻煩了。

　　嵌套集：

　　　　存儲子孫節點的相關資訊，而不是節點的直接祖先。用nsleft存儲所有後台的nsleft中最小的數-1，

用nsright存儲所有後台的nsright中最大的數+1。

　　　　優點：刪除時，原來子節點的關係自動上移。

　　　　缺點：1、查詢一個節點的直接上級或下級，很困難。

2、增、刪，困難。

　　閉包：記錄了樹中所有節點間的關係，而不僅僅是只有那些直接的父子關係。

將樹中任何具有「祖先-後代」關係的節點對都存儲在TreePath表中的一行，同時增加一行指向節點自己。

優點：1、能快速的查詢給定節點的祖先與後代；

2、能更加簡單的維護分層資訊；

3、如果刪除了TreePath表中的一條記錄，那麼並不是真正的刪除具體資訊表中的記錄。這樣設計有時候很有用：

比如在產品目錄的分類或者員工組織架構的圖標中，當你改變了節點關係的時候，並不是真的想要刪除一個節點。

我們把關係路徑存儲在一個分開獨立的表中，使得設計更加靈活。

缺點：查詢直接父節點或子節點，需要在表中增加Path_Length欄位來維護。

結論：

每種設計各有優劣，如何選擇設計依賴於應用程式中的哪種操作最需要性能上的優化。

鄰接表：簡單，但不適用於很深的表；

　　 枚舉路徑：無法保證引用完整性；

　　 嵌套集：無法保證引用完整性，太複雜；

　　 閉包：需要一個額外的表存儲關係；