SQL Server 實作無限層級分類：修正預序樹（左/右值編碼）儲存與查詢完整指南

傳統遞迴查詢在層級極深時效能極差。MySQL 開發者提出的「修正預序樹」（Modified Preorder Tree Traversal，MPTT）演算法，透過為每個樹節點編排左值 (LID) 與右值 (RID)，可在單次查詢即取得任意節點及其所有子孫，效能極佳。唯一缺點：尚未原生支援排序，可透過右值反向排序實現先進先出順序。

核心原理

若某節點左值 = 8、右值 = 17，則所有左值 > 8 且右值 < 17 的節點皆為其子孫。反之，某節點左值 = 14、右值 = 15，其所有祖先節點即為左值 < 14 且右值 > 15 的節點。

資料表結構

CL_ZoneData
- ID       : 節點識別碼
- LID      : 左值
- RID      : 右值
- Tree     : 節點深度
- Name     : 節點名稱

三大核心預存程序

1. 查詢節點及其所有子孫

CREATE PROCEDURE CLSP_ZoneSelect
    @Root INT,      -- 根節點 ID
    @Tree INT       -- 最大深度 (0 = 不限制)
AS
SELECT Z.ID, Z.Tree, Z.Name
FROM CL_ZoneData AS Z, CL_ZoneData AS P
WHERE P.ID = @Root
  AND Z.LID >= P.LID AND Z.RID <= P.RID
  AND (@Tree = 0 OR Z.Tree <= P.Tree + @Tree)
ORDER BY Z.LID ASC

2. 在指定節點下新增子節點

CREATE PROCEDURE CLSP_ZoneInsert
    @Root INT,
    @Name NVARCHAR(50)
AS
DECLARE @RID INT, @NID INT, @Tree INT
SET @RID = 1; SET @NID = 0; SET @Tree = 1

IF @Root = 0
    SELECT TOP 1 @RID = RID + 1 FROM CL_CateData ORDER BY RID DESC
ELSE
    SELECT @RID = RID, @Tree = Tree + 1 FROM CL_ZoneData WHERE ID = @Root

IF @Root = 0 OR @RID > 1
BEGIN
    UPDATE CL_ZoneData SET RID = RID + 2 WHERE RID >= @RID
    UPDATE CL_ZoneData SET LID = LID + 2 WHERE LID > @RID
    INSERT INTO CL_ZoneData (LID, RID, Tree, Name) VALUES (@RID, @RID + 1, @Tree, @Name)
    SET @NID = SCOPE_IDENTITY()
END
SELECT @NID

3. 刪除節點及其所有子孫

CREATE PROCEDURE CLSP_ZoneDelete
    @ID INT
AS
DECLARE @LID INT, @RID INT, @WID INT, @DID INT
SET @DID = 0
SELECT @DID = ID, @LID = LID, @RID = RID, @WID = RID - LID + 1
FROM CL_ZoneData WHERE ID = @ID

IF @DID != 0
BEGIN
    DELETE FROM CL_ZoneData WHERE LID BETWEEN @LID AND @RID
    UPDATE CL_ZoneData SET RID = RID - @WID WHERE RID > @RID
    UPDATE CL_ZoneData SET LID = LID - @WID WHERE LID > @RID
END
SELECT @DID

此演算法被作者譽為「見過效能最高的無限級分類算法」，適合讀多寫少的樹狀分類場景（如地區、產品分類），不適合頻繁插入的評論回覆結構。