無限分類 (Infinite Category) 是電商、CMS、OA 系統的核心需求。本文詳細比較兩大主流實作：
並提供現代化 PDO 程式碼、效能測試建議、以及 Closure Table (關係閉包表) 進階方案簡介。
-- 方案一：Adjacency List (父子關係)
CREATE TABLE `category` (
`id` INT UNSIGNED NOT NULL AUTO_INCREMENT PRIMARY KEY,
`name` VARCHAR(100) NOT NULL,
`pid` INT UNSIGNED NOT NULL DEFAULT 0 COMMENT '父分類 ID，0=頂層',
`sort` INT NOT NULL DEFAULT 0 COMMENT '同層排序',
`status` TINYINT NOT NULL DEFAULT 1,
INDEX `idx_pid` (`pid`),
INDEX `idx_status_sort` (`status`, `sort`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4;
-- 方案二：Materialized Path (路徑枚舉)
CREATE TABLE `category_path` (
`id` INT UNSIGNED NOT NULL AUTO_INCREMENT PRIMARY KEY,
`name` VARCHAR(100) NOT NULL,
`pid` INT UNSIGNED NOT NULL DEFAULT 0,
`path` VARCHAR(500) NOT NULL DEFAULT '0' COMMENT '如 0-1-3-7',
`depth` TINYINT NOT NULL DEFAULT 0 COMMENT '層級深度',
`sort` INT NOT NULL DEFAULT 0,
`status` TINYINT NOT NULL DEFAULT 1,
INDEX `idx_path` (`path`),
INDEX `idx_pid` (`pid`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4;
<?php
/**
* 取得完整分類樹 (遞歸組裝)
* @param PDO $pdo
* @return array 樹狀陣列
*/
function getCategoryTree(PDO $pdo): array
{
// 1. 一次撈取所有啟用分類
$stmt = $pdo->query('SELECT id, name, pid, sort FROM category WHERE status=1 ORDER BY sort, id');
$list = $stmt->fetchAll(PDO::FETCH_ASSOC);
// 2. 建立 id => node 映射，並初始化 children
$map = [];
foreach ($list as $node) {
$map[$node['id']] = $node + ['children' => []];
}
// 3. 利用引用 (&) 一次遍歷掛載子節點
$tree = [];
foreach ($map as $id => &$node) {
if ($node['pid'] === 0) {
$tree[$id] = &$node; // 頂層節點
} elseif (isset($map[$node['pid']])) {
$map[$node['pid']]['children'][] = &$node; // 掛載到父節點
}
// 孤兒節點 (pid 不存在) 可選擇丟棄或掛在虛擬根
}
unset($node); // 解除引用
return $tree;
}
/**
* 取得指定分類的所有後代 ID (含自己) - 遞歸查詢
* @param PDO $pdo
* @param int $rootId
* @return array
*/
function getDescendantIds(PDO $pdo, int $rootId): array
{
$ids = [$rootId];
$stmt = $pdo->prepare('SELECT id FROM category WHERE pid = ? AND status=1');
$stmt->execute([$rootId]);
while ($row = $stmt->fetch()) {
$ids = array_merge($ids, getDescendantIds($pdo, $row['id']));
}
return $ids;
}
// --- 使用 ---
$tree = getCategoryTree($pdo);
// 輸出 HTML 選單
function renderSelect(array $tree, int $level = 0): string
{
$html = '';
foreach ($tree as $node) {
$html .= '<option value="' . $node['id'] . '">' . str_repeat('—', $level) . ' ' . htmlspecialchars($node['name']) . '</option>';
if ($node['children']) {
$html .= renderSelect($node['children'], $level + 1);
}
}
return $html;
}
echo '<select>' . renderSelect($tree) . '</select>';
<?php
/**
* 新增分類 (自動計算 path, depth)
* @param PDO $pdo
* @param string $name
* @param int $pid
* @return int 新分類 ID
*/
function addCategory(PDO $pdo, string $name, int $pid = 0): int
{
$pdo->beginTransaction();
try {
if ($pid === 0) {
$path = '0';
$depth = 0;
} else {
$stmt = $pdo->prepare('SELECT path, depth FROM category_path WHERE id = ?');
$stmt->execute([$pid]);
$parent = $stmt->fetch();
if (!$parent) throw new Exception('父分類不存在');
$path = $parent['path'] . '-' . $pid;
$depth = $parent['depth'] + 1;
}
$stmt = $pdo->prepare('INSERT INTO category_path (name, pid, path, depth) VALUES (?, ?, ?, ?)');
$stmt->execute([$name, $pid, $path, $depth]);
$newId = (int) $pdo->lastInsertId();
// 更新自己的 path 包含自己 (方便 LIKE 查詢)
$pdo->prepare('UPDATE category_path SET path = CONCAT(path, "-", ?) WHERE id = ?')->execute([$newId, $newId]);
$pdo->commit();
return $newId;
} catch (Throwable $e) {
$pdo->rollBack();
throw $e;
}
}
/**
* 查詢某分類的所有後代 (單一 SQL，極快)
* @param PDO $pdo
* @param int $rootId
* @return array
*/
function getDescendantsByPath(PDO $pdo, int $rootId): array
{
// 先取得 root 的 path
$stmt = $pdo->prepare('SELECT path FROM category_path WHERE id = ?');
$stmt->execute([$rootId]);
$root = $stmt->fetch();
if (!$root) return [];
$pattern = $root['path'] . '-' . $rootId . '%'; // 如 0-1-3%
$stmt = $pdo->prepare('SELECT * FROM category_path WHERE path LIKE ? AND status=1 ORDER BY path');
$stmt->execute([$pattern]);
return $stmt->fetchAll(PDO::FETCH_ASSOC);
}
/**
* 移動分類 (更新自己及所有後代 path, depth) - 較複雜
* @param PDO $pdo
* @param int $moveId 要移動的分類
* @param int $newPid 新父分類
*/
function moveCategory(PDO $pdo, int $moveId, int $newPid): void
{
$pdo->beginTransaction();
try {
// 1. 取得舊資訊
$stmt = $pdo->prepare('SELECT path, depth FROM category_path WHERE id = ?');
$stmt->execute([$moveId]);
$old = $stmt->fetch();
if (!$old) throw new Exception('分類不存在');
// 2. 取得新父資訊
$newPath = '0';
$newDepth = 0;
if ($newPid !== 0) {
$stmt = $pdo->prepare('SELECT path, depth FROM category_path WHERE id = ?');
$stmt->execute([$newPid]);
$parent = $stmt->fetch();
if (!$parent) throw new Exception('新父分類不存在');
$newPath = $parent['path'] . '-' . $newPid;
$newDepth = $parent['depth'] + 1;
}
// 3. 計算 path 差異
$oldPrefix = $old['path'] . '-' . $moveId;
$newPrefix = $newPath . '-' . $moveId;
$depthDiff = $newDepth - $old['depth'];
// 4. 批次更新自己及後代
$pdo->prepare('UPDATE category_path SET path = REPLACE(path, ?, ?), depth = depth + ? WHERE path LIKE ? OR id = ?')
->execute([$oldPrefix, $newPrefix, $depthDiff, $oldPrefix . '%', $moveId]);
$pdo->commit();
} catch (Throwable $e) {
$pdo->rollBack();
throw $e;
}
}
| 維度 | Adjacency List (遞歸組裝) | Materialized Path | Closure Table (關係閉包) |
|---|---|---|---|
| 查詢子樹效能 | 需 PHP 組裝 / 多次查詢 | 單一 SQL (LIKE 索引) | 單一 SQL (JOIN 索引) |
| 查詢祖先路徑 | 遞歸查詢 / 多次 SQL | 解析 path 字串 | 單一 SQL |
| 移動節點成本 | 極低 (改 pid) | 高 (更新所有後代 path) | 中 (刪/增關係行) |
| 資料完整性 | 依賴 FK | 路徑可能不一致 | 最強 (FK 约束) |
| 儲存空間 | 最小 | 中 (path 字串) | 最大 (N² 關係行) |
| 適用場景 | 分類 < 5000、頻繁移動 | 分類 < 10萬、查詢多改少 | 嚴格一致性、複雜權限 |
CREATE TABLE `category_closure` (
`ancestor` INT UNSIGNED NOT NULL,
`descendant` INT UNSIGNED NOT NULL,
`depth` TINYINT NOT NULL DEFAULT 0,
PRIMARY KEY (`ancestor`, `descendant`),
INDEX `idx_descendant` (`descendant`)
) ENGINE=InnoDB;
-- 新增節點：插入自己 (depth=0) + 所有祖先關係 (depth+1)
INSERT INTO category_closure (ancestor, descendant, depth)
SELECT ancestor, NEW_ID, depth+1 FROM category_closure WHERE descendant = PARENT_ID
UNION ALL SELECT NEW_ID, NEW_ID, 0;
-- 查詢所有後代：SELECT descendant FROM category_closure WHERE ancestor = ROOT_ID AND depth > 0;
-- 查詢所有祖先：SELECT ancestor FROM category_closure WHERE descendant = NODE_ID AND depth > 0;
-- 移動節點：刪除舊關係 + 插入新關係 (需交易鎖表)
# 生成 10 萬筆測試資料 php artisan db:seed --class=CategorySeeder --count=100000 # 測試查詢時間 time php benchmark.php --method=adjacency --root=1 time php benchmark.php --method=path --root=1 time php benchmark.php --method=closure --root=1 # 監控記憶體 php -d memory_limit=256M benchmark.php
