"加个索引"几乎是所有慢查询的第一反应。但索引为什么能加速?为什么联合索引有"最左前缀"这条铁律?为什么有的查询明明加了索引却走不上?要回答这些,必须理解 MySQL(InnoDB)索引底层的数据结构——B+ 树。它不是普通的二叉树,而是为磁盘场景量身定制的多叉平衡树。

为什么是 B+ 树,而不是别的树

索引的本质是用空间换时间,把"全表扫描 O(N)“变成"树查找 O(log N)”。但能做查找的树很多,为什么偏偏是 B+ 树?核心原因是:索引数据存在磁盘上,瓶颈是磁盘 I/O 次数,而不是 CPU 比较次数。

  • 二叉搜索树/红黑树:每个节点只存一个 key,树高随数据量快速增长。百万级数据树高可能二十层,意味着最坏情况几十次磁盘 I/O,无法接受。
  • B 树:多叉,每个节点存多个 key,树更"矮胖",I/O 次数少。但 B 树的每个节点(包括非叶子节点)都存数据,导致单个节点能容纳的 key 变少,树会变高。
  • B+ 树:在 B 树基础上做了两个关键改进。

改进一:数据只存在叶子节点,非叶子节点只存 key(索引)。 这样非叶子节点不背数据负担,一个 16KB 的页能塞下更多 key,扇出(fan-out)更大,树更矮。InnoDB 一个页 16KB,假设一个索引项约十几字节,一个非叶子节点能存上千个 key。三层 B+ 树就能索引千万级数据,意味着一次主键查找通常只需 2~4 次磁盘 I/O(且根节点常驻 Buffer Pool)。

改进二:所有叶子节点用双向链表串联,且叶子内记录有序。 这让范围查询极其高效:找到范围起点后,顺着叶子链表横向扫描即可,不用回到树根反复查找。WHERE age BETWEEN 20 AND 30 这类查询,B+ 树的链表结构天然友好,而 B 树做范围查询要中序遍历、来回跳节点。

1
2
3
4
5
        [ 50 | 100 ]                  ← 非叶子节点:只存 key 做导航
       /     |      \
   [...]   [...]   [...]
     ↓
[10|20|30] ⇄ [60|70|80] ⇄ [110|...] ← 叶子节点:存完整数据,双向链表串联

聚簇索引与二级索引:回表从哪来

InnoDB 的主键索引是聚簇索引(clustered index):叶子节点直接存放整行数据。表的数据本身就是按主键组织的一棵 B+ 树。所以用主键查找,到叶子节点就拿到了完整行,一步到位。

而二级索引(secondary index,即普通索引) 的叶子节点存的不是整行,而是索引列 + 主键值。所以用二级索引查询时,先在二级索引树里找到主键值,再拿这个主键去聚簇索引树里查一次完整行——这个过程叫回表(回到主键索引取数据)。

回表意味着两次 B+ 树查找,有额外开销。这就引出了覆盖索引(covering index) 的优化:如果查询需要的列恰好都在二级索引里(索引列 + 主键),就不必回表了。

1
2
3
4
5
6
7
8
9
-- 建联合索引
CREATE INDEX idx_name_age ON users(name, age);

-- 覆盖索引:select 的列都在索引里(name, age, id 主键),无需回表
-- 执行计划 Extra 会显示 Using index
SELECT id, name, age FROM users WHERE name = 'Alice';

-- 需要回表:address 不在索引里,必须拿主键回聚簇索引取
SELECT id, name, address FROM users WHERE name = 'Alice';

最左前缀原则:联合索引的排序规则

联合索引 (a, b, c) 在 B+ 树里不是建了三棵树,而是一棵树。它的排序规则是:先按 a 排序;a 相同的再按 b 排序;a、b 都相同的再按 c 排序。就像字典里先按首字母排,首字母相同再看第二个字母。

这个排序规则直接决定了"最左前缀原则":索引的有序性,只在按从左到右连续的列前缀使用时才成立。

  • WHERE a = 1 ✔ 走索引(a 是有序的)
  • WHERE a = 1 AND b = 2 ✔ 走索引(a 定了之后 b 也有序)
  • WHERE a = 1 AND b = 2 AND c = 3 ✔ 完整命中
  • WHERE b = 2 ✘ 用不上索引(脱离 a,b 在全局是无序的)
  • WHERE a = 1 AND c = 3 ⚠ 只能用到 a 部分,c 用不上索引过滤(b 缺失,c 在 a 内部无序)

为什么 b 单独查不行? 因为整棵树是先按 a 排的,b 只在"a 相同"的局部内才有序。脱离 a,所有 b 值在物理上是散乱分布的,无法用树的有序性做二分定位,只能全索引扫描。

范围查询会"截断"索引

最容易踩的坑:范围查询(>, <, BETWEEN, LIKE 'xx%')会终止后续列对索引的使用。

1
2
3
4
-- 索引 (a, b, c)
SELECT * FROM t WHERE a = 1 AND b > 5 AND c = 3;
-- a 等值命中,b 范围命中,但 c 用不上索引过滤!
-- 因为 b 一旦是范围,满足 b>5 的记录里 c 是无序的

原因同样是排序规则:在 a=1 的范围内,记录按 b 排序;但当 b 是一个范围(b>5)时,这个范围内的 c 不再有序(每个不同 b 值下 c 各自有序,但跨 b 值整体无序)。所以 c 无法继续用索引定位。

优化启示:设计联合索引时,把等值查询的列放左边、范围查询的列放右边。WHERE a = ? AND b = ? AND c > ? 就能让索引 (a, b, c) 完整发挥。

工程权衡与常见误区

  1. 索引不是越多越好。 每个二级索引都是一棵独立的 B+ 树,占额外空间,且每次 INSERT/UPDATE/DELETE 都要维护所有相关索引树(可能引发页分裂、页合并),拖慢写入。读多写少加索引划算,写密集场景要克制。
  2. 失效陷阱。 索引列上做函数运算或类型转换会导致索引失效,因为 B+ 树存的是原始值的有序结构,WHERE YEAR(create_time) = 2025 没法用 create_time 的索引,应改写成 create_time >= '2025-01-01' AND create_time < '2026-01-01'。隐式类型转换(字符串列传数字)同理。
  3. LIKE '%xx' 用不上索引。 前导通配符破坏最左前缀的有序性;LIKE 'xx%' 则可以用(本质是一个范围)。
  4. 页分裂与主键选择。 聚簇索引按主键有序插入。用自增主键时新数据总是追加到最后,很顺;用随机 UUID 做主键会导致频繁在中间插入,引发页分裂、碎片化,写性能和空间利用率都变差。这是 UUID 主键的经典坑。
  5. 回表代价被低估。 二级索引命中很多行又都要回表时,优化器可能直接放弃索引改走全表扫描——因为大量随机回表的 I/O 还不如顺序全扫快。这不是 bug,是优化器基于成本的合理选择。

小结

B+ 树是为磁盘而生的索引结构:矮胖的多叉树压低 I/O 次数,数据下沉叶子让非叶子节点装更多 key,叶子链表让范围查询飞快。聚簇索引让主键查找一步到位,二级索引则带来回表与覆盖索引的取舍。而最左前缀原则、范围查询截断这些规则,归根结底都源于联合索引"从左到右逐级排序"这一条物理事实。把索引底层的有序性想清楚,什么查询能命中、为什么失效,就都不再是需要死记的八股,而是可以推导的结论。