您现在的位置：程式碼之家 >> 編程語言 > >> 網頁程式設計 >> PHP 程式設計 >> PHP 綜合知識

PHP 無限級分類：鄰接列表 vs 巢狀集合模型完整比較與實作

編輯：PHP 綜合知識

無限級分類（樹狀結構）在電商分類、CMS 欄目、組織架構、評論回覆等場景普遍存在。關係型資料庫本質是扁平表格，儲存樹狀資料需特定模型。本文深度比較兩大經典模型：**鄰接列表** 與 **巢狀集合**，並提供 PHP 實作範例。

模型對比總覽

維度	鄰接列表	巢狀集合
表結構	`id, parent_id, name, ...`	`id, name, lft, rgt, depth`
概念	每節點指向父節點	每節點標記左/右邊界，子樹包含在區間內
插入節點	極簡單：指定 parent_id	複雜：需更新所有後續節點 lft/rgt (+2)
移動子樹	簡單：更新 parent_id	複雜：需重新計算受影響區間
刪除子樹	遞歸刪除	單一 DELETE 區間
查詢子孫	遞歸/CTE 多次查詢	單一查詢 `BETWEEN lft AND rgt`
查詢祖先	遞歸向上	單一查詢 `lft < node.lft AND rgt > node.rgt`
查詢直接子節點	`WHERE parent_id = ?`	`WHERE parent_id = ? AND depth = node.depth+1`
適用場景	頻繁寫入、結構變動大	讀多寫少、需高效能讀取整棵樹

模型一：鄰接列表實作

資料表結構

CREATE TABLE categories (
    id INT AUTO_INCREMENT PRIMARY KEY,
    parent_id INT DEFAULT 0,
    name VARCHAR(100) NOT NULL,
    sort_order INT DEFAULT 0,
    created_at TIMESTAMP DEFAULT CURRENT_TIMESTAMP
);

PHP 核心操作類別

<?php
class AdjacencyListTree {
    private $pdo;

    public function __construct(PDO $pdo) { $this->pdo = $pdo; }

    // 新增節點
    public function insert(string $name, int $parentId = 0, int $sort = 0): int {
        $stmt = $this->pdo->prepare('INSERT INTO categories (parent_id, name, sort_order) VALUES (?, ?, ?)');
        $stmt->execute([$parentId, $name, $sort]);
        return (int)$this->pdo->lastInsertId();
    }

    // 取得直接子節點
    public function getChildren(int $parentId): array {
        $stmt = $this->pdo->prepare('SELECT * FROM categories WHERE parent_id = ? ORDER BY sort_order, id');
        $stmt->execute([$parentId]);
        return $stmt->fetchAll(PDO::FETCH_ASSOC);
    }

    // 遞歸建構完整樹陣列 (適合資料量 < 1000)
    public function buildTree(int $parentId = 0): array {
        $children = $this->getChildren($parentId);
        foreach ($children as &$node) {
            $node['children'] = $this->buildTree($node['id']);
        }
        return $children;
    }

    // 遞歸取得所有子孫 ID (含自己)
    public function getDescendantIds(int $nodeId): array {
        $ids = [$nodeId];
        $children = $this->getChildren($nodeId);
        foreach ($children as $child) {
            $ids = array_merge($ids, $this->getDescendantIds($child['id']));
        }
        return $ids;
    }

    // 遞歸取得祖先鏈 (含自己)
    public function getAncestors(int $nodeId): array {
        $path = [];
        $currentId = $nodeId;
        while ($currentId > 0) {
            $stmt = $this->pdo->prepare('SELECT * FROM categories WHERE id = ?');
            $stmt->execute([$currentId]);
            $node = $stmt->fetch(PDO::FETCH_ASSOC);
            if (!$node) break;
            $path[] = $node;
            $currentId = $node['parent_id'];
        }
        return array_reverse($path);
    }

    // 移動節點 (含子樹)
    public function moveNode(int $nodeId, int $newParentId): bool {
        // 防止移動到自己的子孫下
        if (in_array($newParentId, $this->getDescendantIds($nodeId))) return false;
        $stmt = $this->pdo->prepare('UPDATE categories SET parent_id = ? WHERE id = ?');
        return $stmt->execute([$newParentId, $nodeId]);
    }

    // 刪除節點及其子樹
    public function deleteSubtree(int $nodeId): int {
        $ids = $this->getDescendantIds($nodeId);
        $placeholders = implode(',', array_fill(0, count($ids), '?'));
        $stmt = $this->pdo->prepare("DELETE FROM categories WHERE id IN ($placeholders)");
        $stmt->execute($ids);
        return $stmt->rowCount();
    }
}

模型二：巢狀集合實作

資料表結構

CREATE TABLE categories_nested (
    id INT AUTO_INCREMENT PRIMARY KEY,
    name VARCHAR(100) NOT NULL,
    lft INT NOT NULL,
    rgt INT NOT NULL,
    depth INT DEFAULT 0,
    sort_order INT DEFAULT 0
);

核心操作：區間管理

<?php
class NestedSetTree {
    private $pdo;

    public function __construct(PDO $pdo) { $this->pdo = $pdo; }

    // 在父節點下新增子節點 (作為最後一個子節點)
    public function insertChild(int $parentId, string $name, int $sort = 0): int {
        $this->pdo->beginTransaction();
        try {
            // 1. 取得父節點右邊界
            $stmt = $this->pdo->prepare('SELECT rgt, depth FROM categories_nested WHERE id = ?');
            $stmt->execute([$parentId]);
            $parent = $stmt->fetch(PDO::FETCH_ASSOC);
            if (!$parent) throw new Exception("Parent not found");

            $rgt = $parent['rgt'];
            $depth = $parent['depth'] + 1;

            // 2. 空出位置：所有 lft/rgt >= $rgt 的節點 +2
            $this->pdo->prepare('UPDATE categories_nested SET rgt = rgt + 2 WHERE rgt >= ?')->execute([$rgt]);
            $this->pdo->prepare('UPDATE categories_nested SET lft = lft + 2 WHERE lft >= ?')->execute([$rgt]);

            // 3. 插入新節點
            $stmt = $this->pdo->prepare('INSERT INTO categories_nested (name, lft, rgt, depth, sort_order) VALUES (?, ?, ?, ?, ?)');
            $stmt->execute([$name, $rgt, $rgt + 1, $depth, $sort]);
            $newId = (int)$this->pdo->lastInsertId();

            $this->pdo->commit();
            return $newId;
        } catch (Exception $e) {
            $this->pdo->rollBack();
            throw $e;
        }
    }

    // 取得節點的所有子孫 (單一查詢)
    public function getDescendants(int $nodeId): array {
        $stmt = $this->pdo->prepare('SELECT * FROM categories_nested WHERE lft > (SELECT lft FROM categories_nested WHERE id = ?) AND rgt < (SELECT rgt FROM categories_nested WHERE id = ?) ORDER BY lft');
        $stmt->execute([$nodeId, $nodeId]);
        return $stmt->fetchAll(PDO::FETCH_ASSOC);
    }

    // 取得節點的所有祖先 (單一查詢)
    public function getAncestors(int $nodeId): array {
        $stmt = $this->pdo->prepare('SELECT * FROM categories_nested WHERE lft < (SELECT lft FROM categories_nested WHERE id = ?) AND rgt > (SELECT rgt FROM categories_nested WHERE id = ?) ORDER BY lft');
        $stmt->execute([$nodeId, $nodeId]);
        return $stmt->fetchAll(PDO::FETCH_ASSOC);
    }

    // 取得直接子節點
    public function getChildren(int $nodeId): array {
        $stmt = $this->pdo->prepare('SELECT * FROM categories_nested WHERE depth = (SELECT depth FROM categories_nested WHERE id = ?) + 1 AND lft > (SELECT lft FROM categories_nested WHERE id = ?) AND rgt < (SELECT rgt FROM categories_nested WHERE id = ?) ORDER BY sort_order');
        $stmt->execute([$nodeId, $nodeId, $nodeId]);
        return $stmt->fetchAll(PDO::FETCH_ASSOC);
    }

    // 刪除子樹 (單一 DELETE)
    public function deleteSubtree(int $nodeId): int {
        $this->pdo->beginTransaction();
        try {
            $stmt = $this->pdo->prepare('SELECT lft, rgt FROM categories_nested WHERE id = ?');
            $stmt->execute([$nodeId]);
            $node = $stmt->fetch(PDO::FETCH_ASSOC);
            if (!$node) return 0;

            $lft = $node['lft']; $rgt = $node['rgt'];
            $width = $rgt - $lft + 1;

            // 1. 刪除區間內節點
            $this->pdo->prepare('DELETE FROM categories_nested WHERE lft BETWEEN ? AND ?')->execute([$lft, $rgt]);

            // 2. 縮補空隙
            $this->pdo->prepare('UPDATE categories_nested SET rgt = rgt - ? WHERE rgt > ?')->execute([$width, $rgt]);
            $this->pdo->prepare('UPDATE categories_nested SET lft = lft - ? WHERE lft > ?')->execute([$width, $rgt]);

            $this->pdo->commit();
            return 1; // 簡化返回
        } catch (Exception $e) {
            $this->pdo->rollBack();
            throw $e;
        }
    }

    // 移動子樹 (複雜，建議改用 Closure Table)
    public function moveSubtree(int $nodeId, int $newParentId): bool {
        // 實作極其複雜，需計算位移量、更新兩個區間，略
        // 實務上巢狀集合極不適合頻繁移動操作
        throw new Exception("Nested Set 不建議移動子樹，請改用 Closure Table");
    }
}

模型三：Closure Table (關係閉包表) - 現代最佳實踐

結合兩者優點：寫入簡單、讀取高效、支援任意深度查詢、易於移動子樹。

資料表結構

CREATE TABLE categories (
    id INT AUTO_INCREMENT PRIMARY KEY,
    name VARCHAR(100) NOT NULL,
    parent_id INT DEFAULT 0,
    sort_order INT DEFAULT 0
);

CREATE TABLE category_paths (
    ancestor INT NOT NULL,
    descendant INT NOT NULL,
    depth INT NOT NULL,
    PRIMARY KEY (ancestor, descendant),
    FOREIGN KEY (ancestor) REFERENCES categories(id) ON DELETE CASCADE,
    FOREIGN KEY (descendant) REFERENCES categories(id) ON DELETE CASCADE
);

核心操作


class ClosureTableTree {
    private $pdo;

    public function insert(string $name, int $parentId = 0): int {
        $this->pdo->beginTransaction();
        $stmt = $this->pdo->prepare('INSERT INTO categories (parent_id, name) VALUES (?, ?)');
        $stmt->execute([$parentId, $name]);
        $id = (int)$this->pdo->lastInsertId();

        // 自己指向自己 depth=0
        $this->pdo->prepare('INSERT INTO category_paths (ancestor, descendant, depth) VALUES (?, ?, 0)')->execute([$id, $id]);

        // 繼承父節點的所有祖先路徑 depth+1
        if ($parentId > 0) {
            $this->pdo->prepare('
                INSERT INTO category_paths (ancestor, descendant, depth)
                SELECT ancestor, ?, depth + 1 FROM category_paths WHERE descendant = ?
            ')->execute([$id, $parentId]);
        }
        $this->pdo->commit();
        return $id;
    }

    public function getDescendants(int $nodeId): array {
        $stmt = $this->pdo->prepare('
            SELECT c.* FROM categories c
            JOIN category_paths p ON c.id = p.descendant
            WHERE p.ancestor = ? AND p.depth > 0
            ORDER BY p.depth, c.sort_order
        ');
        $stmt->execute([$nodeId]);
        return $stmt->fetchAll(PDO::FETCH_ASSOC);
    }

    public function getAncestors(int $nodeId): array {
        $stmt = $this->pdo->prepare('
            SELECT c.* FROM categories c
            JOIN category_paths p ON c.id = p.ancestor
            WHERE p.descendant = ? AND p.depth > 0
            ORDER BY p.depth DESC
        ');
        $stmt->execute([$nodeId]);
        return $stmt->fetchAll(PDO::FETCH_ASSOC);
    }

    public function moveNode(int $nodeId, int $newParentId): bool {
        // 1. 取得舊父路徑與新父路徑
        // 2. 刪除舊路徑、插入新路徑 (單一 SQL 可完成)
        // 詳見 "Moving Subtrees in Closure Table" 經典演算法
        return true; // 略
    }
}

選型決策樹

資料量 < 1000、結構極少變動 → 鄰接列表 + 遞歸 PHP 組裝 最簡單
讀多寫少、需高效能整樹讀取、不移動節點 → 巢狀集合
頻繁增刪改移、需 ACID、資料量大 → Closure Table (推薦)
使用 PostgreSQL → 原生支援 ltree 擴展、WITH RECURSIVE CTE 完美解決
使用 MySQL 8.0+ → WITH RECURSIVE CTE 讓鄰接列表查詢祖先/子孫變單一 SQL，大幅降低巢狀集合優勢

MySQL 8.0+ CTE 範例 (鄰接列表查詢所有子孫)

WITH RECURSIVE descendants AS (
    SELECT id, parent_id, name, 0 AS depth FROM categories WHERE id = 5
    UNION ALL
    SELECT c.id, c.parent_id, c.name, d.depth + 1
    FROM categories c JOIN descendants d ON c.parent_id = d.id
)
SELECT * FROM descendants;

現代專案優先考慮 Closure Table 或 MySQL 8.0+ CTE，避免巢狀集合維護複雜度。