關系數據庫中樹形結構設計三種方案：遞歸、左右值、路徑編碼

關系數據庫中樹形結構設計三種方案：遞歸、左右值、路徑編碼

菜單、分類、組織架構等層級數據在關系型數據庫中難以直觀存儲。本文對比三種主流設計方案的優劣與適用場景。

方案一：遞歸關聯（Parent ID / Adjacency List）

CREATE TABLE food(
    fid INT PRIMARY KEY,
    pid INT,              -- 父節點
    fname VARCHAR(50)
);

數據：

1, NULL, 'Food'
2, 1,    'Fruit'
3, 2,    'Red'
4, 3,    'Cherry'
5, 2,    'Yellow'
6, 5,    'Banana'
7, 1,    'Meat'
8, 7,    'Beef'
9, 7,    'Pork

• 查子節點：SELECT * FROM food WHERE pid = 2;（Fruit 下的 Red/Yellow）。
• 查父節點：SELECT * FROM food WHERE fid = 7;（Beef 的父 Meat）。
• 查全樹/所有後代：需遞歸 CTE（MySQL 8.0+）或應用層遞歸，深度大時性能差。

優點：直觀、增刪改簡單、符合範式。
缺點：遞歸查詢慢、深度不可控、難以單條 SQL 獲取完整路徑。

方案二：左右值編碼

CREATE TABLE food_nested(
    fid INT PRIMARY KEY,
    fname VARCHAR(50),
    lft INT NOT NULL,
    rgt INT NOT NULL
);

數據（每節點佔一個區間 [lft, rgt]）：

1, 'Food',   1,  18
2, 'Fruit',  2,  11
3, 'Red',    3,   6
4, 'Cherry', 4,   5
5, 'Yellow', 7,  10
6, 'Banana', 8,   9
7, 'Meat',  12,  17
8, 'Beef',  13,  14
9, 'Pork',  15,  16

• 查所有後代：SELECT * FROM food_nested WHERE lft > 2 AND rgt < 11;（Fruit 及所有子孫）。
• 查祖先鏈：SELECT * FROM food_nested WHERE lft < 4 AND rgt > 5 ORDER BY lft;（Cherry 的祖先）。
• 查子樹節點數：(rgt - lft + 1) / 2。

優點：單條 SQL 完成子樹/祖先查詢，讀性能極強。
缺點：增刪節點需重算大量 lft/rgt，寫入開銷大、併發難控制。

方案三：路徑編碼

CREATE TABLE food_path(
    fid VARCHAR(50) PRIMARY KEY,  -- 編碼即主鍵
    fname VARCHAR(50)
);

編碼規則：子節點 = 父編碼 + 1 字符（如 'a'→'aa'→'aaa'）。

'a',   'Food'
'aa',  'Fruit'
'aaa', 'Red'
'aaaa','Cherry'
'aab', 'Yellow'
'aaba','Banana'
'ab',  'Meat'
'aba', 'Beef'
'abb', 'Pork'

• 查父節點：SELECT * FROM food_path WHERE fid = 'ab';（Beef 父 'ab'）。
• 查路徑：SELECT * FROM food_path WHERE fid IN ('a','ab','aba') ORDER BY fid;。
• 查直接子節點：SELECT * FROM food_path WHERE fid LIKE 'aa_';。
• 查所有後代：SELECT * FROM food_path WHERE fid LIKE 'aa%' AND fid != 'aa';。

優點：讀查詢極簡（LIKE 前綴），支持廣度/深度優先排序（ORDER BY LENGTH(fid) / fid）。
缺點：增刷節點需更新所有後代編碼，編碼長度受限（VARCHAR 上限），深度過大易溢出。

選型決策表