MySQL 樹型結構建模：鄰接表 vs MPTT 及雙向轉換算法

兩種經典模型

1. 鄰接表

• 字段：id (PK)、parent_id (FK 指向父節點)。
• 優點：結構簡單，理解易，修改節點父子關係只需改一行。
• 缺點：查詢子樹需遞歸 SQL，層級深時查詢數爆炸，性能差，擴展困難。

2. MPTT (Modified Preorder Tree Traversal)

• 在鄰接表基礎上增加 lft、rgt 字段，標識深度優先遍歷順序。
• 根節點 lft=1，每訪問一個節點 lft+1，葉節點 rgt=lft+1，回溯父節點 rgt 繼續遞增。
• 優點：查詢子樹無需遞歸，單條 SQL 完成：WHERE lft BETWEEN parent.lft AND parent.rgt，效率極高。
• 缺點：移動子樹需重算大量節點的 lft/rgt，寫入開銷大。

MPTT → 鄰接表（簡單）

父節點 = level = 當前 level - 1 AND lft < 當前 lft AND rgt > 當前 rgt 的節點。

鄰接表 → MPTT：近似遞推算法（避免遞歸棧溢出）

輸入：鄰接表 (id, pid)。輸出：MPTT 表 (id, lvl, lft, rgt)，輔助字段 cnt (子樹節點數)、seq (遍歷序號)。

算法步驟

1. 根節點入表：lvl=1, lft=1, rgt=NULL, cnt=NULL, seq=1。
2. 逐層展開子節點：lvl = 父 lvl + 1。
3. 自底向上計算 cnt：從最大 lvl 向 1 遞減，cnt = SUM(子節點.cnt) + 1。
4. 自頂向下計算 seq：從 lvl=1 向下，seq = 父.seq + SUM(同級 id < 當前 id 的兄弟.cnt) + 1。
5. 推導 lft/rgt：lft = seq*2 - lvl，rgt = lft + cnt*2 - 1。

優勢

• 無遞歸，無棧溢出風險。
• 純 SQL 集合操作，效率高，已項目驗證。

選型建議

• 讀多寫少、樹深、頻繁查子樹 → MPTT。
• 寫多、樹結構頻繁變動、層級淺 → 鄰接表（配合應用層緩存/物化路徑）。
• MySQL 8.0+ 可用 WITH RECURSIVE CTE 優雅查詢鄰接表子樹，減弱 MPTT 優勢。