阶 m · split · 中位 key 上提

B-tree 的分裂：从下往上长高

B-tree 的定义看起来有四五条，实际上只有一条是规则，其余都是那条规则的后果。这条规则是：节点装不下就一分为二，把中位 key 交给父节点。本页从约束的形状讲到分裂的时机，再讲为什么树高只能从根往上长。

1 · 阶 m 与三条约束

定义 1.1（阶 $m$ 的 B-tree） 一棵阶为 $m$ 的 B-tree 满足：

每个节点至多 $m - 1$ 个 key、至多 $m$ 个孩子；
除根以外，每个节点至少 $\lceil m/2 \rceil - 1$ 个 key；根若非叶则至少 1 个 key；
内部节点的孩子数恒等于 key 数加一，节点内 key 严格升序；
所有叶子处在同一深度。

$m = 5$ 时 key 数落在 2 到 4； $m = 100$ 时落在 49 到 99。下限是上限的一半，这个比例不是任选的：它保证合并两个下限节点（各 $\lceil m/2 \rceil - 1$ 个 key）加上父节点降下来的一个分界 key，恰好不超过上限 $m - 1$ 。删除时的合并因此永远合法（见删除的三种修复 §2）。

「所有叶子同深」是最强的一条，也是 B-tree 与二叉查找树最本质的分野。二叉查找树的平衡靠旋转维持，旋转会改变某些叶子的深度；B-tree 从不旋转，它只做分裂与合并，而这两个动作都不改变任何叶子的深度差：分裂横向加宽一层，合并横向收窄一层，唯一改变深度的时刻是根本身分裂或被掏空。

2 · 溢出时的一刀两断

插入的定位过程与二叉查找树没有区别：从根开始，在节点内找到 key 该落进哪个孩子的区间，下沉一层，直到叶子。key 写进叶子的正确位置，插入本身就完成了。

问题只出在叶子已经有 $m - 1$ 个 key 的时候。

溢出节点的 key 序列为 $k_0 < k_1 < \dots < k_{m-1}$ （共 $m$ 个，超出上限一个），取 $j = \lfloor m/2 \rfloor$ ：

左半 $k_0, \dots, k_{j-1}$ 留在原节点；
右半 $k_{j+1}, \dots, k_{m-1}$ 移入一个新建的兄弟节点；
中位 key $k_j$ 上提到父节点，成为这两个节点之间的分界。

若节点非叶，孩子按同一刀口切开：前 $j+1$ 个留下，其余给新节点。

图 2-1 · 阶 m 的 B-tree 单步插入。蓝框是本步正在读的节点，绿框是刚新建的节点，左侧文字是引擎记下的这一步在做什么。可改阶 m 与插入序列，逐步观察分裂如何沿路径向上传播。

上提之后父节点也可能溢出，于是同一次插入里可以连续发生多次分裂。 $m = 3$ 顺序插入 1 到 7 的实测轨迹，七次插入总共四次分裂：

插入	发生了什么	插完的树高
1, 2	直接写进根	1
3	根溢出，分裂，中位 key 2 上提，新建根	2
4	直接写进叶	2
5	叶溢出，分裂，中位 key 4 上提到根	2
6	直接写进叶	2
7	叶溢出，中位 key 6 上提；根随之溢出，中位 key 4 上提，新建根	3

最后一行是一次插入触发两次分裂。这也说明单次插入的最坏代价是 $O(h)$ 次分裂而不是一次。摊还下来分裂次数远小于插入次数（ $m = 5$ 装 1000 个 key 只有 365 次分裂），但尾延迟由 $h$ 决定。

3 · 树只从根往上长

分裂把一个节点变成两个，key 总数不变，深度也不变——除了一种情况：溢出的节点是根，它没有父可以接收中位 key。此时新建一个只含这一个 key 的根，原根与新兄弟成为它的两个孩子，整棵树的深度加一。

图 3-1 · 随插入条数增长的树高与节点数，竖线标出发生根分裂的那次插入。可改阶 m 与插入顺序（顺序 / 随机）观察树高的阶梯形状。

这个机制有两项后果。其一，B-tree 是自底向上长高的：新层永远加在顶上，叶子层始终是同一层，所以「所有叶子同深」自动维持，不需要任何额外的修复动作。其二，树高的增长十分稀疏。 $m = 5$ 装 1000 个 key 的实测：365 次分裂里只有 4 次是根分裂，树高 5、节点 370。装到 100 万条、 $m = 256$ 时树高 3，意味着从空树到百万条的整个过程里，根分裂只发生过两次。

警示 · 本系列的引擎给每一步操作记一条轨迹供 lab 单步播放，而记轨迹的做法是把整棵树深拷贝一份存进这一步的 after 字段。写完测试才发现这让批量灌数据变成了 $O(n^2)$ ： $m = 32$ 灌 20000 个 key，不记轨迹 4 到 8 ms，每步记快照约 1.0 秒——两个数量级，vitest 直接超时。修法是给 Tree 加一个 trace 开关，insertAll 灌之前关掉、灌完恢复。可视化用的数据结构与批量计算用的数据结构，代价模型正好相反——前者要每一步的完整状态，后者只要最终状态。同一份代码想同时服务两者，就得把「记不记」做成参数。

4 · 阶的选择与节点内的搬移

阶 $m$ 在实现里通常不是直接给的常数，而是由页大小除出来（见页与扇出的算术 §1）。但即使页大小固定， $m$ 也还有一项与树高无关的代价：节点内的搬移量。

插入一个 key 要在节点内腾出位置，平均挪动一半的 entry。 $m = 1170$ 时平均挪 585 个 entry；分裂时要把右半整块搬进新节点，又是约 $m/2$ 个。这些都是页内的内存操作，与页读比起来单价极低，但它们随 $m$ 线性增长，而树高只随 $\log m$ 递减。 $m$ 大到某个点之后，页内搬移的总量会超过省下来的那一次页读，具体的临界点取决于设备延迟与 CPU，不是一个普适常数。

真实实现还会绕开一部分搬移。PostgreSQL 的页内布局把 key 与一张 line pointer 数组分开存，插入时只在指针数组里挪位置，key 本体追加在页尾；InnoDB 的页里 record 之间用单向链表串联，插入只改两个指针。两种做法都把「挪一半 entry」降成了「挪一半指针」或「改两个指针」。

5 · 参考文献

Bayer, R., & McCreight, E. (1972). Organization and maintenance of large ordered indices. Acta Informatica, 1(3), 173–189.
Comer, D. (1979). The ubiquitous B-tree. ACM Computing Surveys, 11(2), 121–137.
Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.), Chapter 18: B-Trees. MIT Press.
Graefe, G. (2011). Modern B-tree techniques. Foundations and Trends in Databases, 3(4), 203–402.