出處:https://segmentfault.com/a/1190000039204025
儲存樹形結構資料是一個常見的問題,同時也有多種解決方案。
這裡介紹三種樹形結構的表設計方案:
鄰接表模型基於路徑和層級的表設計基於左右值編碼的表設計(MPT)這裡以一個線上食品店作為例子,食品透過類別、顏色和品種組織食品。
示例如下:
一、鄰接表模型最簡單的方法就是使用鄰接表模型或者叫做遞迴模型。透過顯示地描述某一節點的父節點,從而能夠建立二維的關係表,你只需要一個簡單的函式去迭代查詢即可獲取你的資料。
示例如下:
優點:
設計簡單實現容易直觀缺點:
由於是遞迴模型CRUD操作低效二、基於路徑和層級的表設計在一的基礎上加上一個 level 欄位來表示當前節點到根節點的距離和一個 key 欄位來表示搜尋路徑。
Node_id 主鍵Name 名字Parent_id 父節點的idkey 搜尋路徑level 表示當前節點到根節點的距離或者層級示例如下:
兩種需求查詢解決方案如下:
select * from table_name where key like "${d.key}-${d.id}-%"select * from table_name where key like "${d.key}-${d.id}-%" and level=${d.level}+1
此設計結構簡單,利用key和level兩個輔助欄位可以完成查詢操作比一更加高效,而且維護這兩個欄位成本很低。
三、基於左右值編碼的表設計(MPT)為了避免對於樹形結構查詢時的“遞迴”過程,基於Tree的前序遍歷設計一種全新的無遞迴查詢、無限分組的左右值編碼方案,來儲存該樹的資料。
如下圖所示, 從根節點Food左側開始,標記為1,並沿前序遍歷的方向,依次在遍歷的路徑上標註數字,最後我們回到了根節點Food,並在右邊寫上了18。
注:lft 和 rgt 分別對應 DFS 的發現時間 d 和完成時間相同 f
如果我們需要查詢Fruit的後續節點,只需找出所有左值大於2,並且右值小於11的節點即可。
1. 獲取某節點的子孫節點返回某節點子孫節點的前序遍歷列表,以Fruit為例:
SQL: SELECT* FROM Tree WHERE Lft BETWEEN 2 AND 11 ORDER BY Lft ASC
查詢結果如下:
那麼某個節點到底有多少的子孫節點呢?
透過該節點的左、右值我們可以將其子孫節點圈進來,則子孫總數 = (右值 – 左值– 1) / 2,以Fruit為例,其子孫總數為:(11 –2 – 1) / 2 = 4。
同時,為了更為直觀地展現樹形結構,我們需要知道節點在樹中所處的層次,透過左、右值的SQL查詢即可實現。以Fruit為例: SELECT COUNT(*) FROM Tree WHERE Lft <= 2 AND Rgt >=11 。為了方便描述,我們可以為Tree建立一個檢視,新增一個層次數列,該列數值可以寫一個自定義函式來計算,函式定義如下:
CREATE FUNCTION dbo.CountLayer( @node_id int)RETURNS intASbegin declare @result int set @result = 0 declare @lft int declare @rgt int if exists(select Node_id from Tree where Node_id = @node_id) begin select @lft = Lft, @rgt = Rgt from Tree where node_id = @node_id select @result = count(*) from Tree where Lft <= @lft and Rgt >= @rgt end return @resultendGO
基於層次計算函式,我們建立一個檢視,添加了新的記錄節點層次的數列:
CREATE VIEW dbo.TreeViewASSELECT Node_id, Name, Lft, Rgt, dbo.CountLayer(Node_id) AS Layer FROM dbo.Tree ORDER BY LftGO
建立儲存過程,用於計算給定節點的所有子孫節點及相應的層次:
CREATE PROCEDURE [dbo].[GetChildrenNodeList]( @node_id int)ASdeclare @lft intdeclare @rgt intif exists(select Node_id from Tree where node_id = @node_id) begin select @lft = Lft, @rgt = Rgt from Tree where Node_id = @node_id select * from TreeView where Lft between @lft and @rgt order by Lft ASC endGO
現在,我們使用上面的儲存過程來計算節點Fruit所有子孫節點及對應層次,查詢結果如下:
在進行樹的查詢遍歷時,只需要進行2次資料庫查詢,消除了遞迴,再加上查詢條件都是數字的比較,查詢的效率是極高的,隨著樹規模的不斷擴大,基於左右值編碼的設計方案將比傳統的遞迴方案查詢效率提高更多。
2. 獲取某節點的族譜路徑假定我們要獲得某節點的族譜路徑,則根據左、右值分析只需要一條SQL語句即可完成。
以Fruit為例: SELECT* FROM Tree WHERE Lft < 2 AND Rgt > 11 ORDER BY Lft ASC
相對完整的儲存過程如下:
CREATE PROCEDURE [dbo].[GetParentNodePath]( @node_id int)ASdeclare @lft intdeclare @rgt intif exists(select Node_id from Tree where Node_id = @node_id) begin select @lft = Lft, @rgt = Rgt from Tree where Node_id = @node_id select * from TreeView where Lft < @lft and Rgt > @rgt order by Lft ASC endGO
3. 為某節點新增子孫節點
假定我們要在節點“Red”下新增一個新的子節點“Apple”,該樹將變成如下圖所示,其中紅色節點為新增節點。
相對完整的插入子節點的儲存過程:
CREATE PROCEDURE [dbo].[AddSubNode]( @node_id int, @node_name varchar(50))ASdeclare @rgt intif exists(select Node_id from Tree where Node_id = @node_id) begin SET XACT_ABORT ON BEGIN TRANSCTION select @rgt = Rgt from Tree where Node_id = @node_id update Tree set Rgt = Rgt + 2 where Rgt >= @rgt update Tree set Lft = Lft + 2 where Lft >= @rgt insert into Tree(Name, Lft, Rgt) values(@node_name, @rgt, @rgt + 1) COMMIT TRANSACTION SET XACT_ABORT OFF endGO
4. 刪除某節點如果我們想要刪除某個節點,會同時刪除該節點的所有子孫節點,而這些被刪除的節點的個數為:(被刪除節點的右值 – 被刪除節點的左值+ 1) / 2,而剩下的節點左、右值在大於被刪除節點左、右值的情況下會進行調整。來看看樹會發生什麼變化,以Beef為例,刪除效果如下圖所示。
則我們可以構造出相應的儲存過程:
CREATE PROCEDURE [dbo].[DelNode]( @node_id int)ASdeclare @lft intdeclare @rgt intif exists(select Node_id from Tree where Node_id = @node_id) begin SET XACT_ABORT ON BEGIN TRANSCTION select @lft = Lft, @rgt = Rgt from Tree where Node_id = @node_id delete from Tree where Lft >= @lft and Rgt <= @rgt update Tree set Lft = Lft – (@rgt - @lft + 1) where Lft > @lft update Tree set Rgt = Rgt – (@rgt - @lft + 1) where Rgt > @rgt COMMIT TRANSACTION SET XACT_ABORT OFF endGO
小結優點:
消除了遞迴查詢,實現了無限巢狀查詢是基於整數的比較,效率很高缺點:
Reference層次資料結構的資料表設計: https://juejin.cn/post/6844903861413478407#heading-7
樹形結構的資料庫表Schema設計:https://blog.csdn.net/monkey_d_meng/article/details/6647488
出處:https://segmentfault.com/a/1190000039204025