2-3 树：多路节点与绝对平衡

我最开始接触“2-3 树：多路节点与绝对平衡”时，先遇到的是这个问题：2-3 树第一次看起来不像我熟悉的二叉树，一个节点能放多个键，让我很难想象插入时节点为什么会分裂。我没有继续硬记结论，而是把过程画出来，再用一两个最小例子亲手跑通。这篇留下的，就是那次重新梳理后真正帮我想明白的东西。

2-3 树是一种多路搜索树。一个节点可以是 2-节点（1 个键、2 个孩子）或 3-节点（2 个键、3 个孩子），所有叶子保持在同一深度，因此树始终绝对平衡。

它从哪里来

2-3 树在二十世纪七十年代前后的平衡搜索树研究中形成。它允许一个节点保存一个或两个键，通过节点分裂与合并让所有叶子保持同一深度。理解它，是理解 B 树以及红黑树“用二叉形式编码多路节点”的重要台阶。

节点如何划分区间

2-3 树节点值域和溢出分裂图

图：2-节点、3-节点的值域划分与中间键提升

节点内部的键有序，孩子对应不同值域。查询时先在节点内比较，再进入唯一可能包含目标的子树。

插入的核心是“向上分裂”

新键总是插入叶子。若叶子原本只有一个键，直接形成 3-节点；若已有两个键，临时出现三个键，需要：

将三个键排序。
中间键提升到父节点。
较小和较大的键分成两个子节点。
父节点若也溢出，继续向上分裂。
根节点分裂时创建新根，树高增加 1。

这种增长方式保证所有叶子仍在同一层。它与普通 BST “一路新增单节点”的方式完全不同。

一个完整的插入示例

依次插入 10、20、30、40、50：

2-3 树依次插入 10、20、30、40、50 的过程图

图：叶节点溢出时提升中间键并保持所有叶子等深

提升中间键后，左右节点分别保留较小和较大区间。若父节点也已有两个键，提升会继续触发父分裂，直到根。

查询流程与节点设计

在 3-节点 [a | b] 中：目标小于 a 走左孩子，介于 a 和 b 走中孩子，大于 b 走右孩子，等于任一键则成功。每层只进入一个孩子，因此成本与树高成正比。

节点通常包含：

有序键数组及当前键数。
值数组（若实现 Map）。
最多比键数多一个的孩子数组。
是否为叶子的信息。

插入临时溢出时可能需要容纳第三个键和第四个孩子；也可以让递归返回“提升键 + 左右节点”的分裂结果，避免节点长期处于非法状态。

下面是一个强调结构而非完整业务能力的 Java 节点定义：

final class Node<K extends Comparable<K>> {
    final List<K> keys = new ArrayList<>(2);
    final List<Node<K>> children = new ArrayList<>(3);

    boolean isLeaf() {
        return children.isEmpty();
    }

    int childIndex(K key) {
        int i = 0;
        while (i < keys.size() && key.compareTo(keys.get(i)) > 0) {
            i++;
        }
        return i;
    }
}

record Split<K extends Comparable<K>>(
        K promoted,
        Node<K> left,
        Node<K> right) {}

递归插入可以返回两种结果：没有分裂，或产生一个 Split。父节点收到分裂结果后，把 promoted 插入对应位置，并用 left/right 替换原孩子。若父节点也溢出，就继续向上传递新的 Split。这种返回值设计比在递归中同时修改父、祖父更容易验证。

重复键必须提前定义语义：Set 可以忽略重复键，Map 可以覆盖旧值，也可以让同一个键关联一组值。若不定义，插入逻辑可能把相等键错误送入孩子，破坏搜索唯一性。

为什么值得学习

2-3 树直接实现代码较复杂，但它是理解红黑树和 B 树的重要桥梁。红黑树可以看作把 3-节点用一条红色连接编码进二叉树；B 树则把一个节点可容纳的键数量继续扩大，以减少磁盘页访问次数。

复杂度

树高始终为 O(log n)，查询、插入和删除也保持 O(log n)。节点内部键数量固定时比较成本可视为常数。

删除比插入更复杂：从只有一个键的叶子删除会造成下溢，需要向兄弟借键，或与兄弟及父键合并，修复可能继续向上。理解时应先掌握插入分裂，再学习删除借位与合并。

若树高为 h，最少键数量出现在所有节点都是 2-节点时，最多键数量出现在所有节点都是 3-节点时，因此叶子规模介于 2^h 与 3^h 的量级之间。反过来，树高始终是对数级。绝对平衡并不代表每个操作没有常数开销：节点内移动键、创建分裂节点和维护父子引用仍需成本。

删除的借位与合并

从 3-节点叶子删除一个键仍是合法 2-节点；从只有一个键的叶子删除则产生下溢。修复选择包括：

邻近兄弟有两个键时，通过父键旋转借一个键。
兄弟也只有一个键时，把兄弟、父分隔键和当前节点合并。
父节点因此下溢时继续向上修复。
根失去最后一个键时，让唯一孩子成为新根，树高减 1。

删除逻辑难点不在比较，而在维护孩子数组、父分隔键与所有叶子同层。完整实现应使用结构化分裂/合并结果，并在每次操作后验证节点键数和深度。

向右兄弟借位时，可以把父分隔键下移到当前节点，再把右兄弟最小键提升到父节点；若是内部节点，还要把右兄弟最左孩子一并转移。向左兄弟借位完全对称。合并时则把父分隔键夹在两个兄弟的键之间，并拼接孩子列表。

2-3 树删除时向兄弟借位和合并的过程图

图：父分隔键参与借位；无法借位时与兄弟合并并向上修复

如果当前节点和兄弟都只有一个键，就无法借位，只能合并。合并会让父节点减少一个键；若父也下溢，修复沿路径继续向上。这正是删除比插入更难的根本原因。

不变量验证器应该检查什么

只比较查询结果不足以证明树正确。建议在每次随机插入、删除后递归检查：

非根节点键数只能是 1 或 2。
键严格有序，且所有孩子的键位于父键划分的范围内。
叶节点没有孩子，内部节点孩子数等于键数加一。
所有叶节点深度相同。
统计得到的键总数等于容器记录的 size。

测试可以同时维护一个 TreeSet 作为参照，执行数万次随机操作后比较有序遍历结果。这样能发现仅在多层连续分裂或连续合并时出现的指针错误。

工程视角

内存中的通用有序 Map 通常不直接选 2-3 树，因为红黑树用二叉节点更容易与既有指针结构结合。数据库索引也通常使用阶数更高的 B+ 树，而不是每节点最多两个键的 2-3 树。它的主要价值是建立多路平衡树的心智模型。

B+ 树把记录或记录指针主要放在叶子，并把叶子连接起来，范围扫描更高效；内部节点只负责导航，一页能容纳更多键，树高更低。2-3 树是理解这些机制的最小模型。

在磁盘或 SSD 索引中，一次随机页访问通常比节点内比较昂贵得多，所以会让一个节点接近页大小并容纳大量键，形成高阶 B 树或 B+ 树。2-3 树每个节点最多两个键，虽然逻辑清晰，却没有充分利用页内空间，因此更适合作为教学模型。

并发场景还需要解决读写期间的节点分裂、锁范围和版本可见性。数据库不会只把课堂版树加一把全局锁就结束，而会结合页锁、闩锁耦合、写前日志和崩溃恢复。理解数据结构不变量，是继续理解这些工程机制的前提。

测试清单

叶节点从 2-节点变成 3-节点。
叶分裂、父分裂和根分裂。
连续递增与随机插入后所有叶子深度相同。
每个节点键有序，孩子区间正确。
删除时向左或右兄弟借位、合并和根降高。

自测

2-节点和 3-节点分别划分几个值域？
为什么分裂时提升中间键？
根分裂后树高怎样变化？
2-3 树与红黑树、B 树有什么关系？