为什么 B+树索引要求最左前缀？从数据结构推导 MySQL 索引规则

接触 MySQL 索引的时候，大部分人应该都背过这三条规则：

• 联合索引必须遵守最左前缀原则
• LIKE '%abc' 不走索引
• 对字段使用函数（UPPER(col)、YEAR(date)）不走索引

背归背，很少人真正想过：为什么？

这其实都是同一个数据结构推导出来的结论。如果能把这个数据结构理解透，你就不再需要背规则，自己就能重新推出来。

为什么是 B+树？先从磁盘的物理限制说起

每次读磁盘都是一个物理动作。磁头要挪到正确的位置，盘片要旋转到正确的扇区。

在现代硬件上，一次随机磁盘 IO 的延迟大概是：

• CPU 读寄存器：~1ns
• CPU 读内存：~100ns
• 读 SSD（一次随机 IO）：~100μs
• 读机械硬盘（一次随机 IO）：~10ms

内存和磁盘之间差了 1000 到 100000 倍。所以数据库的第一设计原则就是：尽量减少磁盘 IO 次数。

这就是为什么 B+树，而不是二叉树。

二叉树存 100 万条数据，高度大约 20 层。查一次数据，最坏要走 20 次磁盘 IO，每次 IO 都要在树里走一步。20 × 10ms = 200ms。一个简单的 SELECT 就卡 200ms。

B+树的每个节点是一个 16KB 的 页（Page），可以存几百个"路标"条目。100 万条数据，B+树的高度只有 3 到 4 层。查一次数据只需要 3 到 4 次磁盘 IO。

高矮之比：20 层 vs 3 层。这就是 B+树胜出的根源。

B+树的结构

B+树最核心的特征：只有叶子节点存完整数据，非叶子节点只存"路标"（也叫目录项）。

非叶子节点里的路标用来导航。走到一个非叶子节点，你看看当前值应该往左走还是往右走，缩小范围。一路走到叶子节点，找到真正的数据行。

叶子节点之间还有双向链表串联，方便做范围扫描。

联合索引在 B+树里排列

假设有个联合索引 (a, b, c)。叶子节点里存的是 (a, b, c, 主键) 这样的元组。这个元组按什么顺序排列？

字典序。

字典序的规则很简单：先比第一个分量（a），a 相同再比第二个分量（b），a 和 b 都相同再比第三个分量（c）。就像查英文词典，先比首字母，首字母相同再比第二个字母。

假设表里有这么 7 行数据：

a	b	c
1	1	A
1	1	B
1	2	A
2	1	A
2	1	C
2	3	B
3	1	A

它们在 B+树叶子节点里的排列顺序就是：

(1,1,A) → (1,1,B) → (1,2,A) → (2,1,A) → (2,1,C) → (2,3,B) → (3,1,A)

验证一下：(1,1,A) 和 (1,1,B) —— a 都是 1，相等；b 都是 1，相等；c 是 A < B，所以 A 在前。(2,1,A) 在 (1,2,A) 后面 —— a：1 < 2，所以 (1,2,A) 排在前面。完全符合字典序。

最左前缀规则是怎么来的？

看非叶子节点里的路标。一个索引 (a,b,c)，非叶子节点里存的也是一组 (a,b,c) 元组，用来指示往哪棵子树走。

现在你执行查询 WHERE a = 2 AND b = 1 AND c = C。

InnoDB 在非叶子节点里看到一个路标 (1,2,A)，拿你的 (2,1,C) 跟它比。比第一个分量：2 > 1，走右边。再看到路标 (2,1,C)，比 a：2 == 2，比 b：1 == 1，比 c：C == C，命中，走向对应的子页。

每次比较都是从第一个分量开始比。这正是 B+树能快速定位的核心。

现在你执行 WHERE b = 1 AND c = C（没有 a）。非叶子节点里的路标是 (1,2,A)、(2,1,C)、(3,1,A)。你手里拿着 (?, 1, C)。第一个分量是空的，没法跟 (1,2,A) 的第一个分量比大小。

InnoDB 不知道应该走左子树还是右子树。它唯一的办法就是全索引扫描——把整个 B+树的叶子节点全部遍历一遍。

这就是最左前缀规则的本质：B+树的节点按元组字典序排列，少了左边分量就无法在树上做二分定位，只能全扫。

LIKE '%xx' 为什么不走索引？

WHERE c LIKE '%abc' 等价于搜索后缀。和上面一样，你不知道第一个字符是什么，也就没法确定应该往 B+树的哪棵子树走。

反过来，WHERE c LIKE 'abc%' 是能走索引的。InnoDB 可以定位到 (abc...) 的起始位置，然后利用叶子节点的双向链表做范围扫描——从 'abc' 开头的最小的值开始往后扫，直到遇到一个不匹配 'abc%' 的值为止。这正是 B+树最擅长的操作：先用树结构定位起始点，再用链表做范围遍历。

函数为什么导致不走索引？

WHERE UPPER(name) = 'JOE'

索引里存的 name 的值，不是 UPPER(name) 的值。非叶子节点的路标也是按原始的 name 排序的，不是按 UPPER(name) 排序的。

举个例子，索引里 name 的排序是：'Alice' < 'Bob' < 'Joe'。但你想要找 UPPER(name) = 'JOE'。UPPER('Alice') 不等于 'JOE'，UPPER('Bob') 不等于 'JOE'……InnoDB 没法利用排序关系，只能把每一行取出来，算一遍 UPPER(name)，再比较。这是全表扫描。

更典型的例子是 WHERE YEAR(date) = 2024。索引按完整日期排序：2023-12-01、2024-01-15、2024-06-30……排序是按日期的大小，而不是按年份。YEAR() 函数完全打破了 B+树的排序关系，优化器无法利用索引做范围过滤。

MySQL 的优化器不会去证明"某个函数保持排序关系"。只要字段套了函数，一律放弃索引。

一条线串起来

这三条规则的本质是同一个：

磁盘 IO 太慢 → 需要矮的树 → B+树 →
 → 元组按字典序排列 →
 → 缺左边分量无法定位（最左前缀）→
 → 前缀未知无法定位（%xx）→
 → 函数破坏排序关系无法定位（函数）

以后你碰到任何跟索引失效有关的场景，问自己一个问题：InnoDB 还能不能利用这个元组的字典序，在 B+树上做二分定位？

能，就用索引。不能，就全扫。

进阶预告

理解了 B+树和字典序之后，再往下可以聊：

1. 聚簇索引 vs 二级索引 —— 主键 B+树的叶子节点存整行数据，二级索引的叶子节点存主键值。查二级索引后还要"回表"查主键索引才能拿到完整数据。
2. 覆盖索引 —— 如果查询的字段恰好都在索引里，就不用回表，直接走索引就能拿到结果。这就是 EXPLAIN 里显示的 Using index。
3. 页的内部结构 —— InnoDB 的一个 16KB 页到底怎么组织几百个路标条目，为什么一次磁盘 IO 就能读这么多数据。
4. **MRR（Multi-Range Read）**和 ICP（Index Condition Pushdown）—— MySQL 怎么在这些规则上做优化。

这些下次再聊。