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欄位來維護。
結論:
每種設計各有優劣,如何選擇設計依賴於應用程式中的哪種操作最需要性能上的優化。
鄰接表:簡單,但不適用於很深的表;
枚舉路徑:無法保證引用完整性;
嵌套集:無法保證引用完整性,太複雜;
閉包:需要一個額外的表存儲關係;