fanout · 填充因子 · 回表 · 索引体积

页与扇出的算术

前四页把结构讲完了，剩下的全是算术。索引设计中的大部分决定，比如页大小选多少、要不要把某列加进索引、为什么长 key 是灾难，都可以在这一页的四个式子里得到答案。

本页的参数取 InnoDB 的一组：页 16 KB，页号 6 字节，主键 8 字节。

1 · 扇出与叶容量

一个内部节点里 $k$ 个 key 配 $k+1$ 个孩子指针，塞进一页：

k \cdot s_{\text{key}} + (k+1) \cdot s_{\text{ptr}} \le S_{\text{page}} \quad\Longrightarrow\quad f = k_{\max} + 1 = \left\lfloor \frac{S_{\text{page}} - s_{\text{ptr}}}{s_{\text{key}} + s_{\text{ptr}}} \right\rfloor + 1

叶子不存孩子指针，存的是 key 与 value，所以另有一个式子：

c_{\text{leaf}} = \left\lfloor \frac{S_{\text{page}}}{s_{\text{key}} + s_{\text{value}}} \right\rfloor

两者的分母不同，这是 B+ tree 的内部层与叶层扇出不一致的全部原因。16 KB 页、8 字节 key、6 字节页号给出 $f = 1170$ ；同一页里若 value 是 120 字节的行，叶子只装得下 128 条。

页大小	key 8 B	key 16 B	key 32 B	key 64 B
4 KB	293	186	108	59
8 KB	585	373	216	117
16 KB	1170	745	432	234

key 从 8 字节涨到 64 字节，扇出掉到五分之一。索引 key 的宽度是唯一一个既由业务决定、又直接换算成页读次数的量。这是「别拿长字符串做索引 key」的定量版本。

图 1-1 · 页大小、key 大小、value 大小、记录数四个参数决定扇出、叶容量、树高、索引页数与索引体积。可调各参数观察哪一个先把树高顶上一层。

2 · 索引占多少页

树高只是点查的代价，索引本身占多大空间是另一笔账，而这笔账通常更能左右「要不要建这个索引」。

叶层页数为 $\lceil n / (c_{\text{leaf}} \cdot \phi) \rceil$ ， $\phi$ 是填充因子；上一层再按 $f \cdot \phi$ 收拢，直到只剩一页。1000 万行、 $\phi = 0.69$ 的两组算例：

索引	叶容量	叶层页数	总页数	层数	体积
聚簇索引（整行 120 B）	128	113637	113779	3	1778 MB
二级索引（16 B 列 + 8 B 主键）	682	21277	21305	3	333 MB

两张表都是 3 层，但体积差 5.3 倍。这解释了一个常见的观察：给一张大表加一个窄列的二级索引，磁盘涨得远比想象中少；而把一个宽列（比如 200 字节的 URL）加进去，索引体积会逼近表本身。

内部层在总页数里的占比小得可以忽略——113779 页里只有 142 页是内部节点，0.12%。这正是「顶部几层常驻内存」在工程上可行的原因：把上面两层全部 pin 在 buffer pool 里只要 2 MB 出头，而这两层挡掉了三分之二的页读。

3 · 回表要走两棵树

聚簇索引的叶子里装的是整行，二级索引的叶子里装的是主键值。于是「用二级索引查一整行」要走两棵树：先在二级索引里定位到主键（3 次页读），再拿主键去聚簇索引里取行（3 次页读），共 6 次。

覆盖索引把第二段省掉：查询要的列全在二级索引里，3 次页读就结束。代价在 §2 那张表里：每加一列， $c_{\text{leaf}}$ 变小、叶层页数变大、索引体积上涨，且每次写入要多维护一份。

范围查询让这笔账更悬殊。扫 1000 行，覆盖索引是 3 次随机读加约 $1000/470 \approx 2$ 次顺序读；不覆盖则要为每一行单独回表一次，3 次随机读加 1000 次随机读。差的不是常数因子，是「回表次数与结果行数成正比」这个结构。

4 · 填充因子

前面所有算式里的 $\phi$ 都不是 1。B+ tree 的叶子几乎从不满，因为分裂总是把一个满页切成两个半页，此后两边各自再填。

图 4-1 · 同一批 key 分别按递增顺序与随机顺序插入 B+ tree，两侧的叶填充率与叶页数。可改阶 m 与 key 总数，观察随机插入稳定落在 ln 2 附近而递增插入落在 50%。

20 万个 key 的实测：

阶 $m$	随机插入的叶填充	递增插入的叶填充	叶页数之比
16	70.7%	53.3%	1.32
32	69.9%	51.6%	1.35
64	69.5%	50.8%	1.37
128	70.2%	50.4%	1.39
256	70.8%	50.2%	1.41

随机插入那一列稳定在 70% 附近，与 Yao 在 1978 年用 fringe analysis 得到的渐近值 $\ln 2 \approx 69.3\%$ 相符。

警示 · 递增插入那一列是本页最初写错的地方。常见的说法是「顺序写入的索引填充率高、随机写入的索引碎片多」，据此本页原本预期递增插入会接近 100%。实测是 50.2%——恰恰相反。原因在分裂规则上：递增插入永远在最右那个叶子溢出，中位切开后左半再也不会收到任何 key，永远停在半满；右半继续接收，满了又切一半。整棵树由一串永久半满的叶子组成。「顺序插入填充率高」这个说法成立，但它描述的不是朴素 B+ tree，而是带右倾分裂优化的实现：检测到插入点在最右端时，不切一半，而是把几乎全部 key 留在左页、新页只放刚插入的那一个。PostgreSQL 与 InnoDB 都有这项优化。本系列的引擎没有实现它，所以实测忠实地反映了朴素分裂的行为——正文因此改成「朴素分裂下 50%」，而不是改代码去凑那个流传的结论。

填充因子的三项后果：索引体积按 $1/\phi$ 放大（ $\phi = 0.69$ 意味着多占 45% 的空间）；扫描要读的页数同比例增加；而树高几乎不受影响，因为它随 $\phi$ 只有对数级的变化。16 KB 页下 $\phi$ 从 1 掉到 0.5，1000 万行的树高仍然是 3。

5 · 参考文献

Yao, A. C. (1978). On random 2-3 trees. Acta Informatica, 9(2), 159–170.
Johnson, T., & Shasha, D. (1989). Utilization of B-trees with inserts, deletes and modifies. Proceedings of PODS '89, 235–246.
Oracle Corporation. MySQL 8.4 Reference Manual, §17.6.2.2: The Physical Structure of an InnoDB Index（含 MERGE_THRESHOLD 与页填充策略）.
Graefe, G. (2011). Modern B-tree techniques. Foundations and Trends in Databases, 3(4), 203–402.