PHP 無限級分類樹構建：遞歸與引用法的高效實現

無限級分類（無限極分類）是 CMS、電商、權限系統的基礎數據結構。本文對比 遞歸查詢法、單次查詢+引用構建樹、閉包表 三種主流方案，重點講解「單次查詢+引用法」的 O(N) 線性構建算法，並提供生產級可復用代碼。

數據表結構

CREATE TABLE `category` (
    `id` INT UNSIGNED NOT NULL AUTO_INCREMENT PRIMARY KEY,
    `pid` INT UNSIGNED NOT NULL DEFAULT 0 COMMENT '父ID，0為頂級',
    `name` VARCHAR(50) NOT NULL,
    `sort` INT NOT NULL DEFAULT 0 COMMENT '同級排序',
    `status` TINYINT NOT NULL DEFAULT 1 COMMENT '1啟用 0禁用',
    INDEX `idx_pid_status` (`pid`, `status`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4;

方案一：遞歸查詢（簡單但 N+1 問題嚴重）

<?php
function getChildrenRecursive(int $pid = 0): array
{
    global $pdo;
    $stmt = $pdo->prepare("SELECT * FROM category WHERE pid = ? AND status = 1 ORDER BY sort");
    $stmt->execute([$pid]);
    $rows = $stmt->fetchAll();
    foreach ($rows as &$row) {
        $row['children'] = getChildrenRecursive($row['id']);
    }
    return $rows;
}
// 缺點：層級越深查詢次數越多，10 層即 10 次查詢，極易超時
?>

方案二：單次查詢 + 引用構建樹（推薦，O(N)）

<?php
/**
 * 一次查詢所有數據，利用引用關係在內存中構建樹結構
 * @param array $rows 平坦數組 [['id'=>1,'pid'=>0,'name'=>'A'], ...]
 * @param int $rootPid 根節點 pid
 * @return array 樹結構
 */
function buildTree(array $rows, int $rootPid = 0): array
{
    // 1. 建立 id => node 映射（引用）
    $map = [];
    foreach ($rows as &$row) {
        $row['children'] = []; // 預置空子集
        $map[$row['id']] = &$row; // 關鍵：存儲引用
    }

    $tree = [];
    // 2. 遍歷掛載
    foreach ($rows as &$row) {
        $pid = $row['pid'];
        if ($pid === $rootPid) {
            $tree[] = &$row; // 頂級節點直接放入樹根
        } elseif (isset($map[$pid])) {
            $map[$pid]['children'][] = &$row; // 掛載到父節點
        }
        // else: 孤兒節點（父級不存在或被過濾），可選拋棄或收集
    }
    return $tree;
}

// === 使用示例 ===
$stmt = $pdo->query("SELECT id, pid, name, sort FROM category WHERE status=1 ORDER BY sort");
$flatRows = $stmt->fetchAll();
$categoryTree = buildTree($flatRows);

// 輸出 HTML 多級選單
function renderTree(array $tree, int $depth = 0): string
{
    $html = '
';
    foreach ($tree as $node) {
        $html .= '
' . str_repeat('—', $depth) . htmlspecialchars($node['name']);
        if ($node['children']) {
            $html .= renderTree($node['children'], $depth + 1);
        }
        $html .= '
';
    }
    $html .= '
';
    return $html;
}

echo renderTree($categoryTree);
?>

核心原理解析

1. &$row 獲取引用：`$map[$id] = &$row` 使映射表持有對原數組元素的引用，而非副本。
2. 掛載時同樣用引用：`$map[$pid]['children'][] = &$row` 將子節點引用加入父節點的 children。
3. 最終 $tree 即為樹根：頂級節點引用直接構成返回數組，修改任一節點均反映到樹中。

方案三：閉包表—— 適合頻繁讀取祖先/後代、移動子樹的場景

CREATE TABLE `category_closure` (
    `ancestor` INT UNSIGNED NOT NULL,
    `descendant` INT UNSIGNED NOT NULL,
    `depth` INT UNSIGNED NOT NULL,
    PRIMARY KEY (`ancestor`, `descendant`),
    INDEX `idx_descendant` (`descendant`)
);

-- 移動節點 5 到節點 3 下
-- 1. 刪除 5 及其後代的所有祖先關係
-- 2. 插入新祖先關係：3 的所有祖先 + 3 自身 -> 5 及其後代
-- 可在單事務中完成，讀取祖先/後代極快（單表查詢）

優點：讀取任意節點的所有祖先/後代、子樹移動均為單 SQL。缺點：寫入複雜、存儲空間隨深度增長（N²/2）。

方案對比與選型指南

生產級增強：緩存 + 路徑物化

<?php
class CategoryService
{
    public function getTree(bool $forceRefresh = false): array
    {
        $cacheKey = 'category:tree:v1';
        if (!$forceRefresh && ($tree = Redis::get($cacheKey))) {
            return json_decode($tree, true);
        }

        $rows = DB::table('category')->where('status', 1)->orderBy('sort')->get()->toArray();
        $tree = buildTree($rows);

        Redis::set($cacheKey, json_encode($tree), 'EX', 3600);
        return $tree;
    }

    public function moveNode(int $nodeId, int $newPid): bool
    {
        // 事務中更新 pid、清理緩存、同步閉包表(若用)
        DB::transaction(function() use ($nodeId, $newPid) {
            DB::table('category')->where('id', $nodeId)->update(['pid' => $newPid]);
            // 同步 closure table...
        });
        $this->getTree(true); // 刷新緩存
        return true;
    }
}
?>

「引用構建樹」是 PHP 處理無限級分類的經典範式：一次查詢、線性時間、代碼極簡。配合 Redis 緩存與寫入時失效，可支撐高併發讀取場景。