PHP 无限分类 (左值右值/嵌套集合模型) 完整实现：增删移树形结构

前言

传统递归查询 (Adjacency List) 在深层树性能差。嵌套集合模型 用 lft (左值) 和 rgt (右值) 编码树结构，实现单次查询获取整棵子树、无递归移动/删除节点。本文提供生产级 PHP 实现，含完整 SQL 与类封装。

数据库表结构

CREATE TABLE `category` (
    `id` INT UNSIGNED NOT NULL AUTO_INCREMENT PRIMARY KEY,
    `name` VARCHAR(100) NOT NULL COMMENT '节点名称',
    `lft` INT UNSIGNED NOT NULL DEFAULT 0 COMMENT '左值',
    `rgt` INT UNSIGNED NOT NULL DEFAULT 0 COMMENT '右值',
    `depth` TINYINT UNSIGNED NOT NULL DEFAULT 0 COMMENT '深度 (冗余字段，加速查询)',
    `status` TINYINT NOT NULL DEFAULT 1 COMMENT '1正常 0禁用',
    INDEX `idx_lft` (`lft`),
    INDEX `idx_rgt` (`rgt`),
    INDEX `idx_status` (`status`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4 COMMENT='无限分类-嵌套集合模型';

核心原理

• 根节点：lft=1, rgt=2*N (N=总节点数)
• 子节点区间完全包含在父节点区间内：parent.lft < child.lft < child.rgt < parent.rgt
• 叶子节点：rgt = lft + 1
• 节点后代数：(rgt - lft - 1) / 2

PHP 核心类实现

<?php
/**
 * 嵌套集合模型树操作类
 * 依赖 PDO，建议注入数据库连接
 */
class NestedSetTree
{
    private \PDO $pdo;
    private string $table;

    public function __construct(\PDO $pdo, string $table = 'category')
    {
        $this->pdo = $pdo;
        $this->table = $table;
    }

    // ==================== 查询操作 ====================

    /** 获取完整树 (用于下拉选单、前端树形组件) */
    public function getTree(int $rootId = 0): array
    {
        if ($rootId === 0) {
            $sql = "SELECT * FROM {$this->table} WHERE status=1 ORDER BY lft";
            return $this->pdo->query($sql)->fetchAll(\PDO::FETCH_ASSOC);
        }

        $node = $this->getNode($rootId);
        if (!$node) return [];

        $sql = "SELECT * FROM {$this->table}
                WHERE lft BETWEEN :lft AND :rgt AND status=1
                ORDER BY lft";
        $stmt = $this->pdo->prepare($sql);
        $stmt->execute([':lft' => $node['lft'], ':rgt' => $node['rgt']]);
        return $stmt->fetchAll(\PDO::FETCH_ASSOC);
    }

    /** 获取单个节点 */
    public function getNode(int $id): ?array
    {
        $stmt = $this->pdo->prepare("SELECT * FROM {$this->table} WHERE id = :id");
        $stmt->execute([':id' => $id]);
        return $stmt->fetch(\PDO::FETCH_ASSOC) ?: null;
    }

    /** 获取面包屑导航 (祖先链) */
    public function getAncestors(int $id): array
    {
        $node = $this->getNode($id);
        if (!$node) return [];

        $sql = "SELECT * FROM {$this->table}
                WHERE lft < :lft AND rgt > :rgt AND status=1
                ORDER BY lft";
        $stmt = $this->pdo->prepare($sql);
        $stmt->execute([':lft' => $node['lft'], ':rgt' => $node['rgt']]);
        return $stmt->fetchAll(\PDO::FETCH_ASSOC);
    }

    /** 获取直属子节点 */
    public function getChildren(int $parentId): array
    {
        $parent = $this->getNode($parentId);
        if (!$parent) return [];

        $sql = "SELECT * FROM {$this->table}
                WHERE lft > :lft AND rgt < :rgt AND depth = :depth AND status=1
                ORDER BY lft";
        $stmt = $this->pdo->prepare($sql);
        $stmt->execute([
            ':lft' => $parent['lft'],
            ':rgt' => $parent['rgt'],
            ':depth' => $parent['depth'] + 1,
        ]);
        return $stmt->fetchAll(\PDO::FETCH_ASSOC);
    }

    // ==================== 写操作 (均使用事务) ====================

    /** 在指定父节点下新增子节点 (作为最后一个子节点) */
    public function insertNode(int $parentId, string $name): int
    {
        $this->pdo->beginTransaction();
        try {
            $parent = $this->getNode($parentId);
            if (!$parent) throw new \Exception("父节点不存在: $parentId");

            $newLft = $parent['rgt'];
            $newRgt = $parent['rft'] + 1;
            $newDepth = $parent['depth'] + 1;

            // 1. 空出位置：所有 lft/rgt >= newLft 的节点 +2
            $this->shiftRL($newLft, 2);

            // 2. 插入新节点
            $stmt = $this->pdo->prepare("INSERT INTO {$this->table} (name, lft, rgt, depth) VALUES (:name, :lft, :rgt, :depth)");
            $stmt->execute([
                ':name' => $name,
                ':lft' => $newLft,
                ':rgt' => $newRgt,
                ':depth' => $newDepth,
            ]);
            $newId = (int)$this->pdo->lastInsertId();

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

    /** 移动整个子树到新父节点下 (作为最后一个子节点) */
    public function moveSubtree(int $sourceId, int $targetParentId): bool
    {
        if ($sourceId === $targetParentId) return false;
        // 防止移动到自己的后代中
        if ($this->isDescendant($targetParentId, $sourceId)) {
            throw new \Exception('不能将节点移动到其自身的子孙节点下');
        }

        $this->pdo->beginTransaction();
        try {
            $source = $this->getNode($sourceId);
            $target = $this->getNode($targetParentId);
            if (!$source || !$target) throw new \Exception('节点不存在');

            $treeWidth = $source['rgt'] - $source['lft'] + 1;
            $targetRgt = $target['rgt'];

            // 1. 从原位置删除 (逻辑上腾出空间)
            $this->shiftRL($source['rgt'] + 1, -$treeWidth);
            $this->shiftRL($source['lft'], -$treeWidth);

            // 2. 计算新位置偏移量
            $shift = $targetRgt - $source['lft'];
            if ($shift > 0) $shift -= $treeWidth; // 移动方向修正

            // 3. 在目标位置空出空间
            $this->shiftRL($targetRgt, $treeWidth);

            // 4. 更新移动节点及其所有后代的 lft/rgt/depth
            $depthDiff = ($target['depth'] + 1) - $source['depth'];
            $sql = "UPDATE {$this->table}
                    SET lft = lft + :shift, rgt = rgt + :shift, depth = depth + :depthDiff
                    WHERE lft >= :oldLft AND rgt <= :oldRgt";
            $stmt = $this->pdo->prepare($sql);
            $stmt->execute([
                ':shift' => $shift,
                ':depthDiff' => $depthDiff,
                ':oldLft' => $source['lft'],
                ':oldRgt' => $source['rgt'],
            ]);

            $this->pdo->commit();
            return true;
        } catch (\Throwable $e) {
            $this->pdo->rollBack();
            throw $e;
        }
    }

    /** 删除节点及其整个子树 */
    public function deleteSubtree(int $id): int
    {
        $this->pdo->beginTransaction();
        try {
            $node = $this->getNode($id);
            if (!$node) return 0;

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

            // 1. 删除区间内所有节点
            $stmt = $this->pdo->prepare("DELETE FROM {$this->table} WHERE lft BETWEEN :lft AND :rgt");
            $stmt->execute([':lft' => $node['lft'], ':rgt' => $node['rgt']]);
            $deleted = $stmt->rowCount();

            // 2. 关闭间隙：右侧节点左移
            $this->shiftRL($node['rgt'] + 1, -$treeWidth);

            $this->pdo->commit();
            return $deleted;
        } catch (\Throwable $e) {
            $this->pdo->rollBack();
            throw $e;
        }
    }

    /** 仅删除单个节点，子节点提升为父节点的子节点 */
    public function deleteNode(int $id): int
    {
        $this->pdo->beginTransaction();
        try {
            $node = $this->getNode($id);
            if (!$node) return 0;

            // 1. 子节点上移一层 (lft/rgt -1, depth -1)
            $sql = "UPDATE {$this->table}
                    SET lft = lft - 1, rgt = rgt - 1, depth = depth - 1
                    WHERE lft > :lft AND rgt < :rgt";
            $stmt = $this->pdo->prepare($sql);
            $stmt->execute([':lft' => $node['lft'], ':rgt' => $node['rgt']]);

            // 2. 删除节点本身
            $stmt = $this->pdo->prepare("DELETE FROM {$this->table} WHERE id = :id");
            $stmt->execute([':id' => $id]);

            // 3. 关闭间隙 (右侧节点 -2)
            $this->shiftRL($node['rgt'] + 1, -2);

            $this->pdo->commit();
            return 1;
        } catch (\Throwable $e) {
            $this->pdo->rollBack();
            throw $e;
        }
    }

    // ==================== 私有辅助方法 ====================

    /** 批量偏移 lft/rgt 值 */
    private function shiftRL(int $boundary, int $offset): void
    {
        if ($offset === 0) return;
        $sign = $offset > 0 ? '+' : '';
        $sql = "UPDATE {$this->table} SET lft = lft {$sign}{$offset}, rgt = rgt {$sign}{$offset} WHERE lft >= :boundary";
        $stmt = $this->pdo->prepare($sql);
        $stmt->execute([':boundary' => $boundary]);
    }

    /** 判断 $descendant 是否为 $ancestor 的后代 */
    private function isDescendant(int $ancestorId, int $descendantId): bool
    {
        $anc = $this->getNode($ancestorId);
        $desc = $this->getNode($descendantId);
        if (!$anc || !$desc) return false;
        return $desc['lft'] > $anc['lft'] && $desc['rgt'] < $anc['rgt'];
    }
}

使用示例

<?php
$pdo = new PDO('mysql:host=localhost;dbname=test;charset=utf8mb4', 'user', 'pass', [
    PDO::ATTR_ERRMODE => PDO::ERRMODE_EXCEPTION,
    PDO::ATTR_DEFAULT_FETCH_MODE => PDO::FETCH_ASSOC,
]);

$tree = new NestedSetTree($pdo);

// 初始化根节点 (仅首次)
$root = $tree->getNode(1);
if (!$root) {
    $pdo->exec("INSERT INTO category (name, lft, rgt, depth) VALUES ('根分类', 1, 2, 0)");
}

// 增
$cat1 = $tree->insertNode(1, '电子产品'); // id=2
$cat2 = $tree->insertNode($cat1, '手机'); // id=3
$tree->insertNode($cat2, 'iPhone');
$tree->insertNode($cat2, 'Android');

// 查
$all = $tree->getTree(); // 全树
$children = $tree->getChildren($cat1); // 直属子节点
$ancestors = $tree->getAncestors($cat2); // 面包屑

// 移
$tree->moveSubtree($cat2, $cat1); // 无效操作示例
$tree->moveSubtree(3, 1); // 将手机移到根分类下

// 删
$tree->deleteSubtree($cat1); // 删除电子产品及所有子分类
$tree->deleteNode(3); // 仅删除手机节点，子节点提升

性能与注意事项

高并发写入场景建议：

1. 改用 Closure Table (闭包表) 模型，写入只需插入祖先关系记录，无大范围更新。
2. 或采用 物化路径 (path = '1/5/12/') + 触发器/应用层维护。
3. 嵌套集合适合读多写少：商品分类、CMS 栏目、组织架构 (变更频率低)。

结语

嵌套集合模型以 lft/rgt 优雅解决树形查询性能痛点，写操作虽需大范围更新但逻辑清晰。配合事务与 PDO 参数绑定，上述类可直接用于中小型项目。大规模高频写入场景请评估 Closure Table 方案。