page · 扇出 · 树高 · 随机读

页作为代价的单位：树高与比较次数

树 · 遍历、平衡 BST 与前缀 / 度量树里的红黑树、AVL、treap 都在做同一件事：把树高压回 $O(\log n)$ ，免得 BST 退化成链表。三者的分歧只在用什么维持平衡：颜色、高度差、还是随机 priority。扇出恒为 2，从不在议题上。

数据一旦不在内存里，这个默认值就成了最贵的一项。本页把账算清楚：为什么要把节点撑到一整页那么大，以及这样做换掉了什么。

1 · 一次随机读的代价结构

块设备不按字节寻址。存储引擎向设备要数据的最小单位是一个固定大小的块，通常叫做页：ext4 与 NTFS 的默认块是 4 KB，PostgreSQL 的页是 8 KB，InnoDB 是 16 KB。读一页里的 8 个字节与读满这一页 16384 个字节，落到设备上是同一次请求。

这条性质把代价函数改成了阶梯形。一次访问的开销由两部分组成：寻址与排队的固定开销，以及传输字节数的线性开销。在页这个粒度上，第一项完全压倒第二项——NVMe SSD 的随机读延迟在 100 微秒量级，而 4 KB 的传输在同一设备上只需几微秒；机械盘的差距更极端，寻道加旋转是毫秒量级。相比之下一次 DRAM 访问是 100 纳秒量级，一次 L1 命中约 1 纳秒（各级延迟量级见页末参考文献 [3]）。

于是可优化的量只剩一个：访存次数。一个数据结构在磁盘上的性能，几乎完全由「一次操作要摸几页」决定，页内做多少事都是白送的。

注 · 这套代价模型有个正式的名字，叫 external memory model 或 I/O model，由 Aggarwal 与 Vitter 在 1988 年形式化：内存能装 $M$ 个元素，一次 I/O 搬 $B$ 个元素，算法的代价按 I/O 次数计。B-tree 在这个模型里的查找代价是 $O(\log_B n)$ ，而二叉查找树是 $O(\log_2 n)$ ，底数之差就是全部。

2 · 从扇出到树高

节点既然至少要占一页，就该把这一页填满。一个内部节点里放 $k$ 个 key 与 $k+1$ 个孩子指针，占用

\text{header} + k \cdot s_{\text{key}} + (k+1) \cdot s_{\text{ptr}} \le S_{\text{page}}

解出最大的 $k$ ，加一便是扇出 $f$ ，即一个节点最多能有多少个孩子。4 KB 页、8 字节 key、8 字节指针给出 $f = 256$ ；16 KB 页配 InnoDB 的 6 字节页号给出 $f = 1170$ 。

树高随之塌下来。一棵高 $h$ 、扇出 $f$ 的树最多容纳 $f^h$ 条记录，所以装 $n$ 条至少需要 $h = \lceil \log_f n \rceil$ 层：

结构	扇出	$n = 10^7$ 的树高	$n = 10^9$ 的树高
完全平衡 BST	2	24	30
红黑树（高度上限）	2	46	59
B-tree，4 KB 页	256	3	4
B-tree，16 KB 页	1170	3	3

图 2-1 · 页大小、key 大小与指针大小决定扇出，扇出决定树高，右侧柱形是同样记录数下二叉树高与 B-tree 树高的对照。可调页大小与 key 大小观察树高在哪一档跳变。

10 亿条记录、16 KB 页，树高仍是 3。这不是巧合而是对数的形状： $1170^3 \approx 1.6 \times 10^9$ 。扇出进入千的量级后，树高在整个实用规模区间里只有 3 或 4 两个取值，超出这个区间要么是记录数少得不需要索引，要么是 key 大到扇出掉回两位数。

警示 · 本页最初写的是「4 KB 页、8 字节 key 的 B-tree 扇出 256、树高 4」。跑一遍 treeHeight 才发现是 3： $256^3 = 16777216$ 已经超过 1000 万，第四层根本用不上。树高 4 对应的是扇出 100 那一档（ $100^3 = 10^6$ ，不够装 $10^7$ ）。改的是正文，不是代码——这类「量级差不多」的估算最容易在数量级边界上错一层，而错一层就是代价差 33%。

3 · 访存次数与比较次数的对账

高扇出不是免费的。节点变大以后，在节点内部找到该走哪个孩子这件事本身变贵了。

本系列的 B+ tree 引擎把两笔账分开计：cost.nodeReads 记摸过几个节点（每个节点一页，故等于页读次数），cost.compares 记做过几次 key 比较。100 万条记录、随机插入、2000 次随机点查的实测：

阶 $m$	树高	节点数	平均页读	平均比较
4	13	647717	13.00	21.8
16	6	103282	6.00	34.4
64	4	23329	4.00	77.5
256	3	5584	3.00	197.6

图 3-1 · 同一批 key 分别装进不同阶的 B+ tree，蓝柱是平均页读、绿柱是平均比较次数。可改 key 数量与阶的取值范围，观察两条曲线的方向相反。

两列的方向相反。页读从 13 降到 3，比较从 21.8 涨到 197.6，省访存的手段就是多比较。 $m = 4$ 那一行的比较次数只有 21.8，接近 $\log_2 10^6 \approx 20$ ，这是二叉查找的理论下界附近； $m = 256$ 那一行的 197.6 则是「每层线性扫过约 $m/2$ 个 key，扫三层」。

这笔交换划得来，因为两项的单价差了三到五个数量级。一次页读 100 微秒，一次比较几纳秒： $m = 256$ 那一行的总代价是 $3 \times 100\,\mu s + 197.6 \times \text{几 ns} \approx 300\,\mu s$ ， $m = 4$ 那一行是 $13 \times 100\,\mu s \approx 1300\,\mu s$ 。多出来的 176 次比较在总账里连零头都算不上。

节点内的线性扫描还可以换成二分查找，把这一项压到 $\log_2 m$ 量级。它值得做（缓存友好的实现通常在小节点上用线性、大节点上用二分），但它改变不了表里的页读那一列。两笔账相互独立，这也是把它们分开计的理由。

建议 · 「扇出越大越好」有上界，来自三处而非一处。其一，页大小由文件系统与设备的最优 I/O 粒度定，超过它一页读不完、要拆成多次请求。其二，节点内的写入代价随节点变大而上升：插入一个 key 要在页内挪动平均一半的 entry， $m = 1170$ 时是挪 585 个。其三，并发控制的粒度通常就是页，页越大冲突越多。工程上落在 4 KB 到 16 KB 之间，不是因为再大算不出好处，而是这三条先撞上来。

4 · 参考文献

Bayer, R., & McCreight, E. (1972). Organization and maintenance of large ordered indices. Acta Informatica, 1(3), 173–189.
Aggarwal, A., & Vitter, J. S. (1988). The input/output complexity of sorting and related problems. Communications of the ACM, 31(9), 1116–1127.
Scott, C. Latency numbers every programmer should know. 取自 Jeff Dean 的量级表，可按年份查看各级存储延迟的变化。
Comer, D. (1979). The ubiquitous B-tree. ACM Computing Surveys, 11(2), 121–137.