系列目录
- MySQL 索引与慢查询：B+ 树如何减少扫描（本篇）
文件列表越来越慢
云盘 Java 版上线后，文件列表接口随单用户文件数增长越来越慢。页面打开要等好几秒，监控里这条接口的 RT 明显高于其他接口。慢查询日志定位到一条 SQL，按记忆重构大致是：
SELECT id, uid, name, size, update_time
FROM file_meta
WHERE uid = ? AND deleted = 0
ORDER BY id DESC
LIMIT 20;EXPLAIN 的结果里 type 是 ALL、key 为 NULL、rows 是整张表的行数，Extra 里没有 Using index 一类标记——标准全表扫描。这几列我看得懂，「没走索引」这个结论也明确；但 type 从 ALL 变成 ref 究竟意味着访问路径换掉了哪一段，我那时还说不清。
看了下慢查询日志建议增加联合索引 (uid, deleted, id)。加上之后，type 变为 ref，rows 降到个位数，接口 RT 也随之回落。当时我知道索引可以加速查询，但说不清为什么要按这三列组合，以及为什么查询条件变化后同一个索引不能继续提供有效的访问路径。
本文说明索引减少扫描的原因，以及查询无法有效利用索引的条件。
B+ 树的扇出与树高
索引维护有序结构，让查询不必逐行扫描。InnoDB 用 B+ 树。理解 B+ 树需要先考虑页读写：磁盘读写以页为单位，InnoDB 默认页大小为 16KB。一次页读取的 I/O 开销主要由页读取决定，而不取决于页内装了多少行。因此，减少 I/O 次数通常比减少逻辑比较次数更能缩短查询耗时。
二叉平衡树每个节点只放一个键，扇出为 2；树高随数据量按 log₂ 增长，路径每增加一层就可能增加一次页读取。B+ 树的非叶子节点只存键和指针，不存整行数据，一个 16KB 页可容纳数百到上千个键，因此扇出更高，数据存放在叶子节点。同样是对数增长，底数从 2 增加到数百时，三层（根、中间、叶子）可以覆盖千万级行数。根页和中间页通常留在内存中，访问叶子页时才可能需要磁盘读取，因此查询路径上的 I/O 次数更少。
维护 B+ 树的有序性会增加写入成本。每次写入都要维护树的有序性：新行插入到对应的叶子页，页写满要一分为二（页分裂），向上传播键。写入比无索引时多出维护索引的代价，页分裂还会带来空间碎片和写放大。索引用写入开销和存储空间换取查询路径上的有序性。
聚簇索引与二级索引。 InnoDB 的主键索引就是聚簇索引，叶子节点直接存整行数据。二级索引的叶子节点只存主键值，不存整行数据。通过二级索引找到匹配项后，需要用主键在聚簇索引中定位整行数据。这个过程称为回表，是额外的一次按主键查找。
二级索引命中大量行时的回表。 如果一条查询通过二级索引命中大量行，每一行都需要回表一次，累积的随机 I/O 成本可能高于全表扫描。覆盖索引可以避免回表：查询字段全在某个二级索引里时，直接从索引叶子页取数据，不用回聚簇索引。select uid, name from ... where uid=? 配 (uid, name) 索引就是覆盖索引。
存储引擎在索引页过滤条件（索引下推）。 MySQL 5.6 引入了 Index Condition Pushdown。在 5.6 之前，联合索引 (a, b) 上 where a=? and b like '%x' 这种条件，存储引擎只能用 a 的等值定位到索引段，把每条主键都回表取整行，再由 server 层过滤 b。5.6 之后，server 层把 b 的过滤条件下推到存储引擎层，直接在索引叶子页上判断 b，不满足的不回表。回表次数从「a 命中行数」降到「a 且 b 命中行数」。a 等值段内 b 本身有序，但前导模糊的 like 无法利用这个顺序定位，仍需逐条判断；这个判断在索引页上就能完成，不必回表。ICP 减少回表次数，定位方式仍依赖 a 的等值条件。
联合索引的字典序
联合索引 (a, b) 先按 a 排序，a 相同再按 b 排序。这是字典序：比较时先比较 a，再比较 b。这个排列规则决定了联合索引能利用哪些查询条件。
最左前缀。 where b=? 无法使用 (a, b) 索引的有序性。跳过 a 后，b 在整个索引中不再有序：每个 a 值内部 b 有序，跨 a 值则无序。
范围条件后的列。 where a=? and b>? 里 a 是等值，先在索引里定位到 a 那一段，b 在这一段内有序，可以利用。where a>? and b=? 里 a 是范围扫描，扫过的多个 a 值各自内部 b 有序，合在一起 b 不再整体有序，无法利用 b 的索引顺序。某一列使用范围条件后，其右侧列无法利用索引有序性。
按索引顺序完成排序。 order by a, b 和索引排列方向一致时，可以直接顺着叶子链表读，不用额外排序（EXPLAIN 里没有 Using filesort）。order by b, a 的排序方向不一致，需要额外排序。
查询条件如何导致索引失效
后来又遇到一次「加了索引还是慢」。某张表的查询字段建了索引，EXPLAIN 仍然是全表扫描。原因是隐式类型转换。
uid 在表里是 varchar，查询时传了数字 uid = 123（没加引号）。MySQL 比较时会把每一行的 uid 转成数字，等价于在 uid 上套了一层数值转换函数。该转换使索引的字符串字典序无法直接用于比较：uid 按字符串字典序存放在 B+ 树中，逐行转换为数字后，比较顺序不再对应原有索引顺序。优化器因而无法据此定位记录，可能选择全表扫描。把查询改为 uid = '123' 后可以使用索引。
函数作用于索引列也会造成同样的问题。where DATE(create_time) = '2015-10-01' 在 create_time 上套了 DATE()，索引顺序无法直接使用。改成范围条件 where create_time >= '2015-10-01' and create_time < '2015-10-02'，create_time 直接作为范围边界，索引能用上。
函数作用于索引列、隐式类型转换和前导模糊查询（like '%abc'，前缀无法确定）都会使查询无法按索引顺序定位。选择性较低时，优化器可能估算出索引回表的成本高于全表扫描。这些场景需要分别检查查询条件与优化器的成本估算。
索引的成本与限制
- 写入放大。 每个索引在写入时都要维护，索引越多写越慢，页分裂还带来空间碎片。写多读少的表加索引要权衡写入代价。
- 空间占用。 每个二级索引是一份独立的 B+ 树，占额外存储。联合索引列越多，叶子页越大。
- 优化器选错索引。 优化器基于统计信息估算各候选索引的成本再选一个，统计信息过期或数据分布特殊时可能选错。验证靠
EXPLAIN，必要时用FORCE INDEX指定。优化器成本估算的内部细节我当时只到「用EXPLAIN验证走没走、走了哪个」这一层，没有深入读源码理解它的成本模型常数。 - 回表成本。 二级索引命中行数较多时，逐行回表的随机 I/O 成本可能高于全表扫描。命中量大且查询字段较多时，需要考虑覆盖索引或调整查询方式。
- 哪些查询可以不加索引。 低频的后台统计、一次性的运维导出可以接受偶尔慢一次，以免索引的写入成本长期累积。临时需求先
EXPLAIN看扫描量，能接受就不加。一个常见的反例是把报表查询的过滤条件随手建成索引，结果写多读少的业务表每天因这些索引写入变慢，而报表一周才跑一次。 - 与 PostgreSQL 的差异（仅记认知）。 那段时间我没有深度使用 PostgreSQL，只了解到它的主存储是堆表，索引独立存在、没有 InnoDB 意义上的聚簇索引，回表是常态。差异认知到此为止，不展开。
认知边界
当时我没有阅读 B+ 树页分裂、页合并和加锁行为的源码，也没有研究优化器成本估算的内部实现。对索引行为的判断主要来自 EXPLAIN 和接口实际 RT。
参考资料
- MySQL 5.6 官方文档（InnoDB 索引与 EXPLAIN 章节）
- 《高性能 MySQL》（第 3 版，索引相关章节，2015 年前已出版）
