趁周末时间，我复盘了之前公司课程目录演变过程，这里做个记录，温故而知新。

本文讨论的 MPTT（Modified Preorder Tree Traversal，修改过的先序遍历树） 也被称为嵌套集模型（Nested Set Model） 或左右值模型，是一种在关系型数据库中高效存储和查询树形结构数据的方案。

传统树形结构痛点

回顾当时重构公司内部的在线教育系统时，我们面临着一个棘手的性能瓶颈：随着课程各个层级数据的增长，课程内容的加载成了当时在线教育系统一个绕不开的性能瓶颈。

一个传统的课程目录包含层层嵌套的结构（课程 -> 章节（多级） -> 小节 -> 学习任务）。前端在渲染时，需要一次性获取整棵“课程树”，并在各类业务场景中频繁统计节点的子任务数量。

在初期的架构设计中，我们采用了直觉上最符合人类直觉的邻接表模型，即经典的 id + pid 结构。每个节点只知道自己的“父”是谁。

1
2
3
4
5
6
7
8
-- 传统 PID 课程目录表结构
CREATE TABLE course_container_pid (
    id BIGINT PRIMARY KEY COMMENT '主键ID',
    pid BIGINT NOT NULL DEFAULT 0 COMMENT '父节点ID，0代表根节点',
    name VARCHAR(100) COMMENT '节点名称（如：第一章、课时1）',
    sort INT COMMENT '同级节点排序',
    INDEX idx_pid (pid)
) COMMENT '传统 PID 课程目录表';

在系统运行初期，这种结构表现得十分轻量。然而，随着数据量级逼近千万级别，该模型的劣势彻底暴露：

  • 灾难级的读取性能： 获取完整的嵌套目录时，由于无法预知子孙节点的 ID，必须在应用层使用递归逻辑。深层级的目录会导致 N+1 查询，严重消耗数据库 CPU 资源。
  • 低效的树形统计： 若要统计某一章节下包含多少个底层的学习任务，必须把该章节下的整棵子树全部查出并在内存中遍历计算，无法通过单条 SQL 高效聚合。

寻找关系型数据库中的树形解法

为了解决“读”的危机，我们开始尝试其他的方式来解决这个问题。在查阅了大量关系型数据库存储树形结构的资料，最终决定引入数据库专家 Joe Celko 提出的 MPTT（Modified Preorder Tree Traversal，修改过的先序遍历树）模型，也常被称为左右值树（Nested Set Model）。

MPTT 是一种“降维打击”的方案。它抛弃了只找父的思路，利用深度优先的先序遍历，为树中的每一个节点分配一个连续的左值（lft）和右值（rgt）。当进入一个节点时分配左值，离开节点时分配右值。

为了直观呈现这种关系，如下的 MPTT 坐标系流转图：

1
2
3
4
5
6
7
8
9
                       [1] 课程: 书名 [14]
                                 |
             ----------------------------------------
             |                                      |
        [2] 第一章 [7]                         [8] 第二章 [13]
             |                                      |
      ---------------                        ---------------
      |             |                        |             |
[3] 课时1 [4]  [5] 课时2 [6]           [9] 课时3 [10] [11] 课时4 [12]

MPTT 模型的结构设计主要解决了传统模型必须依赖递归才能查全层级关系的痛点，它确立了一个核心魔法（铁律）：边界包含。即任何子孙节点的 lft 和 rgt，必定被完美包裹在其所有祖先节点的 lft 和 rgt 之间。

混合架构：纯 MPTT 的妥协与改良

原生的 MPTT 虽然在获取整棵树时性能无敌，但在某些特定场景下却显得力不从心。因此，在最终的 CourseContainer 实体设计中，保留了 pid 和 layer（层级），做了一次混合型变种设计：

1
2
3
4
5
6
7
8
9
10
11
-- MPTT 左右值课程容器表结构 (结合了邻接表特性)
CREATE TABLE course_container (
    id BIGINT PRIMARY KEY COMMENT '主键ID',
    rid BIGINT NOT NULL COMMENT 'Root ID，根节点(课程)ID，用于隔离整棵树',
    pid BIGINT NOT NULL DEFAULT 0 COMMENT '冗余的父节点ID，方便直系上下级查询',
    lft INT NOT NULL COMMENT '左值',
    rgt INT NOT NULL COMMENT '右值',
    layer INT NOT NULL COMMENT '层级深度',
    name VARCHAR(100) COMMENT '节点名称',
    INDEX idx_rid_lft_rgt (rid, lft, rgt)
) COMMENT 'MPTT 课程容器表';

这种空间换时间的设计弥补了纯左右值树的短板：

  1. 彻底废弃了用来维持顺序的 sort 字段（同级节点的顺序天然由 lft 大小决定）。
  2. 引入了关键的 rid（Root ID）字段。在多租户、多课程并存的在线教育系统中，rid 是控制数据库锁粒度的核心。

解决方案与实施

在确定使用 MPTT 的树形结构后，课程的增删改查逻辑发生了翻天覆地的变化。以下在实际代码中实现的各个核心方法及其底层 SQL 映射。

极速读取，消灭递归

在 MPTT 模型下，我们彻底抛弃了 Java 层的递归调用。所有的嵌套关系读取都变成了连续区间的数学扫描。

getChildren (拉取任意子树)
利用包裹特性，查出某节点下的所有子孙节点只需一次区间扫描，且结果天然按照 lft 升序排列，即正确的前序遍历顺序。

1
2
3
4
5
6
-- 参数1: rid (根节点ID)
-- 参数2: node.lft (当前节点左值)
-- 参数3: node.rgt (当前节点右值)
SELECT * FROM course_container
WHERE rid = ? AND lft > ? AND rgt < ?
ORDER BY lft ASC;

注意：使用 lft > ? AND rgt < ? 而非 BETWEEN，是为了排除当前节点本身，只获取子孙节点。

getLinealChildren (精准获取直系子节点)
这是混合模型发挥作用的地方。纯 MPTT 获取直系子节点需要复杂的子查询，但通过冗余的 pid 字段，可以轻松实现：

1
2
3
4
5
-- 参数1: rid (根节点ID)
-- 参数2: node.id (当前节点ID，作为父节点)
SELECT * FROM course_container
WHERE rid = ? AND pid = ?
ORDER BY lft ASC;

getLeaves (精准定位底层任务节点)
叶子节点的特征是内部没有任何子节点，因此它的右值必定紧随左值（差值为 1）。

1
2
3
4
5
-- 参数1: rid (根节点ID)
-- 参数2: node.lft (当前节点左值)
-- 参数3: node.rgt (当前节点右值)
SELECT * FROM course_container
WHERE rid = ? AND lft > ? AND rgt < ? AND rgt = lft + 1;

getLeavesCount (底层任务节点数量)
统计某节点下的叶子节点数量，用于显示”包含 X 个学习任务”。

1
2
3
4
5
-- 参数1: rid (根节点ID)
-- 参数2: node.lft (当前节点左值)
-- 参数3: node.rgt (当前节点右值)
SELECT count(1) FROM course_container
WHERE rid = ? AND lft > ? AND rgt < ? AND rgt = lft + 1;

getChildrenCount (子节点总数统计)
利用左右值的差值公式，可以直接在内存中计算出任意节点包含的后代节点总数，彻底免除数据库查询。

1
2
3
// 节点总数 = (右值 - 左值 - 1) / 2
// 原理：每个节点占用 2 个值（左+右），减去自己占用的 2 个值，再除以 2
return (node.getRight() - node.getLeft() - 1) / 2;

getParents (逆向获取祖先路径)
查出当前节点到根节点的完整面包屑导航，只需反向利用包裹关系：祖先节点的左右值必定包裹当前节点。

1
2
3
4
5
6
-- 参数1: rid (根节点ID)
-- 参数2: node.lft (当前节点左值)
-- 参数3: node.rgt (当前节点右值)
SELECT * FROM course_container
WHERE rid = ? AND lft < ? AND rgt > ?
ORDER BY lft ASC;

承受“写放大”的阵痛

MPTT 的读取达到了极致，但也伴随着维护成本的剧增。由于坐标系是连续的，任何节点的变动都会引发空间的重新分配。

addNode / appendNode (节点新增：撑开连续空间)
为了在树中插入新节点，必须把目标位置后续所有节点的左右值都推后 2 个单位，为其”腾出空档”。这里存在严重的写放大，每一次插入都会导致后续大量记录的 UPDATE。

1
2
3
4
5
6
7
8
9
10
11
12
-- 步骤1: 为新节点腾出空间（更新右值）
-- 参数1: rid, 参数2: targetRgt (目标位置的右值)
UPDATE course_container SET rgt = rgt + 2 WHERE rid = ? AND rgt >= ?;

-- 步骤2: 为新节点腾出空间（更新左值）
-- 参数1: rid, 参数2: targetRgt (目标位置的右值)
UPDATE course_container SET lft = lft + 2 WHERE rid = ? AND lft >= ?;

-- 步骤3: 插入新节点
-- 新节点的 lft = targetRgt, rgt = targetRgt + 1
INSERT INTO course_container (rid, pid, lft, rgt, layer, name)
VALUES (?, ?, ?, ?, ?, ?);

deleteNode (节点删除：物理删除与空间缝合)
删除节点时，除了物理删除目标区间内的所有数据，还需要将后续节点的左右值减去被删除的跨度，像拉链一样缝合断裂的数值空间。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
-- 步骤1: 计算被删除子树的跨度（在应用层计算）
-- span = node.rgt - node.lft + 1

-- 步骤2: 删除目标节点及其所有子孙节点
-- 参数1: rid, 参数2: node.lft, 参数3: node.rgt
DELETE FROM course_container
WHERE rid = ? AND lft >= ? AND rgt <= ?;

-- 步骤3: 缝合右侧节点的右值
-- 参数1: rid, 参数2: span (跨度值), 参数3: node.rgt
UPDATE course_container SET rgt = rgt - ? WHERE rid = ? AND rgt > ?;

-- 步骤4: 缝合右侧节点的左值
-- 参数1: rid, 参数2: span (跨度值), 参数3: node.rgt
UPDATE course_container SET lft = lft - ? WHERE rid = ? AND lft > ?;

注意：删除操作会级联删除所有子孙节点，如果需要保留子节点（只删除当前节点），则需要先移动子节点再删除。

MPTT VS 传统 PID

通过前面的分析，我们来进行直观的对比，从查、增、改三种场景分析两种模式的差异。

⚔️ Round 1：查（获取整棵树或子树）

  • 传统 PID：
    除非使用WITH RECURSIVE 这种关系型数据库支持的递归 SQL，否则单条常规 SQL 根本查不出来。这会导致灾难级的读取性能和 N+1 查询问题。

  • MPTT：
    绝对的统治区。因为子孙的左右值必定在祖先的左右值之间，一条极其简单的范围查询瞬间搞定：

    1
    2
    3
    SELECT * FROM course_container
    WHERE rid = ? AND lft > ? AND rgt < ?
    ORDER BY lft ASC;

    胜者：MPTT（赢得毫无悬念）

⚔️ Round 2：增（新增节点）

  • 传统 PID：
    简单粗暴

    1
    INSERT INTO course_container_pid (name, pid) VALUES ('新节点', 2);

  • MPTT：
    繁琐且危险。要在树中间硬生生塞入一个节点，你必须给它腾出“数值空间”。这意味着新节点右侧所有节点的 lft 和 rgt 都要加上跨度。

    1
    2
    3
    UPDATE course_container SET rgt = rgt + 2 WHERE rid = ? AND rgt >= ?;
    UPDATE course_container SET lft = lft + 2 WHERE rid = ? AND lft >= ?;
    INSERT INTO course_container (rid, pid, lft, rgt, layer, ...) VALUES (?, ?, ?, ?, ?, ...);

    在高并发下，这种大范围的 UPDATE 极易引发锁表和死锁。
    胜者：传统 PID

⚔️ Round 3：改（移动节点）

  • 传统 PID：
    依然是优雅的一行代码。因为子节点是跟着当前节点走的，改一下 pid 就完事了。

    1
    UPDATE course_container_pid SET pid = 1 WHERE id = 3;

  • MPTT：
    需要经历：计算跨度 → 闭合原位置空洞 → 开辟新位置空洞 → 填入子树并加上偏移量。这通常需要在一个事务里执行 5-7 条 SQL，极其消耗性能。

    1
    2
    3
    4
    5
    6
    7
    8
    -- 伪代码流程（实际实现需要处理边界情况和锁机制）：
    -- 1. 锁定源子树和目标位置
    -- 2. 计算源子树跨度 span = srcRgt - srcLft + 1
    -- 3. 临时将源子树的左右值设为负数（避免后续更新影响）
    -- 4. 闭合原位置空洞（类似 deleteNode 的缝合操作）
    -- 5. 在目标位置腾出空间（类似 addNode 的撑开操作）
    -- 6. 将源子树移动到新位置，并加上偏移量
    -- 7. 释放锁

    胜者：传统 PID

对比

维度 传统 PID (邻接表) MPTT (预排序遍历树)
查询整棵树/子树 复杂，性能较差 极简，性能极高
查询祖先路径 复杂，性能较差 极简，性能极高
查询子节点数量 需要 COUNT 查询 O(1) 内存计算
插入单节点 极简 复杂，引发大范围锁表
移动节点/子树 极简 极度复杂，严重影响并发写入
删除节点/子树 简单（需递归删子节点） 复杂，需缝合空间

其他树形方案对比

除了 MPTT 和传统 PID，关系型数据库中还有其他几种常见的树形结构存储方案：

方案 核心思想 优点 缺点 适用场景
Closure Table 单独建表存储所有祖先-后代关系 所有操作都简单，支持复杂查询 空间占用大（O(n²)） 关系查询频繁、写入较少
Path Enumeration 存储完整路径如 /1/4/7/ 查询祖先极其简单 路径长度受限，移动节点需更新所有后代 层级固定、不常移动
Materialized Path 类似 Path，用数组或编码 比 Path 更灵活 实现复杂 需要灵活的层级管理

选型建议：如果读远多于写，且需要频繁查询整树/子树，MPTT 是最佳选择；如果写入频繁或需要频繁移动节点，传统 PID 配合 WITH RECURSIVE 可能更合适。

复盘与反思

将课程目录从传统的 PID 模型重构为 MPTT 左右值模型，本质上是一次**“用高昂的写入计算和批量更新成本，换取读取时极致性能”**的工程妥协。

课程结构的调整不仅暴露了 MPTT 在并发写入时的致命软肋，还增加了维护 pid、layer 等冗余字段的同步成本。为此，在生产环境中确立了两条强制底线：

  1. 确定更新范围： 利用 rid（课程 Root ID）进行分区隔离。每一次 UPDATE 都强制附带 WHERE rid = ?，确保一门课程的目录更新，绝对不会引起全表的锁升级冲突。
  2. 强制分布式锁机制： 在执行 addNode、deleteNode、appendNode 等写入操作时，必须施加分布式排他锁。在并发环境下，左右值计算一旦出现错位，整棵树的数据结构将永久性崩塌，所以必须串行化写入。

MPTT 模型仅适用于典型的读多写少场景。在后续的演进中，我们在后台异步预加载热点课程的树形 JSON，从而进一步降低关系型数据库的承载压力，实现更极致的接口响应。

最后，虽然 MPTT 的理论很优秀，但是在我们实践下来还是遇到了不少挑战（特别是增加了增、删、改的复杂度），不过最终都得到了完善的解决。根据当时的场景，为了追求极致的读性能，这一切都是值得的。

总结

MPTT 适用场景：

  • 读多写少（如：内容管理、目录结构、评论系统）
  • 需要频繁查询整棵树或子树
  • 需要快速统计节点数量
  • 层级相对固定，节点移动不频繁

MPTT 不适用场景：

  • 写入频繁的实时系统
  • 需要频繁移动节点的场景
  • 并发写入要求高的系统（除非有完善的锁机制）

没有最好的模型，只有最合适的选择。