先前跟大家分享 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 的設計方式至少會多出兩個欄位：Left、Right。
它可以用來標記一個節點有多大一串，比如說 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 要選哪一種設計方式，評估上倒不是看優點了，而是實作在我們的需求上，哪一種設計方式的缺點不會被放大？
以上的內容分享給大家，希望對大家在樹狀結構資料表的設計有一點幫助，如果有任何相關經驗，也歡迎不吝分享。
