B+ 树：从纸笔推演到 MySQL 索引调优

一个 8000 万行的 orders 表，下面这条 SQL 跑了 4.2 秒：

SELECT * FROM orders
WHERE user_id = 12345 AND created_at >= '2026-09-01';

加上一个联合索引之后，同样的数据、同样的服务器，它变成了 3 毫秒——快了 1400 倍。

ALTER TABLE orders ADD INDEX idx_user_created (user_id, created_at);

差别在哪里？不是"索引会变魔术"。差别在于：前者把 8000 万行从磁盘上一个页一个页地翻了一遍，后者只沿着一棵矮树下降了三次、读了三四页就找到了全部结果。

这棵树就是 B+ 树。它是 MySQL、PostgreSQL、SQLite、Oracle、SQL Server，以及绝大多数你需要"按主键查一行"“按时间扫一段"“按名字排序"的数据库，默认的索引结构。

本文想做的事，是用最少的数学、最直观的类比，把这棵树讲透，然后你会发现：MySQL 里那些看起来要靠背的优化规则——最左前缀、索引不失效、覆盖索引、主键自增、深分页、索引下推——没有一条是玄学，全部可以从 B+ 树的形状直接推出来。

先给出全文结论：

索引 = 用额外的空间和写入成本，为某一列维护一份"排好序的、每页能装几百上千个 key 的矮树”。B+ 树把一次查找从"扫过 N 行"降成"沿树下降 h 层、每层读 1 个 16KB 的页”，h 通常只有 3～4；而 MySQL 的每一条索引优化规则，本质上都在回答两个问题：① 这棵树维护的"顺序"，你的查询用得上吗？② 为了让查询少读几页，值不值得让写入多花一些维护这棵树的代价？

阅读建议（全文约 2.2 万字，可以按需跳读）：

• 完全没学过索引：读一、二、三、四、五、六，建立直觉和算术感；
• 想理解 MySQL 行为：直接看八、九、十，每条规则都配了真实实验；
• 只想要结论：翻到十二"速查表"，再回头看对应的推导。

想动手玩树的话，本文配了一个可交互的 B+ 树演示（demos/bplus-tree/），插入、分裂、删除、借位都有动画和解说，可以边读边点。

一、开场：一条 4 秒的 SQL，慢在哪

先把慢查询拆开看。数据库接到这条 SQL，要做三件事：

1. 找到起点：满足 user_id = 12345 的第一行在哪里？
2. 往后扫：从这个点开始，把 created_at >= '2026-09-01' 的行一条条取出来；
3. 回表：如果 SELECT *，还要拿到这一行的其它列（amount、status……）。

没有索引时，orders 表对数据库来说就是"一堆无序的行"。它不知道 user_id = 12345 的行在哪，只能从头到尾逐页读取、逐行判断。8000 万行的表大约占 8000 万 × 100 字节 ≈ 8 GB，按 InnoDB 16KB 一页算，约 50 万个页。即使全走磁盘缓存，把 50 万页过一遍也要几百毫秒到几秒；如果冷启动、走真实磁盘，就是本文开头那个 4.2 秒。

有了 (user_id, created_at) 索引之后，数据库里有了一份按 (user_id, created_at) 排好序的目录：

• 先用 user_id = 12345 在目录里走 3 层，跳到"这个用户的第一条记录"；
• 再沿目录的叶子链表往后走，直到 created_at 超过范围。

整个过程读的页数是 个位数到几十，不是 50 万。这就是 1400 倍差距的来源。

所以问题变成了一个纯数据结构问题：

怎样设计一个结构，让"按某个字段查一行"只需要读少数几个磁盘页，同时又支持"按顺序扫一段"？

答案不是"哈希表"，也不是"红黑树"，而是 B+ 树。要理解为什么，得先接受三个物理事实。

二、数据库的三个物理事实

学数据结构时，我们习惯数"比较次数"。但在数据库里，比较几乎不要钱，读磁盘才要钱。这三个事实决定了整个数据库索引的设计。

2.1 事实一：内存和磁盘差了三个数量级

这些数字来自公开的延迟对照表（“Latency Numbers Every Programmer Should Know"及其 2020 年更新版），具体值不同硬件会有差异，但数量级关系是稳定的：内存里一次比较是眨眼，磁盘上读一次是出门。

换算一下：CPU 做一次比较大约 1 纳秒；SSD 读一页大约 100 微秒——这 100 微秒里，CPU 能做 10 万次运算。

2.2 事实二：磁盘按"页"读，不按字节读

磁盘（以及操作系统、数据库）读写的最小单位是块/页，不是字节：

• 机械硬盘一个扇区 512 B～4 KB；
• 操作系统页 4 KB；
• InnoDB 默认页大小 16 KB。

这意味着：你要读 1 行（100 字节），数据库也得把包含它的那 16 KB 页整个读进来。读一页的成本 ≈ 读一万行里的一行。

这个事实带来一个非常反直觉的结论：

“一次查一行"和"一次查一页里的一百行”，磁盘成本几乎一样。

所以好的索引结构应该尽可能让每一页多装一些"路标”，让一次下降能排除掉更多的可能性；而不该像二叉树那样，一个节点只装一个 key、一次只排除一半。

2.3 事实三：顺序 IO 远快于随机 IO

同样读 1 GB 数据：

• 顺序读：磁盘磁头不停旋转/闪存连续地址，机械盘能到 100–200 MB/s，SSD 能到 GB/s；
• 随机读：每次都要寻道/寻址，机械盘每秒只能做 100–200 次 IO，SSD 每秒几万到几十万次。

差距在机械盘上是 几十到上百倍，在 SSD 上也有 十几倍。这就是为什么 B+ 树要把所有数据放在叶子、并用链表把叶子串起来：范围扫描可以顺着链表顺序读，而不是在树里跳来跳去。

2.4 把三个事实合成一条设计目标

三个约束合起来，指向一个明确的方向：

节点要大（装得下一整页）、树要矮（每层扇出尽量大）、数据要在叶子且互相串起来（范围扫描顺序化）。

B+ 树就是同时满足这三条的树。

三、数据结构淘汰赛：从数组到 B+ 树

我们用一场"淘汰赛"来看 B+ 树为什么胜出。参赛者要满足的业务需求是数据库的典型需求：

1. 等值查询：WHERE id = 12345
2. 范围查询：WHERE created_at BETWEEN ... AND ...
3. 排序：ORDER BY created_at
4. 前缀匹配：WHERE name LIKE '张%'
5. 插入/删除：数据一直在变，结构得能维护得起

3.1 有序数组：查询很好，写入要命

把 8000 万行按 id 排好序放进一个数组，等值/范围/排序都完美：二分查找 $O(\log n)$ 次比较。

但磁盘上的二分查找不是 $\log n$ 次比较，而是 $\log n$ 次随机页访问——每次取中间元素都要读一个新的页。而且插入更糟：在数组中间插入一行，后面所有元素都要往后挪一格，磁盘上是几十 GB 的数据搬移。

• 优点：范围、排序能力完美；
• 致命伤：插入/删除 $O(n)$，随机访问代价高。

淘汰。

3.2 哈希表：只能回答"等于"

哈希表等值查询 $O(1)$，非常快。但它丢了顺序：

• WHERE created_at BETWEEN ...：没法做，只能全扫；
• ORDER BY created_at：没法做；
• LIKE '张%'：没法做。

而且磁盘上的哈希表还要面对"哈希冲突、扩容、每个桶一次随机 IO"的问题。

• 优点：纯等值查询最快；
• 致命伤：任何和顺序有关的查询全部失效。

淘汰出局，但保留一个席位：数据库里哈希索引确实存在——MySQL 的 MEMORY 引擎、InnoDB 的自适应哈希索引（AHI，第九章讲），都是"等值查询的加速器"，但它们永远不能单独当主索引。

3.3 二叉搜索树 / 红黑树：高度就是 IO 次数

二叉搜索树（BST）每个节点一个 key、两个子节点。理想情况下树高 $\log_2 n$：2000 万行 → 约 25 层。

这意味着一次点查要顺着 25 个节点下降。如果每个节点是磁盘上一页，就是 25 次随机 IO；如果节点不按页对齐，还会更糟（一次下降可能跨多个页）。

红黑树、AVL 树能保证平衡，但高度依然是 $O(\log_2 n)$——底数只有 2，这是它们的宿命。

还有一个更隐蔽的问题：节点太"小"了。一个节点只装一个 key，但磁盘一次读 16KB。如果按"节点=页"存，一页只装一个 key，浪费 99.99% 的读带宽；如果多个节点挤一页，树的下降路径就在页间乱跳，缓存不友好。

• 优点：内存里的有序结构，$O(\log n)$；
• 致命伤：层数太多（IO 太多），节点太小（页利用率低）。

淘汰。

3.4 跳表：Redis 的选择，不是磁盘的选择

跳表（skip list）用多层链表实现"概率平衡"，查找 $O(\log n)$，实现比红黑树简单，并发也友好。Redis 的 zset 就用它。

但磁盘数据库不选它，原因很直接：

• 跳表的每一层都是指针跳跃，一次查找会访问 $\log n$ 个分散的节点——和红黑树一样，是多次随机 IO；
• 跳表节点大小不固定，一棵 2000 万 key 的跳表节点散布在堆内存里，没有页的局部性；
• 它是为"全内存 + 随机访问廉价"设计的，而数据库面对的是"磁盘 + 随机访问昂贵"。

淘汰，但在内存数据库里合理。

3.5 B 树：第一次让"节点 = 页"

B 树的想法非常朴素：既然一次读一页，那就让一个节点正好是一页，一页里塞几百个 key。

• 每个节点最多 $m$ 个子节点，$m$ 由"一页能装下多少条记录"决定；
• 树高变成 $\log_m n$：$m$ 越大树越矮（理论上 $m=1000$ 时，2000 万行只要 3 层）；
• 查找时每层只读一页。

如果节点里只放 key 和指针，$m$ 能到上千，2000 万行只要约 3 层、3 次 IO——B 树已经比红黑树好了一个数量级。但它有一个结构性的包袱：B 树的内部节点也要存数据。一页 16KB，如果 key 8 字节、数据 100 字节，内部节点的记录数就少了一个数量级，扇出变小、树变高。

进入决赛，但还不是冠军。

3.6 B+ 树：把数据全部下沉到叶子

B+ 树在 B 树上做了三个关键改动：

1. 内部节点只存 key 和子指针，不存数据。同样一页，能装的 key 从几百个变成上千个，扇出更大、树更矮；
2. 所有数据（或指向数据的指针）只出现在叶子节点。查询路径固定：“从根走到叶子”，不会"走到中间就找到"；
3. 叶子节点用链表串起来（通常是双向链表）。范围查询 = 先定位下界，再顺着链表顺序读。

这三个改动带来三个收益，正好对应数据库的三类查询：

冠军。

3.7 一图总结这场淘汰赛

这个淘汰赛还有一个更深层的结论，值得用一句话记住：

B+ 树不是"最好的树"，而是"在磁盘这个约束下最好的树"。 如果全部数据都在内存里，红黑树、跳表、哈希表都可能更合适。理解这一点，就理解了第九章所有优化规则的来历——每一条规则，本质都是"别让这棵树做它不擅长的事"。

四、B+ 树的五条不变量

上一节我们说 B+ 树"内部节点只放 key、数据全在叶子、叶子串成链表"。这三句话是直觉，但写代码、判断对错、看懂 InnoDB，还需要更精确的定义。

4.1 先约定"阶"：一棵最多能长多胖的树

不同教材对"B+ 树的阶（order）“定义不一致。本文统一约定：

一棵 $m$ 阶 B+ 树：每个内部节点最多有 $m$ 个子指针；每个叶子节点最多有 $m-1$ 个 key。

（另一种常见约定是"阶 = 最多 key 数”，遇到时留意一下即可。本文用"最多子指针数"这一种，因为它和"扇出"直接对应。）

对 $m=4$ 的树：

• 内部节点：2～4 个子指针（根节点可以只有 1 个 key、2 个子指针）；
• 叶子节点：1～3 个 key（根同时也是叶子时，可以有 0～3 个 key）。

本文的手工推演都用 $m=4$，因为一屏画得下；真实的 InnoDB 里 $m$ 不是常数，而是由页大小和 key 大小算出来的（第六、八节会算），通常在几百到一千多之间。

4.2 看清楚结构：三层的小树

把图读成三段：

• 根节点（最上面）：只有 1 个 key，负责把查询"分岔"到两个子树；
• 内部节点（中间层）：每个 key 都是一个"路标"，左边子树的 key 都比它小，右边子树的 key 都大于等于它；
• 叶子节点（最下面）：真正的数据都在这里；相邻叶子之间用双向链表串起来，从左到右严格有序。

注意一个细节：内部节点里的 key，在叶子里也会出现一次（图里 5、9 这种路标）。所以准确说法是：叶子里存的是全部 key 的"正本"，内部节点存的是"副本/路标"。这就是 B+ 树名字里那个"+“的含义——内部节点只是索引，不拥有数据。

4.3 五条不变量

现在给出精确定义。一棵合法的 $m$ 阶 B+ 树必须同时满足：

1. 节点容量：每个节点最多 $m$ 个子指针；内部节点的 key 数 = 子指针数 - 1；叶子最多 $m-1$ 个 key。
2. 最低填充率：除根外，内部节点至少 $\lceil m/2 \rceil$ 个子指针；叶子至少 $\lceil m/2 \rceil - 1$ 个 key。（保证树不会"又高又瘦”。）
3. 根可以例外：根至少有 1 个 key 即可（空树除外）。
4. 所有叶子在同一层：树是完美平衡的——无论查哪个 key，经过的层数都一样。
5. 有序性：内部节点的 key 是它右边子树的最小 key；所有 key 在叶子层按从小到大排列，叶子之间用链表连接。

再加一条"存储约定"（不是结构不变量，但极其重要）：

6. 数据只在叶子：内部节点只存 key 和子指针，不存行数据（InnoDB 的叶子存整行，二级索引的叶子存主键值）。

这五条不变量看起来朴素，但从它们出发，可以直接推出 B+ 树擅长和不擅长什么。

4.4 从五条不变量直接读出"能力清单"

再对照上一节的淘汰赛，你会发现 B+ 树的每一分优势，都能在不变量里找到出处：

• 扇出大（不变量 1）→ 树矮 → 等值查询 IO 少；
• 完美平衡（不变量 4）→ 最坏情况和最好情况一样，没有"退化成链表"的风险；
• 数据只在叶子（不变量 6）→ 内部节点能塞下更多 key（同样一页，路标不占地方）；
• 叶子有链表（不变量 5）→ 范围、排序、全表扫描都是顺序 IO。

而它不擅长的事情也一目了然：

• 内部节点不存数据 → 天然不支持"哈希那样 $O(1)$ 的等值查询"，永远要走 h 层；
• 有序性只针对"索引定义的那几列、从左到右的字典序" → 查询一旦不匹配这个序，树就帮不上忙；
• 叶子链表只在同一层有效 → 范围查询没问题，但"跨索引"的联合查询还是要回表。

这三个"不擅长"，正是第九章 MySQL 优化规则的源头。先记住一句话：

B+ 树能免费提供的，只有"它维护的那个顺序"；超出这个顺序的查询，它一页都不会少读。

4.5 高度定理：树为什么这么矮

对一个有 $n$ 个 key、扇出为 $f$、每个叶子平均放 $r$ 个 key 的 B+ 树：

$$ \text{叶子数} \approx \frac{n}{r}, \qquad h \approx \log_f\left(\frac{n}{r}\right) + 1 $$

从公式能读出三件事：

1. 高度随 $n$ 增长得非常慢：$f=1000$ 时，数据量涨 1000 倍，树高才 +1；
2. 高度由页大小决定：$f$ 能有多大，取决于一页能装多少 key 和指针（所以 InnoDB 的页大小、key 类型、行长都直接影响树高）；
3. 下限由填充率决定：不变量 2 保证每个节点至少半满，否则树会变高；这也是"删除后要合并、插入会分裂"的意义。

这个公式后面会反复用到。现在先用它做一个具体的手工推演，把树"怎么长出来"看一遍。

五、手工推演：一棵 4 阶 B+ 树怎么长出来

我们按 $m=4$ 来。叶子最多 3 个 key，内部节点最多 4 个子指针。

5.1 顺序插入 1 到 10

把过程拆成一张表：

第 8 步之后，根节点自己有 4 个 key、5 个子指针，超过了 $m-1=3$ 的限制——根也要分裂：

分裂前（非法，根 4 个 key）：
                     [3, 5, 7, 9]
                   /  /    |    \   \
              [1,2][3,4][5,6][7,8][9,10]

分裂后（合法，树高 3）：
                          [5]
                        /     \
                    [3]         [7, 9]
                   /   \       /   |   \
                [1,2] [3,4] [5,6] [7,8] [9,10]

根分裂的做法和普通内部节点一样：把中间位置的那个 key 提升为新的根，左右各成一个内部节点。这里取的是 5（取 7 也合法，只要两边均衡——B+ 树的形状并不唯一，但每个合法形状的查询代价是一样的）。这是树唯一会长高的时刻：只有根分裂才会让树高 +1。

5.2 三个关键动作，各自为什么这么设计

动作一：叶子分裂，为什么提升"右叶的第一个 key"？

因为不变量 5 规定：内部节点的 key 是右子树的最小 key。分裂后右叶是 [3,4]，它的最小 key 就是 3，所以把 3 放到父节点当路标。以后查 3、查 4，到父节点看到 “≥3 走右边” 就对了。

动作二：内部节点分裂，为什么把中间 key"搬上去"而不是"复制上去"？

因为内部节点的 key 只是路标，不是数据。把一个 key 搬到新父节点后，左边的所有 key 仍小于它、右边的仍大于等于它，路由关系不变。（这也是 B 树和 B+ 树分裂细节上的一个区别：B 树会把 key 留在节点里，B+ 树"只搬副本"。）

动作三：为什么分裂点选中间？

为了让分裂后的两个节点各自填充率接近一半，维持不变量 2 的"至少半满"。如果总在 1/4 处分裂，树会很快变得又高又瘦，查询 IO 变多。

5.3 查找：两次"页内查找"

在这棵树上查 8：

第 1 次页访问：根 [5]              → 8 ≥ 5，走右子指针
第 2 次页访问：内部 [7, 9]          → 7 ≤ 8 < 9，走中间的指针
第 3 次页访问：叶子 [7, 8]          → 页内找到 8

一共 3 次页访问。注意每一层内部是怎么"用 key 选指针"的：节点里的 key 是有序的，可以用二分查找（InnoDB 在页内更进一步，用"页目录 + 稀疏槽"来快速定位，第八节讲）。

5.4 范围查找：叶子链表登场

查 4 ≤ key ≤ 8：

1. 先用 4 做一次等值下降，定位到叶子 [3,4]；
2. 在叶子里找到 ≥4 的位置，扫到页尾；
3. 沿着叶子链表的 next 指针跳到下一叶 [5,6]，整页扫；
4. 再跳 [7,8]，扫到 8 为止；再往右是 [9,10]，第一个 key 9 > 8，停止。

总页访问：下降 3 次 + 叶子 3 页 ≈ 4～5 页。关键在"沿链表顺序走"：这些叶子在磁盘上也是按 key 顺序分配的，所以这是一次近似顺序的 IO，比"在树里为每个 key 单独下降"快一个数量级。

如果没有叶子链表，范围查询会退化成"对区间里每个 key 各做一次 $O(h)$ 查找"——3000 个 key 就是 3000 次树下降。这就是"叶子链表"这一条设计值钱的地方。

5.5 删除：借一个，或者合并

删除比插入麻烦，因为它可能让节点"太瘦"，违反不变量 2。规则只有三条：

一个具体例子：还是用 5.1 里最终的树，依次删 10、9：

• 删 10：叶 [9,10] → [9]，仍 ≥1，直接删。
• 删 9：叶 [9] → 空，太瘦。左兄弟 [7,8] 有 2 个 key，可以借：把 8 挪过来 → 自己变 [8]、兄弟变 [7]，父节点路标从 9 改成 8。

如果兄弟也只有 1 个 key，就合并：[7] 和 [] 合成 [7]，父节点删掉分隔 key。父节点若因此低于最小子指针数，就继续向上借或合并；如果根最后只剩 1 个子节点，就把这个子节点提升为新根，树高减 1——这是树唯一会变矮的时刻，和"只有根分裂才长高"对称。

删除的全部细节，demos/bplus-tree/ 的演示里可以一步步点着看（借位和合并都有高亮）。

5.6 复杂度小结

注意：分裂和合并虽然最坏是 $O(h)$，但均摊下来极少发生——一个节点要装进 $m-1$ 个 key 才裂一次。所以 B+ 树的写性能并不差，真正贵的是"随机位置的写入"（第八、九章会看到它把页写碎）。

到这里，B+ 树的"形"已经清楚了。接下来要回答一个非常实际的问题：这么一棵树，到底能装多少数据？为什么工程上总说"三层 B+ 树能存两千万行"？

六、算术时刻：三层为什么能装下两千万行

这一节全是小学算术，但它是整篇文章最重要的"数量级直觉"。算完你会对"索引为什么快"有一个可验证的信念，而不是背结论。

6.1 扇出：一页能装多少个路标

内部节点里的每条记录长这样：

[ key ][ 子页号 ]      ← 内部节点记录：只有 key 和"下一层在哪一页"

• 假设主键是 BIGINT：key 8 字节；
• 子页号（指针）：教科书的 B+ 树通常按 6 字节算；
• 一页 16 KB = 16384 字节。

于是：

$$ \text{扇出} \approx \frac{16384}{8 + 6} = 1170 $$

一页能装约 1170 个路标，即一个内部节点有约 1170 个孩子。 这是"三层存两千万"这个说法的第一块基石。

真实的 InnoDB 还要扣掉这些东西：

按这些开销重新算：$(8 + 4 + 5 + 2) \approx 19$ 字节/条，再乘 0.85 的填充率：

$$ \text{真实扇出} \approx \frac{16384 \times 0.85}{19} \approx 730 \text{（数量级 800 左右）} $$

所以后文会同时用 1170（理想） 和 800（保守） 两个口径算，结论只差一档数量级，不影响直觉。

6.2 叶子：一页能装多少行

叶子页要存一整行（聚簇索引）。假设平均行长 1 KB：

$$ \text{每叶行数} \approx \frac{16384 \times 0.9}{1024} \approx 15 $$

行越小，叶子能装越多；这也是为什么宽表（几百列、大 VARCHAR）的索引"更不耐装"。

6.3 三层树能装多少

一层根、一层内部节点、一层叶子：

$$ N_{\max} = \text{扇出}^2 \times \text{每叶行数} $$

这就是"三层 B+ 树能存两千万行"的出处——它是一个在"1 KB 行、8 字节主键、1170 扇出"假设下算出来的数字，不是常数。行更小就更多，行更大就更少：

反过来，如果行有 1 KB 又想稳超两千万，就需要第四层：四层的容量是三层再乘一个扇出，约 百亿行（保守口径 82 亿，理想口径 256 亿）。

6.4 和红黑树比一比：25 层 vs 3 层

同样是 2000 万行、每行 1 KB：

25 次随机 IO 是什么概念？按机械盘 10 ms/次算，就是 250 ms；按 SSD 0.1 ms/次算，也要 2.5 ms。而 B+ 树的 3 次，机械盘 30 ms、SSD 0.3 ms。差一个数量级，且数据量越大差距越大——因为红黑树每翻一倍数据就多一层，B+ 树要翻上千倍才多一层。

这张表值得盯十秒钟。它解释了数据库世界的两个常识：

• “数据量翻倍，查询不会明显变慢”：1000 万到 2000 万，B+ 树高度可能只从 3 变 4，多一次页访问；
• “大表加索引之后，几千万行和几百万行的点查差不多快”：因为树高几乎不变，差距在缓存命中率，而不在算法复杂度。

6.5 更反直觉的一点：树高是"慢变量"

把扇出取 1000，数据量从 1000 行涨到 1 亿行（涨 10 万倍）：

• 树高只从 2 层涨到 3 层，最多 +1 层；
• 真正变慢的不是树高，而是叶子页太多，缓存装不下。

所以数据库性能优化里，“减少树下降的次数"往往不是重点，重点是"减少需要读的叶子页数量"和"提高缓存命中率”。这直接解释了为什么：

• 覆盖索引（不回表）有用：省掉一次树的下降 + 一次随机回表；
• 索引要短（比如用前缀索引）：一页装更多 key，树更矮，缓存命中率更高；
• 深分页慢：LIMIT 1000000, 10 要数 100 万个索引项，树高没变，但要走 100 万步叶子。

6.6 那为什么实测点查常常只有 1 次 IO？

因为树的上面几层会被缓存。

一棵三层 B+ 树，内部节点总共只有 $1 + 800 \approx 800$ 页，约 12.8 MB。InnoDB 的缓冲池（Buffer Pool）默认 128 MB，把整棵树的"路标层"全放进去绰绰有余。命中后读取完全在内存里完成，一次点查真正落到磁盘上的，通常只有"最后一次叶子页访问"。

这带来一个重要的工程结论：

缓存"树的上层"性价比极高：12 MB 内存换掉 2/3 的磁盘 IO。缓存"叶子层"才是无底洞：叶子页的数量和数据量成正比，几百 GB 的表不可能全放进内存。

所以：

• 内存要优先给"热数据"和"索引上层"；
• 表越宽，叶子页越少装行，同样的内存能缓存的行数越少——“窄表"不只是省空间，也提高了缓存命中率；
• 这也就是后面讲 Buffer Pool、innodb_buffer_pool_size、以及"为什么索引列越短越好"的地方。

七、实现一：用 400 行代码写一棵 B+ 树

看完原理，最快的验证方式是自己写一遍。这一节拆解一份零依赖的 400 行 JavaScript 实现（完整代码在 demos/bplus-tree/bplus.js，配了 1 万次随机操作的测试和交互式演示页）。

它的目标不是"造一个数据库”，而是把所有不变量变成可执行、可检查的代码——写完你会对"为什么分裂要提升右叶第一个 key"“为什么删除要借位"有肌肉记忆。

7.1 数据模型：一个节点就是一个"页”

class Node {
  constructor(id, leaf) {
    this.id = id;                     // 页号：演示里显示成 P3
    this.leaf = leaf;
    this.keys = [];                   // 页内的 key，严格升序
    this.values = leaf ? [] : null;   // 仅叶子：行数据（教学里就是 value）
    this.children = leaf ? null : []; // 仅内部页：子页指针
    this.next = null;                 // 仅叶子：右兄弟指针（叶子链表）
    this.parent = null;               // 便于分裂/合并时向上回溯
  }
}

把它和 InnoDB 的页逐一对应：

这就是"节点 = 页"的具体含义：一个 Node 对象承载一页的内容，B+ 树的全部结构都在这些数组里。

7.2 查找：每个内部页选一个孩子，叶子页内二分

_route(key) {
  if (!this.root) return { path: [], found: false, index: -1, insertAt: 0 };
  const path = [];
  let node = this.root;
  while (!node.leaf) {                       // 上层：每层只做一次"选哪个孩子"
    path.push(node);
    let i = 0;
    while (i < node.keys.length && this.compare(key, node.keys[i]) >= 0) i += 1;
    node = node.children[i];
  }
  path.push(node);                           // 到底了：叶子层二分查找
  let lo = 0, hi = node.keys.length;
  while (lo < hi) { const mid = (lo + hi) >> 1; if (this.compare(node.keys[mid], key) < 0) lo = mid + 1; else hi = mid; }
  const found = lo < node.keys.length && this.compare(node.keys[lo], key) === 0;
  return { path, found, index: found ? lo : -1, insertAt: lo };
}

两个细节，正好对应第四、五节的定义：

• 内部节点的选择规则：keys[i] 是"第 i+1 个孩子的最小 key"，所以找"第一个 key ≥ 分界 key 的孩子"——这也是为什么分裂时要把右叶第一个 key 复制到父节点；
• path 数组就是"这次查询访问了哪几个页"：path.length 就是点查要读的页数。文章里"一次点查 = 3 次页访问"的结论，在代码里就是 route(key).pageAccesses === 3。

7.3 插入与分裂：自底向上，最多到根

插入分两步：先找到叶子、插进去；如果超过上限，就沿父指针自底向上分裂。

// 插入完成后：while 循环处理"这一页 key 超限了"
let child = leaf;
while (child.keys.length > this.maxKeys) {
  const isLeaf = child.leaf;
  // 叶子：从中间劈开，右叶第一个 key 复制提升
  // 内部页：从中间劈开，中间 key 上移（搬走，不复制）
  const mid = isLeaf ? Math.floor(this.order / 2) : Math.floor((this.order - 1) / 2);
  const upKey = child.keys[mid];
  const right = new Node(++this._id, isLeaf);
  if (isLeaf) {
    right.keys = child.keys.slice(mid);      child.keys = child.keys.slice(0, mid);
    right.values = child.values.slice(mid);  child.values = child.values.slice(0, mid);
    right.next = child.next;                 // 维护叶子链表
    child.next = right;
  } else {
    right.keys = child.keys.slice(mid + 1);        child.keys = child.keys.slice(0, mid);
    right.children = child.children.slice(mid + 1); child.children = child.children.slice(0, mid + 1);
  }
  const parent = child.parent;
  if (!parent) {                          // 根也满了：新建根，树高 +1
    const root = new Node(++this._id, false);
    root.keys = [upKey];
    root.children = [child, right];
    this.root = root;
    break;
  }
  const idx = parent.children.indexOf(child);
  parent.keys.splice(idx, 0, upKey);          // 把提升的 key 插到父页
  parent.children.splice(idx + 1, 0, right);  // 把新页挂到父页
  child = parent;                             // 继续向上处理
}

这段代码就是第五节的翻版。几个和文章呼应的点：

• 叶子分裂复制、内部节点分裂搬移：upKey 的来源不同，这由"内部节点 key 是路标"决定；
• right.next = child.next; child.next = right：叶子链表必须同步维护，否则范围查询会断；
• 根分裂 = 树高 + 1：这是树长高的唯一入口；
• mid 取中间：为了让分裂后的两页填充率接近 50%，维持"至少半满"的不变量。

7.4 删除：先借，借不到就合并

删除的规则在第五节已经用一张表讲清了。代码里是一个"自底向上修复下溢"的循环：

_deleteFix(node, steps, heightBefore) {
  while (node !== this.root) {
    if (node.keys.length >= this.minKeys) return;       // 没下溢，收工
    const parent = node.parent;
    const idx = parent.children.indexOf(node);
    const left  = idx > 0 ? parent.children[idx - 1] : null;
    const right = idx < parent.children.length - 1 ? parent.children[idx + 1] : null;

    if (left && left.keys.length > this.minKeys) { /* 向左兄弟借一个 */ return; }
    if (right && right.keys.length > this.minKeys) { /* 向右兄弟借一个 */ return; }

    // 兄弟都只有下限 → 合并进左兄弟（或把右兄弟并进自己），然后父页继续检查
    ...
    node = parent;
  }
  // 根被合并空了 → 唯一子节点变成新根，树高 -1
}

注意最后一步：根空了就把孩子提上来，树高 -1——和"根分裂树高 +1"对称。到这里，插入、删除、查找三条路径都闭环了。

7.5 用不变量测试"证明"实现没写错

B+ 树的代码很容易写出"看起来能跑、实际上结构坏了"的 bug：漏更新父节点 key、叶子链表断链、合并后区间越界……这些 bug 往往只在特定顺序的插入/删除后才暴露。

所以实现里写了 checkInvariants()，把第四节的五条不变量逐条翻译成断言：

// 不变量检查（节选，完整版见 bplus.js）
if (node.keys.length > this.maxKeys) add(`页 P${node.id} 超过 key 上限`);
if (!isRoot && node.keys.length < this.minKeys) add(`页 P${node.id} 低于 key 下限`);
if (node.children && node.children.length !== node.keys.length + 1)
  add(`内部页 P${node.id} 的子页数应为 keys + 1`);
// 每个节点必须落在祖先给的 (lo, hi) 区间内
if (lo !== null && node.keys[0] <= lo) add(`页 P${node.id} 的 key 破坏祖先区间`);
// 叶子链表的顺序必须与中序遍历一致
if (prev && prev.keys.at(-1) >= cur.keys[0]) add(`叶子链表顺序错误`);

测试脚本（demos/bplus-tree/test.mjs）做三件事：

1. 与参考实现随机对拍：用有序数组做"标准答案"，随机执行 1 万次插入/删除，每次操作后对比查找结果；
2. 结构体检：每 1000 次操作调用一次 checkInvariants()，必须返回空数组；
3. 边界用例：空树删、单元素、阶 = 3 时的连续分裂/合并、删除到空树。

在这台机器上，这套测试的实际输出是：

在这台机器上，这套测试的实际输出是：

$ node test.mjs
断言：通过 17061，失败 0

主随机对拍：order=4 / 10000 次 insert+delete（每 1000 次查不变量）
  最终 size=952，树高=7，节点=863（内部 308 + 叶子 555）
  叶子填充率均值=57.2%，平均每叶 1.72 个 key
  分裂=1106 次，借位=396 次，合并=228 次，重复插入(更新)=1925 次

order=4 顺序插入 1..10：树高 3，节点 8（3 内部 + 5 叶子），分裂 5 次（4 叶子 + 1 根）
  叶子=[1,2]|[3,4]|[5,6]|[7,8]|[9,10]；根=[5]；左内部=[3]；右内部=[7,9]

IO 估算（2000 万行 / 1KB 行 / key 8B / 指针 6B / 16KB 页）：
  扇出 1170，B+ 树高 3，点查 3 次页访问；二叉搜索树 25 层

PASS：全部通过 ✅

两个值得注意的数字：

• 随机增删之后，叶子平均填充率只有 57.2%——这是"随机写入把树写碎"的直接证据（第 9.3 节），顺序插入则能接近 90%；
• 1 万次操作里发生了 1106 次分裂、396 次借位、228 次合并——写路径上"结构维护"远比想象中频繁，这就是写放大。

7.6 教学实现与 InnoDB 还差什么

这份 400 行代码只实现了 B+ 树的"骨架"。真实的 InnoDB 在它外面还包了一整套工程系统：

这正好说明了本节的定位：B+ 树的原理 400 行就能讲完，而数据库把它工程化需要几十万行。面试里问"B+ 树怎么实现"，问的是前者；线上排查"为什么这个索引没走"，靠的是后者。

八、实现二：MySQL InnoDB 里的 B+ 树

前七节讲的是"教科书上的 B+ 树"。但 MySQL 的实现不是把教科书直接抄过来：它把节点做成了 16 KB 的页，页里又塞了记录头、页目录、空闲链表……这一节我们打开 InnoDB 的页，看真实的 B+ 树长什么样。先给结论：InnoDB 的表，就是一棵以主键为 key 的 B+ 树；你看到的"表"和"索引"，在物理上是同一棵树。

8.1 一组页，就是一整棵树的节点

InnoDB 把数据文件（.ibd）切成一页一页，默认每页 16 KB（innodb_page_size 可以设成 4/8/16/32/64 KB，但建库后不能改）。表空间里的页有不同的类型：

• 第 0 / 1 / 2 页：文件头（FSP_HDR）、插入缓冲位图（IBUF_BITMAP）、索引节点信息（INODE）；
• 之后才是数据页、溢出页、undo 页……
• 在 file-per-table（默认）的独立表空间里，表的第一棵 B+ 树（聚簇索引）的根页通常从第 3 页开始；这是 InnoDB 的实现细节，不是文档契约（系统表空间里不成立）。

“每个节点正好是一页"不是比喻：在 InnoDB 里，B+ 树的节点就是一个 16 KB 的索引页。根节点长期住在内存里，剩下的一页一页按需读。

所以查询一次点查的 IO 次数，就是"从根页走到叶子页要经过几个索引页”。这直接把第六节的算术和真实的磁盘 IO 对上了。

8.2 一页 16 KB 里到底装了什么

InnoDB 用的是 Slotted Page（分槽页） 结构。一页从 0 到 16384 字节，大致是这样：

偏移 0    +--------------------------------------------------+
          | FIL Header（38B）：页号、上一页/下一页、LSN、页类型、校验  |
偏移 38   +--------------------------------------------------+
          | Page Header（56B）：记录数、页目录槽数、PAGE_LEVEL、堆顶……  |
          +--------------------------------------------------+
          | Infimum 记录（13B） | Supremum 记录（13B）              |  ← 页内两个虚拟哨兵
          +--------------------------------------------------+
          | User Records（变长）                               |
          |   记录按 key 从小到大排列，用 5 字节记录头里的             |
          |   next_record 偏移串成一条单向链表                    |
          +--------------------------------------------------+
          | Free Space（空闲区，按空闲链表管理）                     |
          +--------------------------------------------------+
          | Page Directory（变长）：稀疏槽位，每槽指向 4～8 条记录      |
偏移 16376+--------------------------------------------------+
          | FIL Trailer（8B）：校验和、LSN 低 32 位                 |
偏移 16384+--------------------------------------------------+

几个对理解性能很关键的点：

再往下是记录的物理格式。InnoDB 默认行格式是 DYNAMIC，一条记录大概长这样：

[ 变长字段长度列表 ][ NULL 位图 ][ 5 字节记录头 ][ 列 1 ][ 列 2 ]……

其中"变长字段长度列表"是反着存的（最后读到的变长列在最前），NULL 列不占数据空间、只在 NULL 位图里占一位。这些细节解释了为什么：

• 太多变长列（VARCHAR/TEXT）会让行变长，一页装的行数变少，B+ 树变高、叶子 IO 变多；
• 行太长会溢出：DYNAMIC 格式下，超长字段只在本页存 20 字节指针，真实内容放到"溢出页"（off-page），读一行要多读额外的页；
• InnoDB 单行最大约 8 KB（手册口径"约半页"，16 KB 页时内部阈值 8126 字节），超过就报错——这条限制来自"一页至少要装两行"的页结构设计，也解释了为什么一行不能无限宽。

8.3 聚簇索引：主键的叶子就是整行数据

InnoDB 的主键索引叫聚簇索引（Clustered Index），它的叶子页里存的不是"指针"，而是完整的一行数据。

这意味着：

• 按主键查一行 = 一次树下降，到底就拿到整行，不需要再去别的地方取数据；
• 按主键排序 / 范围扫描 = 顺序读叶子页，因为叶子页之间的链表是按主键顺序连的；
• 表本身没有独立的"数据区"——数据就长在主键 B+ 树的叶子上。这就是"索引组织表（Index-Organized Table）“的含义。

如果没有定义主键，InnoDB 会退而求其次：

1. 选第一个 UNIQUE 且 NOT NULL 的索引当聚簇索引；
2. 如果也没有，就自动生成一个 6 字节的隐藏列 DB_ROW_ID 当主键。

所以"建表一定要显式主键"不是风格问题：没有主键的表，你根本不知道数据按什么顺序组织，每次插入的位置由隐藏 rowid 决定，二级索引里存的也是这个隐藏值。

8.4 二级索引：叶子存的是主键，不是行

你在 city 上建的普通索引是二级索引（Secondary Index）。它也是一棵 B+ 树，但叶子页里存的是：

[ 索引列的值 ][ 主键值 ]      ← 注意：不是整行

查询 SELECT * FROM users WHERE city = '杭州' 时，InnoDB 要经历两次树下降：

flowchart LR
    Q["SQL：SELECT * FROM users<br/>WHERE city = '杭州'"] --> S["第一步：走二级索引 idx_city<br/>叶子存 city + 主键 id"]
    S --> I["取出满足条件的一批 id<br/>（这些 id 在物理上不连续）"]
    I --> C["第二步：用每个 id 回表<br/>去聚簇索引再下降一次"]
    C --> R["从聚簇索引叶子取出整行"]

这个过程叫回表（table lookup）。回表有两个代价：

1. 每行一次树下降：哪怕聚簇索引只有 3 层，1000 行就是 1000 次下降；
2. 随机 IO：二级索引按 city 排序，取出来的主键 id 是乱序的，回表就是"按乱序的主键随机访问聚簇索引的叶子页”——这正是机械盘最怕的模式。

反过来，如果查询要的所有列都在二级索引里，就不需要回表：

-- 需要 name，不在索引里 → 回表
SELECT name FROM users WHERE city = '杭州';

-- 只要 city 和 age，都在 idx_city_age 里 → 覆盖索引，不回表
SELECT city, age FROM users WHERE city = '杭州';

执行计划里后者的 Extra 会显示 Using index，这就是"覆盖索引"。为什么它重要？因为二级索引的叶子页通常比聚簇索引窄得多——一页能装更多索引项，扫同样的数据读的页更少，而且完全省掉了回表的随机 IO。

8.5 树是怎么维护的：页分裂、填充率、MERGE_THRESHOLD

B+ 树不是建好就静止的树。每次 INSERT/DELETE 都可能改结构，InnoDB 的维护规则是：

• 叶子页满了，且新 key 落在中间：申请一个新的页，把记录分成两半（具体比例由插入位置和 InnoDB 的分裂策略决定）、更新父节点的路标——这就是页分裂（page split）；
• 新 key 总是落在最右侧（自增主键、递增时间戳）：InnoDB 有针对性优化，分裂更克制、新页主要接收新记录，页填充率能保持很高（手册口径：插入时尽量给页留 1/16 空间，顺序插入可接近 15/16 满）；
• 删除不会立刻回收页：InnoDB 先标记删除（记录头里的 delete 位），等页利用率低于 MERGE_THRESHOLD（默认 50%） 时才尝试和相邻页合并。所以删掉一半数据之后，表文件经常不会变小——这叫"空间碎片"。

这个 50% 的合并阈值是一个非常值得记住的数字：它是"合并"的触发线，不是"分裂"的比例。手册给出的页填充区间是：顺序插入接近 15/16（约 94%），随机插入大致在 1/2～15/16 之间。我们的教学实现在随机增删 1 万次后实测叶子填充率约 57%，正好落在这个区间的下半段——这就是"随机写入把树写碎"的量化表现。

页分裂还有"写放大"的代价：一次分裂要分配新页 → 搬一半记录 → 更新父页 → 写 redo log，本来一条 INSERT 只写一条记录，可能变成写好几页。这就是为什么"随机主键的插入"比"自增主键的插入"慢——不是因为插入本身，而是因为它把 B+ 树写碎了。

8.6 Buffer Pool：把树的上层放进内存

InnoDB 的所有读写都经过 Buffer Pool（缓冲池）：磁盘页先读进内存页，修改也在内存页上做，再由后台线程刷回磁盘。

• 默认大小 128 MB（MySQL 5.7 / 8.0 / 8.4 一致，更早的版本更小），生产环境通常设成物理内存的 50%～75%；
• 它缓存的是页，不是行、不是索引对象；
• 采用"两段式 LRU"：young 区（约 5/8）+ old 区（约 3/8）。新读入的页先插到 old 区尾部，只有停留超过 innodb_old_blocks_time（默认 1 秒）后再次被访问，才升级进 young 区。

为什么要这么设计？因为全表扫描会把缓存冲干净：如果新读的页直接插到 LRU 头部，一次大查询就能把热点页全部挤出去。两段式 LRU 让"只用一次"的页（全表扫描读的页）停留在 old 区并很快被淘汰，保护了真正热的数据。

第六节说过：三层树的内部节点总共约 800 页、十几 MB，可以长期驻留 Buffer Pool。所以一次点查的物理 IO 通常只有"叶子页"这一张；如果叶子页也在缓存里，甚至一次 IO 都没有。这解释了为什么"缓存命中率"比"树高"更直接影响线上延迟。

我们用实验量化了这件事（users 表 77.6 MB，Buffer Pool 96 MB）：

同样的 SQL、同样的树，只因为页在不在内存里，物理 IO 就在 0 和 4,989 之间跳变。这就是为什么"缓存命中率"比"树高"更值得监控。

8.7 写路径上的两个加速器：Change Buffer 与自适应哈希索引

Change Buffer（写缓冲）：修改一个非唯一二级索引时，如果目标页不在 Buffer Pool 里，InnoDB 不立刻把页读进来，而是把"这次修改"记在 Change Buffer 里，等这个页因为别的原因被读入时再合并（merge）。它的意义是把随机写变成顺序写：写入只追加 change buffer（在内存/系统表空间里连续写），避免了"为了改一个索引项而随机读一页"。

为什么"非唯一"才行？因为唯一索引需要先确认"这个值不存在"，必须把页读进来检查，无法延迟。这个细节是"能不用唯一索引就别用“这一建议在写入场景下的根据之一。（版本提示：innodb_change_buffering 在 MySQL 8.0 默认 all，8.4 起默认 none；另外，含降序索引列的二级索引不支持 change buffering。）

自适应哈希索引（AHI）：InnoDB 会在内存里为频繁访问的页建立哈希表，把"等值查找"直接映射到页地址，绕开 B+ 树的下降。注意：

• AHI 是内存结构，不是磁盘上的索引，也不改变 B+ 树；
• 它只对等值查询有效，范围/排序仍然要走 B+ 树；
• 它是"锦上添花”，不是"另一种索引类型"（MySQL 的 InnoDB 不支持显式 USING HASH 索引）。

这解释了为什么"哈希索引快"的说法在 MySQL 里总显得含糊：InnoDB 的等值查询有 B+ 树 + AHI 两层加速，但主结构永远是 B+ 树。（版本提示：innodb_adaptive_hash_index 在 MySQL 8.0 默认开启，8.4 起默认关闭。实测补充：本机对随机 key 做点查时，AHI 开关前后的页请求都是 3/6/9，没有差别——AHI 只在同一批页被反复访问、形成热点时才有收益，随机点查不会触发它。）

8.8 一个容易被忽略的事实：锁是加在 B+ 树的索引项上的

InnoDB 的行级锁，不是锁在"行"上，而是锁在"索引记录"上。锁对象的定位，依赖你查询时走的那棵 B+ 树。

这带来几个直接后果：

• UPDATE users SET ... WHERE email = 'x'：如果 email 上没有索引，InnoDB 只能全表扫描，并给扫到的每一行加锁（RR 隔离级别下还会加间隙锁）——你以为更新一行，实际锁了全表；
• 反过来，如果 email 是唯一索引且等值命中，InnoDB 可以只锁那一条记录，不会锁间隙；
• WHERE 条件命中的行数取决于索引能过滤掉多少——索引不仅决定读多少页，也决定锁多少行。线上很多"莫名其妙锁等待/死锁"，根因就是某条 UPDATE 没走索引。

到这里，“InnoDB 里的 B+ 树"就完整了：

• 节点 = 16 KB 页，页内是"记录链表 + 稀疏目录”；
• 表 = 聚簇索引 = 主键 B+ 树，叶子存整行；
• 二级索引 = 另一棵 B+ 树，叶子存"索引列 + 主键"；
• 维护 = 页分裂 / 标记删除 / MERGE_THRESHOLD / 两段式缓冲池；
• 锁 = 加在索引项上。

接下来，是全文最实用的一部分：把这棵树的结构，直接翻译成 MySQL 优化规则。

九、从 B+ 树推出 MySQL 优化规则

前面八节讲的是"树长什么样"。这一节做一次翻译练习：把树的物理结构，逐条翻译成 MySQL 的优化规则。

阅读方法：每一条规则都按同一个模板讲——

1. 树上的原因：这条规则为什么从 B+ 树的结构里必然成立；
2. 能用的写法 / 用不上的写法：正反两个 SQL 例子；
3. 怎么验证：EXPLAIN 里该看哪个字段。

规则很多，但它们只回答两个问题：A 组问"这棵树的顺序，你的查询用得上吗"；B 组问"用哪棵树、值不值得回表"。 后面 C、D、E 三组分别讲维护成本、排序分页、锁。

9.1 A 组：这个查询，能用上索引的"序"吗？

规则 A1：联合索引必须"从左到右"地用——最左前缀

树上的原因。 一个联合索引 (city, age) 不是"两个独立的索引"，而是把 (city, age) 这个元组按字典序排成一棵树：

先按 city 排；city 相同的，再按 age 排。
（杭州, 20）<（杭州, 25）<（杭州, 30）<（上海, 18）<（上海, 22）……

这就像电话簿"先按姓排，姓相同再按名排"。查"姓张的人"可以；查"名字叫伟的人"不行——因为名字在全局没有排序。注意"最左"指的是索引定义里的列顺序，不是 SQL 里 WHERE 的书写顺序，优化器会自动调整等值条件的顺序。

验证：EXPLAIN 的 type 从 ALL（全表）变成 ref / range，key 显示用上的索引，rows 明显变小。

设计含义：联合索引的列顺序不是随便写的。把区分度最高的等值列放最左，通常能让 rows 降得最多。

规则 A2：范围查询"截断"了后面的列

树上的原因。 看索引 (city, age, name)。查询：

WHERE city = '杭州' AND age > 18 AND name = '张三'

树的结构决定了：在"杭州"这一段里，记录按 age 排；age 相同的才按 name 排。而 age > 18 会跨越多个 age 值，每换一个 age 值，name 就从无序重新开始。优化器没法把 name = '张三' 变成一个"连续区间"，只能：

• 用 (city, age) 定位到起点 (杭州, 19)；
• 往后扫描所有 city = '杭州' AND age > 18 的记录；
• 对每条记录检查 name = '张三'。

这里 age 是"范围列"，它后面的列在定位阶段就废了。这就是常说的"范围之后的列失效"。

正确设计：等值列在前、范围列在后。上面这个查询，(city, name, age) 更好：city、name 两个等值定位，age 只剩一个区间。

有一个例外值得知道：MySQL 8.0.13 起支持 Skip Scan（跳扫）。如果最左列基数极低（比如只有几个值），优化器可以"跳过"它，对每个值分别用后面的列做范围扫描。EXPLAIN 里显示 Using index for skip scan。它是优化器的补救，不是设计索引的理由。

规则 A3：别在索引列上做运算或套函数

树上的原因。 索引是按列的原值排序的。WHERE YEAR(created_at) = 2023 里，树里存的是 created_at 的完整时间，没有"年份"这一列的排序。数据库只能把每一行的 YEAR() 算出来再比较——树用不上了。

-- ❌ 索引失效：对列做了函数运算
SELECT * FROM orders WHERE YEAR(created_at) = 2023;

-- ✅ 改写成对常量的范围比较
SELECT * FROM orders
WHERE created_at >= '2023-01-01' AND created_at < '2024-01-01';

同样的道理：WHERE amount * 2 > 100、WHERE DATE(created_at) = '2026-10-01'、WHERE SUBSTRING(name,1,1) = '张' 全部失效。

如果业务上确实必须按函数结果查，MySQL 8.0.13+ 可以建函数索引（本质是把函数结果作为 key 存进树里）：

ALTER TABLE orders ADD INDEX idx_year ((YEAR(created_at)));

验证：EXPLAIN 里看 type 是否退化成 ALL；key 为 NULL 就是没用上索引。

规则 A4：隐式类型转换，等于在列上套了一层函数

树上的原因。 还是同一句话：索引按列的原值排序。如果 phone 是 VARCHAR，而查询写的是：

-- ❌ phone 是字符串，右边是数字
SELECT * FROM users WHERE phone = 13800138000;

MySQL 会把字符串列转成数字再比较（CAST(phone AS DOUBLE)），每一行都要转换，树自然用不上。反过来，id BIGINT = '123' 没问题：把常量字符串转成数字是一次性的，不影响索引。

规则：等号两边的类型必须一致。字符串列就加引号，数字列就写数字。这是线上最隐蔽的索引失效原因之一——SQL 能跑、结果也对，就是慢。

规则 A5：LIKE 只有"前缀匹配"能走索引

树上的原因。 字符串索引按完整字符串的字典序排列。

• LIKE '张%'：所有"以张开头的字符串"在树里是连续的一段，等价于范围 ['张', '张' + 最大字符)，能定位 ✅；
• LIKE '%张' / LIKE '%张%'：结尾或中间匹配的字符串在树里分散在各处，无法定位起点 ❌。

-- ✅ 前缀匹配：走范围扫描
SELECT * FROM users WHERE name LIKE '张%';

-- ❌ 前后通配：全表扫描
SELECT * FROM users WHERE name LIKE '%张%';

补救手段：把"包含匹配"换成全文索引（FULLTEXT）或搜索引擎（ES）；如果只是想查后缀，可以额外存一列"反转后的字符串"再前缀查（经典技巧）。

另外注意 collation（排序规则）：utf8mb4_general_ci 大小写不敏感、_bin 区分大小写。索引的"序"是按 collation 定义的，比较时的 collation 不一致也会导致索引失效（常见于 JOIN 两张表字符集不同）。

规则 A6：OR、!=、IS NULL 的真实表现

树上的原因。 B+ 树擅长"一个连续区间"。

• WHERE a = 1 OR b = 2：如果两列各自有索引，MySQL 可以走 index merge（分别扫两棵树再合并）；如果只有部分有索引，通常退化成全表扫描。更好的写法是 UNION ALL 或重新设计联合索引；
• WHERE status != 'DONE'：!= 等于"取反的两个区间"，如果这两个区间很大，优化器宁可直接全扫；
• WHERE col IS NULL：这个能走索引——NULL 也是索引里的一个值（InnoDB 在索引记录里存 NULL 标记），IS NULL 等价于等值查询。不要被"NULL 不走索引"的传言误导（那是 Oracle 的部分行为，不是 InnoDB）。

验证：看 EXPLAIN 的 type 是否 index_merge、range，以及 rows 的估计值。

规则 A7：字符集/排序规则不一致的 JOIN，会让索引失效

树上的原因。 两棵树的"序"必须按同一种规则排。如果 users.name 是 utf8mb4_general_ci，orders.user_name 是 utf8mb4_bin，JOIN 时 MySQL 需要做隐式转换，orders.user_name 上的索引就用不上了。

规则：同一业务字段在关联表里用同一字符集、同一 collation；建表时显式写 CHARACTER SET utf8mb4 COLLATE utf8mb4_0900_ai_ci（MySQL 8.0 默认），别依赖库的默认值。

A 组一句话总结：

B+ 树只能回答"在它排好的那个序上，你要的东西是不是一个连续区间"。 最左前缀、范围截断、函数、类型、LIKE、OR、字符集——七个坑，全是同一个问题的七种问法。

9.2 B 组：用哪个索引？——成本模型与"回表"问题

A 组解决"能不能用"，B 组解决"用哪个、值不值"。

InnoDB 优化器选索引的依据是成本，而成本基本上就是"要读多少页 + 要回表多少行"：

总成本 ≈ 扫描索引页的成本 + 回表读聚簇索引页的成本 × 回表行数

回表是 B+ 树查询里最贵的一步（第二次树下降 + 随机 IO），所以这一组的规则几乎都围绕"减少回表"。

规则 B1：区分度（选择性）决定索引值不值得用

树上的原因。 索引的叶子按列值排序。如果一列只有 2 个值（性别），那么"定位到起点"之后，你要扫的是一半的索引页，而且每一条都要回表——回表 50% 的行，不如直接全表顺序扫描。

区分度公式：

$$ \text{区分度} = \frac{\text{COUNT(DISTINCT col)}}{\text{COUNT(*)}} \quad 0 < \text{区分度} \le 1 $$

• 接近 1（如手机号、订单号、主键）：优秀；
• 接近 0（如性别、状态、是否删除）：通常不该单独建索引，除非配合其它列组成联合索引。

为什么优化器会"拒绝"用索引：不是它坏，而是在它估算的成本里，走索引 + 大量回表 > 全表扫描。这也解释了为什么同一个索引，查 1 行时走索引、查 50 万行时改走全表——不是索引坏了，是成本模型在起作用。

验证：EXPLAIN 的 rows 是估算要检查的行数；filtered 是过滤后剩余的百分比。rows × (1 - filtered) 很大时，索引的意义就不大。

规则 B2：联合索引的列顺序设计（等值 → 排序 → 范围）

树上的原因。 联合索引的排序是"从左到右的字典序"。所以列顺序应该匹配查询的访问模式：

这套顺序在社区里叫 ESR 原则（Equality, Sort, Range）。注意两个细节：

• 多个等值列之间，区分度高的放前面通常更好（能用更少的行进入下一列）；
• 范围列只能有一个"有效"（第一个范围列之后的列不能再用于定位），所以范围列尽量只留一个。

例：查询"杭州的用户里，2026 年 9 月之后创建的，按创建时间排序"：

SELECT * FROM users
WHERE city = '杭州' AND created_at >= '2026-09-01'
ORDER BY created_at;

索引 (city, created_at) 就是最优：等值 city 定位，created_at 既做范围又做排序，排序完全免费。如果写成 (created_at, city)，city 的等值就用不上了。

规则 B3：覆盖索引——让查询"不用回表"

树上的原因。 二级索引的叶子只有"索引列 + 主键"。如果 SELECT 要的列全在这棵二级索引里，数据库读完二级索引就够了，不需要再去聚簇索引取行。

-- 需要 name（不在索引里）→ 回表
SELECT id, name FROM users WHERE city = '杭州';

-- 只要 city、age（都在 idx_city_age 里）→ 覆盖索引，不回表
SELECT city, age FROM users WHERE city = '杭州';

EXPLAIN 的 Extra 显示 Using index 就是覆盖索引。它的收益有两层：

1. 省掉回表的第二次树下降；
2. 二级索引页通常比聚簇索引页窄，同样多的数据读更少的页。

代价：索引变宽 → 页变多 → 写放大和缓存压力变大。所以"覆盖索引"不是让你把所有列都塞进索引，而是针对高频查询，把 SELECT 需要的那几列刚好放进索引。

规则 B4：索引条件下推（ICP）——在索引层先过滤，再回表

树上的原因。 有些条件里的列在索引中，但无法用于定位（典型的是范围截断后面的列）。InnoDB 的做法是：先在索引页里用这些列做过滤，只把真正可能命中的行拿去回表。

-- 索引 (city, age, name)：age 范围之后的 name 无法定位
SELECT * FROM users
WHERE city = '杭州' AND age > 18 AND name LIKE '张%';

没有 ICP 时：把所有 city = '杭州' AND age > 18 的行全部回表，再过滤 name；有 ICP 时：在索引页里就把 name 过滤掉，大幅减少回表次数。

EXPLAIN 的 Extra 显示 Using index condition 就是 ICP 生效（它和覆盖索引的 Using index 是两回事：ICP 仍要回表，只是回表变少了）。MySQL 5.6 引入，默认开启。

规则 B5：MRR——把回表的随机 IO 排成"接近顺序"

树上的原因。 二级索引按索引列排序，取出的主键值是乱序的。按乱序主键回表，就是随机访问聚簇索引的叶子页——机械盘最怕这个。

MRR（Multi-Range Read） 的做法是：先把一批主键值在内存里排序，再按主键顺序回表。这样对聚簇索引的访问就从"随机跳"变成"沿叶子顺序走"，把随机 IO 变成近似顺序 IO。

• 对机械盘/高延迟存储效果明显，对全内存的 SSD 提升有限；
• 由 optimizer_switch 里的 mrr 控制，EXPLAIN 里可能显示 Using MRR；
• 常和 BKA（Batched Key Access）配合用于 JOIN。

规则 B6：索引列越短越好——前缀索引与索引长度

树上的原因。 回到第六节的扇出公式：一页能装多少 key，取决于 key 有多长。key 越短：

• 内部节点扇出越大 → 树越矮；
• 叶子页装更多索引项 → 同样行数读更少页；
• Buffer Pool 能缓存更多索引页 → 命中率更高。

对长字符串列（如 URL、邮箱、地址），可以只索引前缀：

ALTER TABLE users ADD INDEX idx_email_prefix (email(20));

选前缀长度的方法：逐步增加长度，直到 COUNT(DISTINCT LEFT(email, n)) / COUNT(*) 接近整列的区分度。代价是：前缀索引不能用于覆盖索引（因为叶子只存前缀，取不到完整值），也不能用于 ORDER BY / 精确等值以外的场景。

同时要避免"索引不必要的长列"：能给 VARCHAR(64) 就别给 VARCHAR(255)（虽然 InnoDB 变长存储，但前缀索引规划、临时表、排序内存都会受影响）；能用 INT 就别用 VARCHAR 存数字。

B 组一句话总结：

优化器在算一笔账：走这棵索引要读多少页、回表多少行。 你设计的每一个索引（列顺序、宽度、覆盖哪些列），都是在替它降低这笔账；区分度低、回表多、列太宽的索引，它迟早不用。

9.3 C 组：写路径——维护这棵树的代价

读优化关心"少读几页"，写优化关心"少改几页，别把树写碎"。

一条 INSERT 在 InnoDB 里要动的东西比想象中多：写入聚簇索引叶子 → 更新每个二级索引（每个都是一棵 B+ 树）→ 可能触发页分裂 → 写 redo log / undo log → 维护索引统计信息。B+ 树的所有写代价，都来自"要保持树的有序和平衡"。

规则 C1：自增主键 vs 随机主键

树上的原因。 主键是聚簇索引的 key，新行落在哪个叶子，取决于主键值：

• 自增主键：新值总是最大的，永远落在最右侧的叶子页。InnoDB 只需要在树的右边缘追加，页填充率能做得很高（接近 90%），几乎没有随机 IO；
• 随机主键（UUID）：新值落在树的任意位置。每次插入都要先在聚簇索引里找到目标叶子页（3 次下降）、在页中间插入；页满了就分裂，把一半记录搬到新页。整棵树被写得"七零八落"，页平均填充率只有 50%～70%，索引文件更大、缓存命中率更低；
• 二级索引的连带代价：二级索引叶子存的是主键值。主键用 BIGINT（8 字节）还是 CHAR(36)（36 字节），会直接影响所有二级索引的叶子宽度——36 字节的 UUID 让每个索引项多出 28 字节，索引页数变多、树变高、缓存更紧张。

这就是"主键要自增、要用窄类型"的完整理由：它不是为了"好看"，而是因为主键是聚簇索引的排序键，也是所有二级索引的引用值。

如果业务必须用 UUID，正确的做法不是换成随机 UUID 字符串，而是：

• 用 UUID v7 / ULID 这类"时间前缀有序"的 ID（前几位按时间递增，写入仍然近似顺序）；
• 用 BINARY(16) 存储，而不是 CHAR(36)；
• 或者保留自增主键做聚簇索引，把 UUID 放到一个普通唯一索引列上。

实测（同样的 30 万行、同样的批量插入方式、服务端纯 SQL 耗时取两轮中位）：

需要澄清一个常见误解：自增主键并不是"零分裂"——每新建一个叶子页就要分裂一次（673 次 ≈ 叶子页数），顺序插入只是把分裂都集中在树的右边缘、填充率高、随机 IO 少。随机 UUID 的分裂次数更多（1,788 次），而且分裂发生在整棵树的各个位置，页填充率更低、缓存命中更差——这才是它慢 7 倍的完整原因。

规则 C2：索引不是越多越好

树上的原因。 每个二级索引都是一棵独立的 B+ 树。一次 INSERT 要写 N 棵树：每棵树都要定位叶子页、插入记录、可能分裂、写日志。索引越多：

• 写放大：一次写变成 N 次索引维护；
• 缓存竞争：Buffer Pool 要同时缓存 N 棵树的页面，热数据的命中率被稀释；
• 优化器负担：可选索引变多，选错索引的概率也变大。

常见的经验值是：单表二级索引控制在 5 个以内；能不建就不建；能用联合索引解决的，不要建多个单列索引（联合索引的最左前缀可以覆盖单列查询，但反过来的代价更大）。

实测（同样插入 10 万行、同样的数据与批量大小）：

4 个二级索引让插入慢了 3.2 倍，并额外占用了 2.5 倍于数据的索引空间。这就是"索引不是免费的"最直接的量化。

规则 C3：删除不会让文件变小——碎片与 MERGE_THRESHOLD

树上的原因。 InnoDB 删除记录是标记删除（记录头里的 delete 位），空间先挂在页内的空闲链表上；只有当整页利用率低于 MERGE_THRESHOLD（默认 50%）时，才会尝试和相邻页合并、把页还给表空间。而表空间里的空闲页不会自动还给操作系统。

所以：

• 删掉大量行之后，SHOW TABLE STATUS 的 Data_free 会上升，但 .ibd 文件不会变小；
• 顺序写入再删除，树里留下大量"半满页"，查询扫描同样的行数要读更多页；
• 解决办法是重建：OPTIMIZE TABLE（本质是 ALTER TABLE ... FORCE，重建表 + 重建所有索引）、ALTER TABLE ... ENGINE=InnoDB，或者用 pt-online-schema-change / gh-ost 做在线重建。

这也是"按时间分区 + 删分区"在日志类业务里流行的原因：删分区是删文件，不是标记删除。

实测（一张 30 万行、无二级索引的表）：

删掉一半数据，表文件一个字节都没变小、Data_free 也没变；重建之后体积才减少约 63%（同一批数据 19 MB → 7 MB）。线上"表越来越大、越删越大"的现象，就是标记删除 + 碎片造成的。（实验机是共享宿主机，DELETE/OPTIMIZE 的绝对耗时波动极大（0.3–6.8 s / 16–100 s），所以这里只引用体积变化，不引用耗时。）

规则 C4：宽表和大字段，会同时伤害树高和缓存

树上的原因。 回到扇出公式：叶子每页能装的行数 = 页大小 / 行大小。行越宽：

• 叶子页数越多、树可能越高；
• 同样的 Buffer Pool 能缓存的行数越少，缓存命中率越低；
• TEXT/BLOB 超过行内阈值会触发行溢出（真实数据放到溢出页，本页只存 20 字节指针），读一行可能要多读几页；
• 如果这些大字段还参与了索引（尤其是长 VARCHAR），内部节点的扇出也会被拖小。

建议：冷热字段拆表（大字段单独放一张"详情表"）；SELECT 只取需要的列（这也是覆盖索引的前提）；索引列尽量用窄类型。

规则 C5：批量写、顺序写、少改索引列

树上的原因。 B+ 树对"顺序插入"最友好：

• 批量插入（多行 INSERT + 单事务）把多次页访问合并成一次，减少日志刷盘次数；
• 按主键顺序写（自增、时间有序）只碰最右页；
• 更新索引列的代价等于"删一条 + 插一条"，而且要在每个索引上做；所以 UPDATE 尽量只更新非索引列；如果必须更新热点索引列，考虑"先标记、后异步重建"；
• 大批量导入前可以临时关闭二级索引/唯一性检查（SET unique_checks=0; SET foreign_key_checks=0），导入后再重建索引，这比边导入边维护树快得多。

C 组一句话总结：

读是"沿树下降"，写是"维护树的有序"。 越随机、索引越多、行越宽、删除越多，维护成本越高。优化写路径的关键不是加速某一条 SQL，而是让写入尽量顺序、让索引尽量少而窄、让废弃空间及时回收。

9.4 D 组：排序、分组、分页——用"索引序"免费做事

B+ 树的叶子是有序链表，这意味着一件事：如果查询的排序需求和索引的顺序一致，排序就是免费的。

规则 D1：ORDER BY 能走索引，就不要 filesort

树上的原因。 沿着叶子链表读出来的数据，天然按索引列升序排列。所以：

-- idx_created(created_at) 存在：直接沿叶子链表读，没有任何排序
SELECT * FROM users ORDER BY created_at LIMIT 10;

-- 改写：用主键的天然顺序也能避免排序
SELECT * FROM users ORDER BY id LIMIT 10;

EXPLAIN 里如果 Extra 没有 Using filesort，说明排序被索引"免费"完成了。注意：

• 多列排序 ORDER BY city, age 需要 (city, age) 联合索引，且列顺序一致；
• 混合方向 ORDER BY a ASC, b DESC 需要 MySQL 8.0 的降序索引 (a ASC, b DESC) 才能完全走索引；
• ORDER BY 后面加函数（ORDER BY LOWER(name)）同样会让索引失效。

规则 D2：Using filesort 到底慢在哪

树上的原因。 如果排序用不上索引，MySQL 只能把满足条件的行读出来，在内存里排序（sort buffer），内存不够就落到磁盘临时文件。这里有两个成本：

1. 读行成本：如果是 SELECT *，可能还要回表；
2. 排序成本：$O(k \log k)$ 次比较，k 是结果行数。

LIMIT 并不能免除排序——ORDER BY ... LIMIT 10 仍然要找出前 10 名，只是排序算法可以优化成"堆排序 top-N"。优化方式不是改 SQL 写法，而是让排序有索引可用，或者先过滤（WHERE）再排序。

规则 D3：GROUP BY / DISTINCT 也吃"有序"

树上的原因。 如果 GROUP BY 的列在索引里有序，MySQL 可以"流式分组"：沿着索引扫一遍，相邻的相同值归成一组，不需要临时表；否则要建临时表 + 排序去重。

-- (city, age) 索引：按 city 分组可以边扫边分组
SELECT city, COUNT(*) FROM users GROUP BY city;

看 Extra 里有没有 Using temporary。如果分组列和索引顺序不一致（或用了函数），就会退化成临时表。

规则 D4：深分页为什么慢，以及两种正确写法

树上的原因。 LIMIT 1000000, 10 的语义是"跳过 100 万行，取 10 行"。B+ 树没有办法"瞬间跳到第 100 万行"——它只能从定位点开始沿叶子链表走 100 万步，而且如果是 SELECT *，每一步还要回表。树高没变，但步数是 $O(\text{offset})$。

两种解法：

-- 方法一：延迟关联（先用覆盖索引拿到主键，再只回表 10 行）
SELECT u.* FROM users u
JOIN (SELECT id FROM users ORDER BY id LIMIT 1000000, 10) t ON u.id = t.id;

-- 方法二：游标分页 / Seek Method（记住上一页的最后一个 id）
SELECT * FROM users WHERE id > 1234567 ORDER BY id LIMIT 10;

方法二把"偏移量"换成了"起点条件"，每一步都是 $O(h)$ 的树查找，翻到第几页都一样快。接口设计上，能用游标分页就别用 offset 分页。

规则 D5：COUNT(*) 为什么慢——它也要扫树

树上的原因。 InnoDB 的 B+ 树不维护"总行数"这个计数（因为 MVCC 下不同事务看到的行数不同）。COUNT(*) 只能真的去数：优化器会挑最小的那棵索引树做全索引扫描（EXPLAIN 里显示 Using index），扫的页数 = 那棵索引的叶子页数。

实测（100 万行表）：扫最小的二级索引 idx_gender 只要 895 页，而扫聚簇索引要 4947 页——差了 5.5 倍。这就是"COUNT(*) 慢"的真正原因，也是"建一个很窄的索引能让 count 变快"的原因。

规则 D6：MIN / MAX 是 B+ 树的"送分题"

树上的原因。 最小值在最左叶子、最大值在最右叶子，沿最左/最右指针下降 h 次就能拿到，不需要扫描整个索引。对应的优化规则：如果 MIN/MAX 走了索引，EXPLAIN 的 Extra 会显示 Select tables optimized away 或很低的 rows。

9.5 E 组：索引决定锁的范围

第八章已经说过：InnoDB 的锁加在索引记录上。这一组把它变成可操作的规则。

规则 E1：没有索引的 UPDATE / DELETE，锁的是全表

-- email 没有索引：全表扫描，扫描到的每一行都会加锁
UPDATE users SET status = 2 WHERE email = 'a@b.com';

在 RR 隔离级别下，全表扫描会锁住所有扫描过的记录（以及间隙）。并发一高，就是大面积锁等待、超时、死锁。给 WHERE 条件加上合适的索引，是"减少锁范围"最有效的手段。

规则 E2：唯一索引等值 vs 普通索引范围

• 唯一索引 + 等值命中：InnoDB 可以确定"只有一条"，只加记录锁；
• 普通索引 + 等值：可能有多条，还会加间隙锁（Next-Key Lock），锁住"这个值附近"的区间。

所以"能唯一就唯一"不仅省空间（不用存额外主键？不，二级索引都存主键），更是缩小锁范围。

规则 E3：索引失效 = 锁范围爆炸

WHERE 里对索引列做函数、隐式类型转换、LIKE '%x%'……这些让索引失效的写法，在读上表现为"慢"，在写上表现为"锁得多"。线上很多"偶发锁超时"，根因就是某个后台任务用了不走索引的 UPDATE。

规则 E4：死锁常常是"加锁顺序不一致"

两个事务分别按不同顺序更新两行（例如 UPDATE ... WHERE id=1 和 WHERE id=2 交叉），加锁顺序相反，就会互相等待。解决办法：按固定顺序访问（比如按主键排序后批量更新）、缩小事务、避免大范围扫描加锁。

E 组一句话总结：

索引的边界就是锁的边界。 读的页数、写的行数、锁的范围，都由"这条 SQL 能不能精确定位到 B+ 树的一小段"决定。

十、实验课：10 个场景，把 B+ 树看个明白

前面讲的规则，光看文字容易"哦，懂了"，一上生产就忘。这一节把文章里的表、索引和查询跑一遍，用实测数字对照树的结构。

实验环境（所有数字都来自这份真实实验，脚本在 research/lab/，可复现）：

说明：MariaDB 的 InnoDB 与 MySQL 8.0 的 InnoDB 在 B+ 树结构和这些查询的计划上基本一致，数字会因机器不同而不同；相对关系才是重点。统计值是采样估算，rows 可能有偏差（10.3 会看到一个例子）。全部数字来自 research/lab/FINDINGS.md，实验机是 2 核 / 3.5 GB 的小实例，绝对耗时不具备生产参考意义。

10.1 先学会读 EXPLAIN 的五个字段

记住一条：type=ALL 且 rows ≈ 表行数，说明树完全没用上；type=index 是"扫了整棵树/整个索引"，也不算好事；type=const/ref/range 才是树在干活。

10.2 实验一：一次主键点查，真的是 3 次页访问

SELECT * FROM users WHERE id = 500000;

id  select_type  table  type   key      key_len  ref    rows  Extra
1   SIMPLE       users  const  PRIMARY  8        const  1

树上的解释。 const 表示"等值命中唯一索引，最多一行"。InnoDB 从根页开始，比较、选子页，经过 3 个索引页（根 → 内部 → 叶子）到达目标行。这和第六节算出的"三层树"完全对上：一次点查 = 树高 = 3 次页访问。

物理读是 0，因为页都缓存了——这正是 8.6 节说的"内部节点和热叶子常驻 Buffer Pool"。

10.3 实验二：同一个索引，2 万行和 654 行，差了 170 倍

-- A：只用到联合索引的第一列（city 只有几十个取值，平均每个城市约 2 万行）
SELECT * FROM users WHERE city = 'Beijing';

-- B：两列都用上（数据生成方式导致 city/age 分布不均，Shanghai+30 命中 654 行）
SELECT * FROM users WHERE city = 'Shanghai' AND age = 30;

树上的解释。 两个查询都"用上了索引"，但代价天差地别：

• A 用第一列定位到 Beijing 那一段（约 2 万条），每条都要回表（第二次树下降），于是约 2 万次随机访问聚簇索引 → 5.4 万次页请求、1.15 秒；
• B 用两列精确定位到 654 条记录 → 1,762 次页请求、6.66 ms；
• 654 次回表 × 每次 3 页 ≈ 2,000 页，与实测的 1,762 页同量级（部分页命中缓存），说明成本大头就是"回表"。

这个实验同时说明两件事：

1. 最左前缀不是"用上索引"就够了：city 这种覆盖 2 万行的前缀，SELECT * 的回表代价可能比全表扫描还高；
2. 联合索引的第二列值钱：多一个等值列，把 2 万行变成 654 行，页请求降到 1/31、耗时降到 1/170。设计联合索引时，“还能不能再加一个等值列"往往比"加更多单列索引"有效。

另外注意：rows 估算是 42,958，实际只有 19,997——统计信息是采样估算的（innodb_stats_persistent_sample_pages 默认 20 页），大表上估计偏差很常见，必要时 ANALYZE TABLE 或调大采样页数。

10.4 实验三：跳过最左列，树直接"失效”

SELECT * FROM users WHERE age = 30;   -- idx_city_age 的第二列

type  key   rows      Extra
ALL   NULL  995,304   Using where

实际扫描 1,000,001 行，耗时约 165 ms。树上的解释：索引按 (city, age) 排序，age 在全局没有排序，优化器找不到起点，只能全表扫描。这就是 A1 规则。

10.5 实验四：范围之后的列，只能靠 ICP 缓解

SELECT * FROM users
WHERE city = 'Beijing' AND age > 25 AND name = 'user500000';

type   key           key_len  ref   rows    Extra
range  idx_city_age  134      NULL  36,694  Using index condition; Using where

树上的解释。 city='Beijing' 是等值、age>25 是范围：树能定位到 (Beijing, 26) 的起点，但 age 是范围，name 无法在树上定位，只能在索引页里过滤 age（ICP，Using index condition），再对剩下的 1.7 万行回表，在回表后过滤 name（Using where）。1.7 万次回表 = 4.3 万次页请求、近 1 秒。

怎么改：把高频等值条件放进联合索引，比如 (city, name, age) —— 前两列等值定位，age 只做范围，回表量从 1.7 万行降到个位数。ICP 只是"少回表"，不能"不定义索引"。

10.6 实验五：LIKE 的前缀，是"能不能定位"的分水岭

树上的解释。 'Bei%' 能翻译成连续区间 [Bei, Bej)，定位后顺序扫 47 页；%jing / %eij% 找不到区间起点，只能全表。这就是 A5 规则。注意即使 'Bei%' 走了索引，匹配 2 万行还是慢——范围大时，索引也只能帮你"少读一些页"，不能帮你"少读很多行"。

10.7 实验六：函数让索引失效，范围改写让索引复活

树上的解释。 created_at 的索引里存的是完整时间，没有"年份"这个排序维度，YEAR() 只能逐行算（Using where; Using index 说明是扫了整个索引再过滤）。改写成常量范围后，树能定位到 2023 年那一段，只扫 301 页、匹配 25 万行，快了约 3 倍、少读 3.8 倍页。

这也回答了一个常见疑问：为什么 WHERE DATE(col) = '2026-10-01' 慢、WHERE col >= '2026-10-01' AND col < '2026-10-02' 快？——前者是在列上套函数，后者是范围区间。

10.8 实验七：覆盖索引，把"两棵树"变成"一棵树"

命中 654 行的查询，只改 SELECT 的列：

-- 覆盖索引：只取索引里已有的列
SELECT city, age FROM users WHERE city='Shanghai' AND age=30;   -- Extra: Using where; Using index

-- 非覆盖：需要回表取整行
SELECT * FROM users WHERE city='Shanghai' AND age=30;           -- Extra: Using index condition

页请求差了 224 倍。 树上的解释：二级索引的叶子只有"城市 + 年龄 + 主键"，SELECT city, age 读完 654 条索引项、8 个索引页就够了；而 SELECT * 要拿 654 个主键回聚簇索引逐个再下降一次——654 × 3 ≈ 1,962 页，与实测 1,794 页同量级。

作为对照，单行等值查询的页请求（A.3 实验，100 次不同 key 平均）：

（单行场景的 9/6 里还包含优化器 index dive 等固定开销，所以不是 3；但差值 3 页 = 一次完整的聚簇索引下降，正好是一棵三层树的高度。行数越多，“覆盖 vs 回表"的差距越惊人：654 行时已经是 224 倍。）

10.9 实验八：排序要不要 filesort，差了数千倍

ORDER BY name 没有索引，MySQL 只能把 100 万行全读出来排序，耗时 1.88 秒；ORDER BY created_at 沿索引叶子链表读 10 行就停，0.4 毫秒——差了约 4,700 倍。

更细的一组对照：ORDER BY city, age 与联合索引顺序一致（40 页，0.59 ms）；ORDER BY age, city 与索引顺序不一致（4,947 页，1,825 ms，Using filesort）。排序的"免费"只对索引定义的顺序有效。

10.10 实验九：分组和去重也能"免费”

树上的解释。 两个查询都利用了"索引按 city 有序"：

• GROUP BY city 扫一遍 idx_city_age 就能边扫边分组（无需临时表，Using index），但扫了 100 万项，206 ms；
• DISTINCT city 更聪明：因为索引里 city 是排序的，只需要"跳着读"每个 city 的第一个值（loose index scan / Using index for group-by），51 个不同城市只读 153 页，0.58 ms。

这是 B+ 树"叶子有序"带来的又一个红利：只要查询关心的是"顺序上的第一/唯一值"，树就能跳过大量数据。

10.11 实验十：低区分度索引的两副面孔

SELECT COUNT(*) FROM users WHERE gender = 1;

type  key         rows      Extra
ref   idx_gender  497,652   Using index

同样的条件，如果换成 SELECT *（要回表）或范围放大到 50 万行，代价会迅速变大；我们的补充实验里，SELECT * ... LIMIT 1000 走了索引但页请求升到 1,041 页，强制索引反而比优化器自选更慢——区别就在"回表多少行"。

所以"性别索引没用"这句话，只在"要回表取整行"时成立。如果查询是 COUNT(*) 或只取索引列（覆盖），低区分度索引反而比全表扫描省页（463 页 vs 4,947 页）。

这提醒我们：索引的好坏不是绝对的，取决于查询要不要回表、以及一次查询要覆盖多少行。 优化器的成本模型就是在算这笔账。

10.12 把这一节的数字，对回树的结构

如果只记一句话：

EXPLAIN 里的每个数字，几乎都能换算成"要访问几个 B+ 树页"。优化 SQL 的本质，就是让这个数字变小。

十一、B+ 树的边界：它不是万能的

写到这里，很容易产生"B+ 树就是最好的索引结构"的错觉。它不是。它只是在"读多写少、要范围查询、要事务和锁"的 OLTP 场景下，综合得分最高的那一个。 换个场景，答案就会变。

11.1 为什么 MySQL 的 OLTP 主索引还是 B+ 树

把 B+ 树放进数据库的真实需求里，它满足的是一组"组合拳"：

1. 等值 + 范围 + 排序 + 前缀 + 最值都能高效支持——哈希和 LSM 都做不到这么全；
2. 支持"唯一性约束"的检查（唯一索引需要在树里定位后判断是否重复，这是事务语义）；
3. 锁是加在索引记录上的，页级结构配合行锁、间隙锁，能实现事务隔离；
4. 更新是"就地"的（改一行只改一个页附近），而 LSM 的更新是"追加 + 后续压缩"；
5. 成熟的缓存/恢复/统计体系（Buffer Pool、redo/undo、采样统计）。

11.2 三种"放大"，是一张跷跷板

任何存储结构都在三个成本之间取舍：

• 读放大：为了读到 1 行，实际读了多少数据（B+ 树回表、LSM 查多层）；
• 写放大：为了写 1 行，实际写了多少数据（B+ 树页分裂、LSM 压缩重写）；
• 空间放大：为了存 1 行，实际占了多少空间（索引副本、页填充率、LSM 的多版本）。

B+ 树在"读放大"上做得很好（$O(h)$ 次页访问），代价是"写放大"（分裂、多索引）和"空间放大"（索引页填充率只有 50%～70%）。LSM 反过来：写放大换读放大。没有银弹，只有匹配场景。

11.3 那什么时候该考虑别的

• 写入量极大（日志、埋点、消息）：优先 LSM 系（RocksDB/HBase/Cassandra），或先写 Kafka 再落库；
• 全文检索/模糊匹配：别硬用 LIKE '%x%'，用全文索引或 ES；
• 实时聚合分析：别在 MySQL 上扫大表做 GROUP BY，用列存（ClickHouse/Doris）或预聚合；
• 高并发点查 KV：Redis 或哈希索引；
• 向量相似度：专用向量库/插件。

反过来，只要你的场景是"按主键/时间/用户查少量行，还要事务"，B+ 树仍然是默认答案。

十二、速查表：症状 → 病因 → 处方

下面这张表把全文压缩成"急诊手册"。左边是现象，中间是 B+ 树视角的病因，右边是对应的处方。

建表/建索引检查清单（8 条）：

1. 主键用自增窄整型；必须用 UUID 时用有序版本 + BINARY(16)；
2. 单表二级索引不超过 5 个，优先联合索引；
3. 联合索引按 等值 → 排序 → 范围 排（ESR）；
4. 高频查询设计覆盖索引，避免 SELECT *；
5. 长字符串用前缀索引，先用 COUNT(DISTINCT LEFT(...)) 估长度；
6. 等值条件列放索引前面，范围条件列放最后；
7. 按时间增长的大表做分区/归档，别让 B+ 树无限长大；
8. 上线前用 EXPLAIN + EXPLAIN ANALYZE（MySQL 8.0.18+）看真实行数与页访问。

十三、收尾：把整篇文章压缩成一张图

回顾一下我们的推导链条，你会发现整篇文章其实是一条单向的因果链：

磁盘一次只能读一个 16KB 的页
        ↓
所以"树矮"比"比较次数少"重要
        ↓
二叉搜索树 25 层 → 淘汰；要让一页装下几百个路标
        ↓
B+ 树：内部节点只放 key（扇出大）+ 数据只在叶子 + 叶子链表
        ↓
一棵 3 层的树能装千万到上亿行，点查 = 3 次页访问
        ↓
InnoDB 把节点实现成 16KB 页：聚簇索引叶子存整行，二级索引叶子存主键
        ↓
于是有了回表、覆盖索引、页分裂、Buffer Pool、锁在索引项上
        ↓
所有优化规则 = 让查询匹配树的序 + 减少回表的页 + 降低维护树的成本

下面这张决策图，可以在遇到慢查询时按顺序问自己四个问题：

flowchart TD
    Q["一条 SQL 为什么慢？"] --> Q1{"1. 树能不能定位？<br/>EXPLAIN type 是 ALL/index？"}
    Q1 -->|"不能"| A1["改写查询条件：<br/>等值/范围/前缀/类型一致<br/>（第九章 A 组）"]
    Q1 -->|"能"| Q2{"2. 回表多少行？<br/>rows × filtered 大不大？"}
    Q2 -->|"多"| A2["覆盖索引 / 缩小索引范围 / ICP / MRR<br/>（第九章 B 组）"]
    Q2 -->|"不多"| Q3{"3. 有没有额外排序/临时表？<br/>Using filesort / temporary？"}
    Q3 -->|"有"| A3["让 ORDER BY / GROUP BY 匹配索引序<br/>（第九章 D 组）"]
    Q3 -->|"没有"| Q4{"4. 是写慢还是读慢？"}
    Q4 -->|"读慢"| A4["看缓存命中率、是否深分页、<br/>是否扫了太多叶子页"]
    Q4 -->|"写慢"| A5["顺序主键、减少索引、<br/>处理碎片、分批提交<br/>（第九章 C 组）"]

如果这篇文章你只能记住五句话，我希望是这五句：

1. 索引 = 为某一列维护的、排好序的 B+ 树；它用空间和写入成本，换取"按顺序快速定位"的能力。
2. B+ 树之所以"矮"，是因为一个节点正好是一页、内部节点只装路标；三层到四层就能覆盖千万到百亿行。
3. 查询快不快，取决于两件事：这棵树的"序"能不能被用上，以及要回表多少行。
4. MySQL 的所有索引优化规则，都能从"树的结构 + 页的布局"推出来，不需要背。
5. 每次看到 EXPLAIN，把它当成这棵树的"体检报告"：每个数字背后，都是要访问几个 16KB 的页。

最后送一句可能有点"大"的话：B+ 树本身并不难，难的是在物理约束下做权衡——磁盘慢就减少 IO、页为单位就让节点变大、写会碎裂就用填充率和合并阈值兜底、读要顺序就用链表串联。数据库的几十年演进，基本都是在回答同一类问题。理解了 B+ 树，你理解的不只是一种数据结构，而是一套"用工程手段对抗物理限制"的思维方式。

参考

参考

MySQL 8.0 手册：InnoDB 存储结构与索引

• The Physical Structure of an InnoDB Index：页默认 16KB、索引记录存叶子页、插入预留 1/16、MERGE_THRESHOLD 默认 50%
• Clustered and Secondary Indexes：聚簇索引=主键、无主键时的 GEN_CLUST_INDEX、二级索引叶子含主键
• InnoDB Row Formats：COMPACT/DYNAMIC、5 字节记录头、NULL 位图、20 字节溢出指针
• InnoDB Limits：key 前缀 3072B/767B、联合索引最多 16 列、每表最多 64 个二级索引、单行约半页
• File Space Management：表空间与页大小
• Configuring the Merge Threshold for Index Pages：MERGE_THRESHOLD 默认 50、取值 1–50
• InnoDB Startup Options and System Variables：page_size、buffer_pool_size、old_blocks_pct、stats_persistent_sample_pages 等默认值
• Configuring Optimizer Statistics for InnoDB：持久化统计与采样页数

执行计划与优化器机制

• EXPLAIN Output Format：Using index、Using index condition、Using filesort、Using index for group-by 等 Extra 语义
• Index Condition Pushdown Optimization：ICP 原理与 EXPLAIN 表现
• Multi-Range Read Optimization：MRR 与随机回表
• Block Nested-Loop and Batched Key Access Joins：BKA 与 join buffer
• Range Optimization（Skip Scan）：8.0.13+ 的跳扫
• Index Merge Optimization：多索引合并
• The Optimizer Cost Model：优化器如何按成本选索引

Buffer Pool、锁与并发

• The InnoDB Buffer Pool：两段式 LRU、midpoint 插入、old 子表 3/8
• Server Status Variables：Innodb_buffer_pool_read_requests（逻辑读）与 Innodb_buffer_pool_reads（物理读）
• InnoDB Locking：记录锁、间隙锁、Next-Key Lock、唯一索引等值降级
• Locks Set by Different SQL Statements in InnoDB：无索引全表扫描时"每行都被锁住"
• Transaction Isolation Levels：默认 REPEATABLE READ
• Change Buffer：二级索引写缓冲与 merge
• Adaptive Hash Index：内存哈希加速等值查询

版本差异

• MySQL 8.4 InnoDB Parameters：8.4 起 change_buffering=none、adaptive_hash_index=OFF
• MySQL 5.7 InnoDB Parameters：5.7 起 buffer pool 默认已是 128MB

MySQL 源码（页/记录格式的一手依据）

• fil0types.h：FIL Header 38B、FIL Trailer 8B
• page0types.h：Page Header 字段偏移、PAGE_LEVEL、infimum/supremum 偏移
• page0page.h：Page Directory 稀疏槽（2B/槽，每槽 4–8 条记录）
• rem0rec.ic：记录头 next_record 的 2 字节相对偏移

B+ 树理论与课程

• Bayer & McCreight, Organization and Maintenance of Large Ordered Indices (1972), Acta Informatica 1:173–189 — Springer
• Comer, The Ubiquitous B-Tree (1979), ACM Computing Surveys 11(2):121–137 — PDF 镜像（DOI 10.1145/356770.356776）
• Knuth, The Art of Computer Programming, Vol. 3: Sorting and Searching — TAOCP：§6.2.4 多路搜索树
• CMU 15-445/645 Tree Indexes 课件 与 第 9 讲
• UC Berkeley CS186 B+ Trees 笔记：另一种"阶"定义
• use-the-index-luke: The Tree：面向开发者的 B+ 树索引图解
• MariaDB: Row Size Too Large 排错：16KB 页下 8126 字节阈值说明

附录 A：术语表

附录 B：复现说明

本文的数字来自两套可复现的产物，都在仓库里：

B.1 B+ 树交互演示与测试（demos/bplus-tree/）

# 1) 打开交互演示（纯静态，无需构建；也可以用任意静态服务器）
cd demos/bplus-tree && python3 -m http.server 8000
# 浏览器打开 http://localhost:8000

# 2) 跑不变量/随机对拍测试（Node 22+）
cd demos/bplus-tree && node test.mjs

# 3) 重新生成文章里的三张 SVG 配图
cd demos/bplus-tree && node scripts/gen-figures.mjs

演示里可以手动插入/删除 key，步进播放分裂、借位、合并的每一步，并实时看到"树高、叶子填充率、一次查找要访问几个页"。

B.2 MySQL 实测实验（research/lab/）

实验用私有 MariaDB 10.11 实例（socket 方式启动，innodb_buffer_pool_size=96M、page_size=16384、query cache 关闭），脚本按 A（索引几何与页访问数）、B（EXPLAIN 对照）、C（自增 vs 随机主键）、D（索引数量 vs 写入）、E（Buffer Pool 命中率）分组，每组产出原始输出到 research/lab/results/：

# 启动实验实例（数据目录已初始化时）
cd research/lab && setsid --fork mariadbd --datadir="$PWD/mysql-data" \
  --socket="$PWD/mysql.sock" --port=3307 --innodb-buffer-pool-size=96M \
  --sort-buffer-size=1M --join-buffer-size=1M --skip-log-bin

# 重跑全部实验（会重建 lab 库）
cd research/lab && ./run-all.sh

实验结果汇总在 research/lab/FINDINGS.md，包含每个实验的 SQL、原始输出摘录和"可引用数字"表。

B.3 版本与口径说明

• 数据库为 MariaDB 10.11.14（InnoDB），不是 MySQL 8.0；两者在 B+ 树结构、页格式、聚簇/二级索引、ICP 等核心机制上一致，但优化器成本模型、部分 EXPLAIN 输出格式和默认参数有差异，绝对耗时不可直接搬到 MySQL；
• 实验机器是 2 核 / 3.5 GB 内存的小实例，Buffer Pool 只有 96 MB，因此"全表扫描"的物理读和耗时会被放大；文章引用时已尽量只用相对关系；
• 文中"三层树 2000 万行"是在 1 KB 行、8 字节主键、1170 扇出假设下的估算，真实表要按第六节的公式代入自己的行宽和主键宽度重算。