[食譜好菜] 另外一種存放樹狀結構資料的資料表設計方式 - Nested Set Model(巢狀集合模型)

先前跟大家分享 CTE 遞迴的寫法,在粉絲團貼文的留言中,就有網友分享另一種存放樹狀結構資料的設計方式 - Nested Set Model(巢狀集合模型),這篇文章就來跟大家分享 Nested Set Model 資料表的設計方式。

我們印象中最常用的設計方式叫做 - Adjacency List Model(鄰接表模型),先前文章的範例 Genealogy 資料表就是一種 Adjacency List Model 的設計方式,我就延續這個範例,將它修改成 Nested Set Model 的設計方式。

Left and Right

Nested Set Model 的設計方式比 Adjacency List Model 的設計方式至少會多出兩個欄位:LeftRight

它可以用來標記一個節點有多大一串,比如說 Johnny 的 Left/Right 的值分別為 1/8,我們把 (Right - Left) ÷ 2 = (8 - 1) ÷ 2 = 3.5,無條件捨去取整數就等於 3,就是 Johnny 之下所有子孫的個數,而無條件進位取整數就等於 4,就是 Johnny 以下所有家族成員個數,底下就是 Johnny 家族的巢狀樹示意圖。

這樣子設計看起來就像上層包下層,一層包一層,我們也可以觀察到一個特性,就是一個節點的 Left 值永遠在父節點的 Left 與 Right 之間,所以要撈出任何一個人以下的所有家族成員,只要把這個特性當成 JOIN 的條件去下查詢就可以撈出來了。

SELECT
    descendant.*
FROM Genealogy descendant WITH (NOLOCK)
INNER JOIN Genealogy ancestor WITH (NOLOCK)
    ON descendant.[Left] BETWEEN ancestor.[Left] AND ancestor.[Right]
WHERE ancestor.Id = 1

除了列出結果之外,我們也順便跟 CTE 寫法(下面)的執行計劃做比較,可以看到節點比較少,箭頭的線也比較細。

※ 節點愈少,表示滿足查詢所需執行的運算愈少;箭頭的線愈細,表示滿足查詢所需讀取的資料列愈少。

看到這邊各位朋友應該也有感覺到,雖然查詢效能比 CTE 寫法好不少,但是只要節點有異動,Left 及 Right 的欄位就要跟著更新,在維護上得費不少工夫,所以接下來,我們就針對節點的異動做幾個範例。

新增節點

新增節點大致上分成兩種情況,第一種是新節點單純地附加在父節點底下,不管順序。第二種是新節點要安插在父節點底下的特定位置。我們兩種都來寫寫看。

新節點單純地附加在父節點底下,不管順序。

這種的就比較簡單一點,邏輯大概是這樣:

找到父節點,再將大於等於父節點 Right 的 Left/Right 都加上 2,最後將父節點的 Right 當做新節點的 Left。

假設我有一個 JohnnyG2 要加到 LittleJohnny 底下,示意圖及 SQL 語句如下:

BEGIN TRANSACTION

SET TRANSACTION ISOLATION LEVEL SERIALIZABLE

DECLARE @ParentId INT = 2
DECLARE @Name NVARCHAR(50) = N'JohnnyG2'
DECLARE @Left BIGINT

SELECT
    @Left = g.[Right]
FROM Genealogy g WITH (UPDLOCK, TABLOCK)
WHERE g.Id = @ParentId

UPDATE Genealogy SET [Left] = [Left] + 2 WHERE [Left] >= @Left
UPDATE Genealogy SET [Right] = [Right] + 2 WHERE [Right] >= @Left

INSERT INTO Genealogy([Name]
                     ,ParentId
                     ,[Left]
                     ,[Right])
    VALUES (@Name
           ,@ParentId
           ,@Left
           ,@Left + 1);

COMMIT TRANSACTION

執行完之後,Johnny 家族的巢狀樹就變成下面這樣。

新節點要安插在父節點底下的特定位置

再來,如果父節點底下已經有若干個子節點,新節點想要安插在子節點之間,大致的邏輯是:

找到要被替換位置的子節點,將大於等於子節點 Left 的 Left/Right 都加上 2,最後將該子節點的 Left 當做新節點的 Left。

假設我有一個 LittleJohnny22 要加到 LittleJohnny2 與 LittleJohnny3 之間,說是這樣說,但實際上是取代 LittleJohnny3 的位置,示意圖如下:

SQL 語句我們稍微調整一下,讓它可以相容第一種新增節點的情境。

BEGIN TRANSACTION

SET TRANSACTION ISOLATION LEVEL SERIALIZABLE

DECLARE @ParentId INT = 1
DECLARE @SiblingId INT = 4
DECLARE @Name NVARCHAR(50) = N'LittleJohnny22'
DECLARE @Left BIGINT

SELECT
    @Left =
    CASE
        WHEN @SiblingId IS NOT NULL THEN g.[Left]
        ELSE g.[Right]
    END
FROM Genealogy g WITH (UPDLOCK, TABLOCK)
WHERE g.Id = COALESCE(@SiblingId, @ParentId)

UPDATE Genealogy SET [Left] = [Left] + 2 WHERE [Left] >= @Left
UPDATE Genealogy SET [Right] = [Right] + 2 WHERE [Right] >= @Left

INSERT INTO Genealogy([Name]
                     ,ParentId
                     ,[Left]
                     ,[Right])
    VALUES (@Name
           ,@ParentId
           ,@Left
           ,@Left + 1);

COMMIT TRANSACTION

下面是執行完之後,巢狀樹的示意圖。

刪除節點

接著是刪除節點,刪除節點也有兩種,第一種是節點被刪除之後,連同子節點一起刪除。第二種是節點被刪除之後,子節點提升一層。

節點被刪除之後,連同子節點一起刪除。

這種的單純一點,就是:

將 Left 值在被刪除節點的 Left/Right 以內的節點刪除,並且將大於被刪除節點 Right 的 Left/Right 減掉被刪除的寬度。

假設我要刪掉 LittleJohnny,示意圖及 SQL 語句如下:

BEGIN TRANSACTION

SET TRANSACTION ISOLATION LEVEL SERIALIZABLE

DECLARE @NodeId INT = 2
DECLARE @Left BIGINT
DECLARE @Right BIGINT

SELECT
    @Left = g.[Left],
    @Right = g.[Right]
FROM Genealogy g WITH (UPDLOCK, TABLOCK)
WHERE g.Id = @NodeId

DELETE FROM Genealogy WHERE [Left] BETWEEN @Left AND @Right

DECLARE @Width BIGINT = @Right - @Left + 1

UPDATE Genealogy SET [Left] = [Left] - @Width WHERE [Left] > @Right
UPDATE Genealogy SET [Right] = [Right] - @Width WHERE [Right] > @Right

COMMIT TRANSACTION

下面是刪除之後,巢狀樹的示意圖。

節點被刪除之後,子節點提升一層。

再來這種就稍微麻煩一點,大致上是:

節點被刪除之後,將子節點的 Left/Right 全部減 1,再將大於被刪除節點 Right 的 Left/Right 減掉 2。

假設一樣要刪除 LittleJohnny,但是子節點提升一層,示意圖及 SQL 語句如下:

BEGIN TRANSACTION

SET TRANSACTION ISOLATION LEVEL SERIALIZABLE

DECLARE @NodeId INT = 2
DECLARE @Left BIGINT
DECLARE @Right BIGINT

SELECT
    @Left = g.[Left],
    @Right = g.[Right]
FROM Genealogy g WITH (UPDLOCK, TABLOCK)
WHERE g.Id = @NodeId

DELETE FROM Genealogy WHERE Id = @NodeId

UPDATE Genealogy SET [Left] = [Left] - 1, [Right] = [Right] - 1 WHERE [Left] BETWEEN @Left AND @Right
UPDATE Genealogy SET [Left] = [Left] - 2 WHERE [Left] > @Right
UPDATE Genealogy SET [Right] = [Right] - 2 WHERE [Right] > @Right

COMMIT TRANSACTION

執行完畢之後,整個巢狀樹的示意圖如下:

搬移節點

接下來我們進入了更複雜的情境了,搬移節點我們可以看成是「先刪除節點再新增節點」,但是實際上並沒有真的將節點刪除再新增,只是 Left/Right 值的改變而已。

假設我要將 LittleJohnny 節點移到 LittleJohnny22 與 LittleJohnny3 之間,示意圖及 SQL 語句如下:

BEGIN TRANSACTION

SET TRANSACTION ISOLATION LEVEL SERIALIZABLE

DECLARE @NodeId INT = 2
DECLARE @ParentId INT = 1
DECLARE @SiblingId INT = 4
DECLARE @SrcLeft BIGINT
DECLARE @SrcRight BIGINT

SELECT
    @SrcLeft = g.[Left]
   ,@SrcRight = g.[Right]
FROM Genealogy g WITH (UPDLOCK, TABLOCK)
WHERE g.Id = @NodeId

DECLARE @Width BIGINT = @SrcRight - @SrcLeft + 1

UPDATE Genealogy SET [Left] = -[Left], [Right] = -[Right] WHERE [Left] BETWEEN @SrcLeft AND @SrcRight -- 將被搬移的節點先移出巢狀樹
UPDATE Genealogy SET [Left] = [Left] - @Width WHERE [Left] > @SrcRight
UPDATE Genealogy SET [Right] = [Right] - @Width WHERE [Right] > @SrcRight

DECLARE @DstLeft BIGINT

SELECT
    @DstLeft =
    CASE
        WHEN @SiblingId IS NOT NULL THEN g.[Left]
        ELSE g.[Right]
    END
FROM Genealogy g
WHERE g.Id = COALESCE(@SiblingId, @ParentId)

DECLARE @Distance BIGINT = @DstLeft - @SrcLeft -- 移動的距離

UPDATE Genealogy SET [Left] = [Left] + @Width WHERE [Left] >= @DstLeft
UPDATE Genealogy SET [Right] = [Right] + @Width WHERE [Right] >= @DstLeft
UPDATE Genealogy SET [Left] = -[Left] + @Distance, [Right] = -[Right] + @Distance WHERE [Left] BETWEEN -@SrcRight AND -@SrcLeft

COMMIT TRANSACTION

搬移完之後,整個巢狀樹如下圖:

查詢節點

我們在增刪改節點之後,最重要的是將節點撈出來,起手式是將子節點跟其祖先節點先撈出來,SQL 語句很簡單,也很好理解,在上面已經展示過了。

SELECT
    *
FROM Genealogy descendant WITH (NOLOCK)
INNER JOIN Genealogy ancestor WITH (NOLOCK)
    ON descendant.[Left] BETWEEN ancestor.[Left] AND ancestor.[Right]

整個家族的上下關係透過這個 JOIN 的語法就能撈出來,我們只要在這個 JOIN 的語法上再去做加工,就能撈出我們想要的結果,下面我們就來寫幾個查詢範例。

查詢任一人底下的所有成員

這個在上面已經有展示過了,這邊就不再贅述。

查詢任一人的血脈

這個就是找出自己還有自己頭上的祖先,假設我們找出 JohnnyG2 的血脈,示意圖、 SQL 語句及查詢結果如下:

SELECT
    ancestor.*
FROM Genealogy descendant WITH (NOLOCK)
INNER JOIN Genealogy ancestor WITH (NOLOCK)
    ON descendant.[Left] BETWEEN ancestor.[Left] AND ancestor.[Right]
WHERE descendant.Id = 5

查詢家族成員是第幾代人

這個只要算一下自己有幾個祖先,就能知道自己是第幾代人了,SQL 語句及查詢結果如下:

SELECT
    descendant.Id
   ,descendant.[Name]
   ,COUNT(ancestor.Id) AS [Generation]
FROM Genealogy descendant WITH (NOLOCK)
INNER JOIN Genealogy ancestor WITH (NOLOCK)
    ON descendant.[Left] BETWEEN ancestor.[Left] AND ancestor.[Right]
GROUP BY descendant.Id
        ,descendant.[Name]

查詢任一人下的第幾代

剛剛我們已經撈出每個家族成員是第幾代人了,把這個資訊 JOIN 進我們原本的查詢裡面,我們就可以下條件了,假設要找到 Johnny 下的第二代,也就是孫子輩的成員,示意圖、SQL 語句及查詢結果如下:

SELECT
    descendant.*
FROM Genealogy descendant WITH (NOLOCK)
LEFT JOIN (SELECT
        g1.Id
       ,COUNT(g2.Id) AS [Generation]
    FROM Genealogy g1 WITH (NOLOCK)
    INNER JOIN Genealogy g2 WITH (NOLOCK)
        ON g1.[Left] BETWEEN g2.[Left] AND g2.[Right]
    GROUP BY g1.Id) gs
    ON descendant.Id = gs.Id
INNER JOIN Genealogy ancestor WITH (NOLOCK)
    ON descendant.[Left] BETWEEN ancestor.[Left] AND ancestor.[Right]
WHERE ancestor.Id = 1
    AND gs.Generation = 3

不過我在這邊差點被制約了,如果要撈出兒子輩的成員,其實不需要像上面這樣寫,直接找 Parent 是 Johnny 的成員出來就好了。

優缺點

最後我們來說一下 Nested Set Model 的優缺點,優點顯而易見的,查詢效能比 Adjacency List Model 好很多,但是缺點也顯而易見,要維護 Left/Right 我們得費不少力氣,可想而知,如果我們的節點經常異動,我們的索引很快就要重整或重建了,而且經常異動節點,也意謂著引發資源競爭的問題會越頻繁。

所以,Nested Set Model 及 Adjacency List Model 要選哪一種設計方式,評估上倒不是看優點了,而是實作在我們的需求上,哪一種設計方式的缺點不會被放大?

以上的內容分享給大家,希望對大家在樹狀結構資料表的設計有一點幫助,如果有任何相關經驗,也歡迎不吝分享。

參考資料

C# 指南ASP.NET 教學ASP.NET MVC 指引
Azure SQL Database 教學SQL Server 教學Xamarin.Forms 教學