separator · 叶链 · 范围扫描 · 覆盖索引

B+ tree：数据下沉到叶子

B-tree 把 key 与它对应的数据一起存在节点里，无论这个节点在哪一层。B+ tree 改一条：数据只存在叶子，内部节点的 key 退化成纯粹的路标，同时给叶子之间加一条链表。

改动看起来很小，后果有三项，且都指向同一类负载——数据库索引。

1 · 路标不是数据

定义 1.1（B+ tree） 阶 $m$ 的 B+ tree 与 B-tree 的三处差别：

全部 $(\text{key}, \text{value})$ 对存在叶子层；内部节点只存 key 与孩子指针。
内部节点的 key 是 separator：它把左右两棵子树分开，语义是「小于它的走左边」。separator 不必是任何实际存在的 key。
每个叶子有一个指向右邻叶子的指针，全体叶子按 key 升序串成一条链。

分裂规则随之分岔。叶子溢出时，右半的首 key「复制」一份上去当 separator，数据本身留在叶子里；内部节点溢出时与 B-tree 相同，中位 key「移动」上去。「复制」与「移动」的区别正是「路标不是数据」这句话的实现形态。

图 1-1 · 同一串 key 同时喂给 B-tree 与 B+ tree，上下并排。B+ tree 的叶子之间有虚线的链表指针，内部节点的 key 在叶子里会重复出现一次。可逐个插入观察两者的分裂时机差异。

separator 允许与数据脱钩，带来一项直接的简化：删除时不用管内部节点。被删的 key 若恰好等于某个 separator，那个 separator 留着不动仍然正确——它只是说「小于它的走左边」，而这句话在 key 消失后依然成立。B-tree 没有这项自由，它必须用前驱顶替（见删除的三种修复 §3）。实测 $m = 5$ 装 1000 个 key 再删光，B-tree 做了 296 次前驱顶替，B+ tree 是 0 次。

2 · 同一页装得下更多路标

内部节点不存 value，这一点在页算术上直接兑现。设 key 8 字节、指针 6 字节、value 120 字节：

	一个 entry 占用	16 KB 页装得下
B-tree 内部节点	$8 + 6 + 120 = 134$ B	123 个孩子
B+ tree 内部节点	$8 + 6 = 14$ B	1170 个孩子
B+ tree 叶节点	$8 + 120 = 128$ B	128 条记录

扇出从 123 变成 1170，9.5 倍。树高的差别没有 9.5 倍那么夸张（对数），但足够跨过一整层：1000 万条记录在扇出 123 下需要 4 层，在 1170 下需要 3 层。一次点查省一次页读，四分之一的延迟。

B-tree 在这张表里还有一项优势没算：它的内部节点里就有数据，运气好的话点查不必走到叶子。但这项优势的期望值很低——记录几乎全部落在叶子层，因为叶子层占了整棵树的绝大部分节点。实测 $m = 256$ 、100 万条记录的 B+ tree 有 5584 个节点，其中 5551 个是叶子，占 99.4%。「提前命中」的概率不到 1%。

3 · 叶链把范围扫描变成顺序读

范围查询 WHERE k BETWEEN lo AND hi 是索引的第二大用途，仅次于点查。两种树在这件事上的差距远大于点查。

B-tree 要做一次带剪枝的中序遍历：进入一个节点，取出落在区间里的 key，再下沉到相邻的孩子，取完再回到父节点取下一个 key。访问顺序在层与层之间反复上下跳，每一次都是一次随机读。

B+ tree 只需一次定位加一次顺序走：自根下沉找到含 lo 的叶子，然后沿 next 指针一直走到超出 hi。

图 3-1 · 范围扫描的页读构成，蓝段是自根而下的随机读、绿段是沿叶链的顺序读。可改阶 m 与区间宽度，观察两者的总页读几乎相同而随机读部分差出两个数量级。

10 万条记录、扫 [30000, 40000] 共 10001 条的实测：

阶 $m$	B+ 总页读	其中随机读	其中顺序读	B-tree 总页读（全随机）
8	2507	7	2500	2507
32	629	4	625	629
128	160	3	157	159

警示 · 本页原先写的是「B+ tree 的范围扫描页读次数少于 B-tree」。实测推翻了： $m = 8$ 与 $m = 32$ 两档完全相等， $m = 128$ 那一档 B+ 反而多读一页（160 对 159）。B-tree 的内部节点里也存数据，扫同样的区间它需要的叶子更少，两笔正好抵掉。真实的差别不在页数，而在这些页是哪一种：B+ 那 2507 次里只有 7 次是随机读，剩下 2500 次是物理相邻的顺序读，可以被预读、可以合并成大 I/O、在机械盘上不用寻道；B-tree 的 2507 次全部是随机读。改的是正文，测试里那条断言也跟着改成了「B+ 的非下降页读全是顺序的」，而不是原来那句「总页读更少」。

顺序读与随机读的单价差多少，取决于设备与预读窗口。NVMe 上是数倍，机械盘上是两个数量级。这就是「数据库索引选 B+ 不选 B」的第二条理由，且在很多负载下比第一条（扇出）更重要。

4 · 聚簇索引与二级索引

数据全在叶子这件事还改变了「索引与数据的关系」。

clustered index 把整行数据直接放在 B+ tree 的叶子里，索引就是表本身。InnoDB 的主键索引即是如此，一张表有且只有一个聚簇索引。二级索引则是另一棵 B+ tree，它的叶子里存的不是行，而是主键值。

于是通过二级索引查一整行要走两棵树：先在二级索引里定位到主键，再拿主键去聚簇索引里取行。两棵树都是 3 层的话，一次查询 6 次页读而不是 3 次。这个动作叫回表。

避开回表的办法是让二级索引自己就装得下查询需要的全部列，即 covering index：查询只碰索引里已有的列，第二棵树不用走。代价是索引变宽、扇出下降、写入时要维护更多字节。

PostgreSQL 的默认组织方式不同：它的表是 heap，索引的叶子存的是行的物理位置 ctid，所有索引都是「二级」的。这意味着 PostgreSQL 没有免费的聚簇查询，但也没有「主键变更要重排整张表」的问题。两种设计的取舍在页末参考文献 [2] 与 [3] 里各有一手说明。

5 · 参考文献

Comer, D. (1979). The ubiquitous B-tree. ACM Computing Surveys, 11(2), 121–137.
Oracle Corporation. MySQL 8.4 Reference Manual, §17.6.2: Indexes（含 clustered index 与 secondary index 的物理结构）.
PostgreSQL Global Development Group. PostgreSQL Documentation, §64.2: B-Tree Indexes.
Graefe, G. (2011). Modern B-tree techniques. Foundations and Trends in Databases, 3(4), 203–402.