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欄位來維護。

結論:

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

鄰接表:簡單,但不適用於很深的表;

   枚舉路徑:無法保證引用完整性;

   嵌套集:無法保證引用完整性,太複雜;

   閉包:需要一個額外的表存儲關係;