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