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

PHP 無限分類算法比較：遞歸、Path 路徑與左右值模型

編輯：PHP 相關知識

三大主流方案對比

維度	遞歸查詢 (Adjacency List)	Path 路徑 (Materialized Path)	左右值 (Nested Set)
表結構	id, parent_id, name	id, parent_id, name, path	id, name, lft, rgt
查詢子樹	多次查詢/遞歸 PHP	單查詢 `WHERE path LIKE '%,1,%'`	單查詢 `WHERE lft>2 AND rgt<11`
查詢祖先	遞歸向上	單查詢 `WHERE FIND_IN_SET(id, REPLACE(path,',',','))`	單查詢 `WHERE lft<2 AND rgt>11`
插入節點	簡單	簡單 (path = parent.path + id + ',')	複雜 (需更新所有後續 lft/rgt +2)
移動子樹	簡單 (改 parent_id)	中等 (批量更新 path 前綴)	極其複雜 (需重算大量區間)
刪除子樹	遞歸刪除	單查詢 `DELETE WHERE path LIKE '%,3,%'`	單查詢但需修復間隙
適合場景	層級淺、變動頻繁	讀多寫少、層級深、需完整路徑	極少變動、頻繁讀取子樹/祖先

Path 路徑模型實現細節 (推薦通用)

// 表結構
CREATE TABLE categories (
    id INT UNSIGNED AUTO_INCREMENT PRIMARY KEY,
    parent_id INT UNSIGNED DEFAULT 0,
    name VARCHAR(100) NOT NULL,
    path VARCHAR(500) NOT NULL COMMENT '如: ,1,5,12,',
    depth TINYINT UNSIGNED DEFAULT 0,
    sort INT DEFAULT 0,
    INDEX idx_path (path),
    INDEX idx_parent (parent_id)
) ENGINE=InnoDB;

// 新增節點
function addNode($parentId, $name) {
    $pdo = getPDO();
    if ($parentId == 0) {
        $path = ',';
        $depth = 0;
    } else {
        $stmt = $pdo->prepare("SELECT path, depth FROM categories WHERE id = ?");
        $stmt->execute([$parentId]);
        $parent = $stmt->fetch();
        $path = $parent['path'] . $parentId . ',';
        $depth = $parent['depth'] + 1;
    }
    $stmt = $pdo->prepare("INSERT INTO categories (parent_id, name, path, depth) VALUES (?, ?, ?, ?)");
    $stmt->execute([$parentId, $name, $path, $depth]);
    $newId = $pdo->lastInsertId();
    // 更新自身 path 包含自己
    $pdo->prepare("UPDATE categories SET path = CONCAT(path, ?, ',') WHERE id = ?")->execute([$newId, $newId]);
    return $newId;
}

// 獲取完整樹 (按 path 排序即為層級順序)
function getTree() {
    return getPDO()->query("SELECT id, name, path, depth FROM categories ORDER BY path")->fetchAll();
}

// 顯示縮進
foreach (getTree() as $node) {
    echo str_repeat('  ', $node['depth']) . htmlspecialchars($node['name']) . "
";
}

// 移動子樹 (將節點 12 移至新父節點 8)
function moveSubtree($nodeId, $newParentId) {
    $pdo = getPDO();
    $pdo->beginTransaction();
    try {
        // 1. 獲取舊路徑前綴與新路徑前綴
        $old = $pdo->prepare("SELECT path FROM categories WHERE id = ?")->execute([$nodeId])->fetchColumn();
        $newParent = $pdo->prepare("SELECT path, id FROM categories WHERE id = ?")->execute([$newParentId])->fetch();
        $newPrefix = $newParent['path'] . $newParent['id'] . ',';
        $depthDiff = substr_count($newPrefix, ',') - substr_count($old, ','); // 深度差

        // 2. 批量更新 path 與 depth
        $pdo->prepare("UPDATE categories SET path = REPLACE(path, ?, ?), depth = depth + ? WHERE path LIKE ?")
            ->execute([$old, $newPrefix, $depthDiff, $old . '%']);
        $pdo->commit();
    } catch (Exception $e) {
        $pdo->rollBack();
        throw $e;
    }
}