首頁>技術>

出處: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

12
最新評論
  • BSA-TRITC(10mg/ml) TRITC-BSA 牛血清白蛋白改性標記羅丹明
  • Anaconda詳細教程