索引与B+树
开篇：为什么数据库需要索引？
想象你手里有一本 800 页的书，要找"B+树"这个词出现在哪一页。如果没有目录，你只能从第 1 页翻到第 800 页——这就是全表扫描。而如果书后面有一份按字母排序的索引，你翻到"B"那一栏，瞬间就能定位到页码——这就是索引查找。
MySQL 里的索引做的事情完全一样：用一种有序的数据结构，减少磁盘 I/O 次数，加快查询速度。
索引的好处显而易见：
- 把"逐页翻书"变成"查目录"，大幅降低磁盘 I/O
- 唯一索引还能顺带保证数据不重复
- 对 ORDER BY、GROUP BY 友好，减少排序开销
- 多表 JOIN 时，连接字段有索引可以大幅加速匹配
当然也有代价：
- 索引本身占磁盘空间（每多一个索引就多一棵 B+ 树）
- 每次 INSERT/UPDATE/DELETE 都要同步维护索引，写操作变慢
- 索引越多，优化器的选择越复杂，偶尔会"选错"
所以索引不是越多越好——合理地使用索引，才是数据库调优的核心功夫。
一、从二叉树到B+树的演化
要理解 MySQL 为什么选择 B+ 树，我们先快速走一遍"数据结构选型"的心路历程。
1.1 没有索引时怎么查？
InnoDB 把数据存在一个个 16KB 的页 里，页和页之间用双向链表连接，页内的记录用单向链表按主键递增排列。
查找一条记录要分两步：
- 定位数据在哪个页——沿着双向链表逐页扫描
- 在页内找到目标行——以主键查可以在页目录里二分查找，以其他列查只能从头遍历单链表
数据量一大，光是"逐页扫描"这一步就需要成百上千次磁盘 I/O，完全不可接受。我们需要一种结构能快速定位"数据在哪一页"。
1.2 索引的雏形：给数据页建目录
最朴素的想法：给所有数据页建一个目录，每个目录项记录"这个页里最小的主键值"和"页号"。查找时对目录做二分查找，一步定位到目标页。
但随着数据增长，目录项也越来越多，放在一块连续内存里压力很大，增删也不方便。怎么办？把目录项也存到数据页里，形成一个目录页。
目录页越来越多怎么办？再给目录页建一层目录页。层层嵌套下去——这不就是一棵树么？
[ 高级目录页 ]
/ \
[目录页1] [目录页2]
/ | \ / | \
[数据页] [数据页] [数据页] [数据页] [数据页] [数据页]这就是 B+ 树的由来——一步步从实际需求中演化出来的。
1.3 Hash：快但不够灵活
Hash 索引的等值查询飞快（O(1)），但它有几个致命短板：
- 不支持范围查询（
WHERE age > 20得全表扫） - 不支持排序（ORDER BY 无法利用 Hash）
- 联合索引时，Hash 是把所有列合在一起算的，不能只用前几列
- 重复值多时容易哈希冲突，退化成链表
所以 Hash 更适合 Redis 这类内存 KV 场景。InnoDB 默认不用它，但提供了自适应哈希（Adaptive Hash Index）：对频繁访问的数据页自动建 Hash 缓存，让 B+ 树也能享受 Hash 的等值查询速度。
适合用 Hash 的场景
Memory 存储引擎 + 字段重复度低 + 只做等值查询时，Hash 索引非常高效。
1.4 二叉搜索树 / AVL树：太"瘦高"
平衡二叉搜索树（AVL）查找效率是 O(log₂N)，但每个节点只存一个 key，树会非常"瘦高"。100 万条数据，树高约 20 层——每层对应一次磁盘 I/O，20 次 I/O 不可接受。
更严重的是，普通二叉搜索树在数据递增插入时会退化成链表，变成 O(N)。AVL 虽然通过旋转保持平衡，但本质问题——一个节点一个 key，太浪费磁盘的每次 I/O 了——并没有解决。
核心矛盾：磁盘 I/O 按页（16KB）读取，一次只读一个 key 太浪费了。 我们需要让每个节点"胖"起来，一次读一页就能拿到尽可能多的 key。
1.5 B 树：矮胖了，但还不够
B 树（多路平衡查找树）让每个节点存多个 key，树变得又矮又胖，I/O 次数大幅下降。它有三个特点：
- 插入和删除时自动调整，始终保持平衡
- 所有节点（包括非叶子）都存储数据
- 搜索可能在中间节点就结束了
但 B 树有两个不足：
- 非叶子节点也存数据，挤占了空间，能容纳的 key 变少，树还是偏高
- 范围查询时需要中序遍历整棵树，在不同层级之间来回跳，效率不理想
1.6 B+ 树：MySQL 的最终选择
B+ 树在 B 树基础上做了关键改进：
| 特性 | B 树 | B+ 树 |
|---|---|---|
| 非叶子节点存数据 | 是 | 否（只存 key + 指针） |
| 叶子节点 | 存部分数据 | 存所有数据 |
| 叶子间连接 | 无 | 双向链表 |
| 查询路径 | 可能在中间节点结束 | 一定走到叶子节点 |
| 查询效率稳定性 | 不稳定 | 稳定（路径长度一致） |
用一张图来看 B+ 树的结构：
B+ 树带来的好处：
- 查询效率稳定——每次都要走到叶子节点，路径长度一致
- 范围查询高效——叶子节点是有序双向链表，找到起点后顺着链表扫就行
- 非叶子节点能塞更多 key——不存数据，一个 16KB 的页可以存上千个 key+指针
- 天然支持排序——叶子节点本身就是有序的
- 磁盘预读友好——节点大小等于页大小，一次 I/O 读满一个节点
- 有利于缓存——非叶子节点不存数据、体积小，更容易被 Buffer Pool 全部缓存
1.7 为什么只需要 1~3 次磁盘 I/O？
做个简单估算：
| 层级 | 每页存储量 | 说明 |
|---|---|---|
| 非叶子节点 | ~1000 个指针 | 16KB / (key 8B + 指针 8B) |
| 叶子节点 | ~100 条记录 | 16KB / 160B（假设平均行长） |
- 两层非叶子 + 一层叶子 = 1000 x 1000 x 100 = 1 亿条记录
- 三层非叶子 + 一层叶子 = 1000 亿条记录（远超实际需求）
而 B+ 树的根节点在表创建时就分配好了，常驻内存不变。所以实际只需要 2~3 次磁盘 I/O 就能定位到任意一条记录。
1.8 关于 B+ 树的几个细节
根页面位置始终不变。 创建索引时就分配了根页面。数据增长后，根页面的记录会被复制到新页，根页面升级为目录页，但它的物理位置不会改变。
一个页面至少存两条记录。 否则 B+ 树退化成链表，失去了多路查找的意义。
非叶子节点会冗余主键保证唯一性。 二级索引的目录项可能出现重复的索引值，这时会附带主键一起存储，确保每个目录项都能唯一定位到对应的子页。
主键不是递增的会导致页分裂。 如果插入的主键值"忽大忽小"，新记录可能要插到一个已满的数据页中间，迫使 InnoDB 把这个页一分为二（页分裂），带来额外的 I/O 开销。这就是为什么推荐用自增主键。
二、聚簇索引与非聚簇索引
2.1 一个生活类比
把 InnoDB 的表想象成一个图书馆：
- 聚簇索引 = 书架上书的摆放顺序。书按照编号从小到大排列在架上，你知道编号就能直接伸手拿到那本书。数据和索引放在一起，找到索引就找到了数据。
- 非聚簇索引 = 图书馆的主题目录卡。卡片上写着"数据库 → 编号 978"，你先查卡片拿到编号，再去书架上按编号取书。索引和数据分开存储，查到索引后还需要一次"回表"。
2.2 聚簇索引（主键索引）
在 InnoDB 中，聚簇索引就是主键索引。它的 B+ 树叶子节点直接存储完整的行记录——所以我们说"索引即数据，数据即索引"。
聚簇索引 B+ 树叶子节点:
┌──────────┬──────────────────────────┐
│ 主键 id │ 整行数据(name,age,...) │
├──────────┼──────────────────────────┤
│ 1 │ ('张三', 25, ...) │
│ 2 │ ('李四', 30, ...) │
│ 3 │ ('王五', 28, ...) │
└──────────┴──────────────────────────┘关键特性：
- 每张 InnoDB 表有且只有一个聚簇索引
- 如果你定义了主键，主键就是聚簇索引
- 没有主键时，InnoDB 会选一个非空唯一索引；都没有的话，会生成一个隐藏的 6 字节
db_row_id - 基于主键查询不需要回表，效率最高
- 对主键的排序和范围查找天然高效（叶子节点就是有序链表）
- 插入速度严重依赖插入顺序（推荐自增主键）
- 更新主键代价高昂（数据要物理搬迁）
2.3 非聚簇索引（二级索引 / 辅助索引）
除主键外的所有索引都是非聚簇索引。它的叶子节点存的是索引列的值 + 主键值，并且按照索引列的值排序。
非聚簇索引 B+ 树叶子节点（以 name 索引为例）:
┌──────────┬──────────┐
│ name │ 主键 id │
├──────────┼──────────┤
│ '李四' │ 2 │
│ '王五' │ 3 │
│ '张三' │ 1 │
└──────────┴──────────┘
（按 name 排序，不是按 id 排序）通过非聚簇索引查询时：先在二级索引树中找到主键值，再拿着主键值到聚簇索引树中查完整记录——这个过程就叫回表。
联合索引也属于非聚簇索引，只不过它同时用多个列排序。
2.4 InnoDB vs MyISAM 的索引对比
| 特性 | InnoDB | MyISAM |
|---|---|---|
| 聚簇索引 | 支持（主键索引） | 不支持 |
| 叶子存储 | 聚簇索引存整行数据 | 所有索引都存数据的物理地址 |
| 回表方式 | 二级索引 → 主键值 → 聚簇索引 | 索引 → 物理地址 → 直接读数据文件 |
| 必须有主键 | 是（没有会自动生成） | 否 |
| 事务支持 | 支持 | 不支持 |
| 锁粒度 | 行级锁 | 表级锁 |
| 默认引擎 | MySQL 5.5+ | MySQL 5.5 之前 |
MyISAM 的索引文件（.MYI）和数据文件（.MYD）是分离的，所有索引本质上都是"非聚簇"的。MyISAM 的回表是拿着物理地址直接读数据文件，速度其实不慢，但缺少聚簇索引"一步到位"的优势。正是因为 MyISAM 存在这个局限，后来的 InnoDB 引入了聚簇索引，让主键查询效率有了质的飞跃。
三、联合索引与最左前缀
3.1 电话簿的类比
想象一本按照"姓 → 名"排序的电话簿：
- 你知道姓"张"，可以快速翻到"张"那一节 → 能用索引
- 你知道姓"张"且名"三"，定位更精准 → 能用索引
- 你只知道名"三"，不知道姓 → 整本翻，索引用不上
联合索引 (a, b, c) 的排序规则完全一样：先按 a 排，a 相同再按 b 排，b 也相同再按 c 排。这决定了你只能从左往右匹配。
3.2 最左前缀匹配规则
对于联合索引 (a, b, c)：
| 查询条件 | 能否走索引 | 说明 |
|---|---|---|
WHERE a = 1 | 能 | 匹配最左列 |
WHERE a = 1 AND b = 2 | 能 | 匹配前两列 |
WHERE a = 1 AND b = 2 AND c = 3 | 能 | 完整匹配 |
WHERE a = 1 AND c = 3 | 部分走（只用 a） | 跳过了 b，c 用不上 |
WHERE b = 2 | 不能 | 缺少最左列 |
WHERE b = 2 AND c = 3 | 不能 | 缺少最左列 |
两个关键细节：
WHERE 条件中字段的书写顺序不影响索引使用。
WHERE b = 2 AND a = 1和WHERE a = 1 AND b = 2效果完全一样，优化器会自动调整顺序。最左前缀不只适用于联合索引。 单列索引做 LIKE 查询时，
LIKE 'ab%'可以走索引（左边确定），而LIKE '%ab'不行（左边不确定），本质也是最左前缀匹配。
3.3 联合索引只建了一棵树
一个常见误区：创建 (a, b, c) 联合索引后，MySQL 会自动创建 (a)、(a,b)、(a,b,c) 三个索引。
实际上只有一棵 B+ 树。 在这棵树的节点中，同时存储 a、b、c 三个字段的值。排序规则是"先比 a，a 相同比 b，b 相同比 c"。
之所以 a 单独查也能用，是因为在这个排序规则下，a 本身就是全局有序的。但 b 只在"同一个 a 值内部"有序，所以单独查 b 时，b 在全局范围内是乱序的，走不了这个索引。
3.4 范围条件对右边列的影响
联合索引 (age, classId, name) 中，如果查询条件有范围：
-- classId > 20 是范围条件，name 的索引就用不上了
SELECT * FROM student
WHERE age = 30 AND classId > 20 AND name = 'abc';只有 age 和 classId 能走索引，name 失效。原因是 classId 一旦变成范围扫描，后面的 name 就不再有序了。
实践建议
创建联合索引时，把可能用于范围查询的列放到最右边。
3.5 索引跳跃扫描（MySQL 8.0+）
MySQL 8.0.13 引入了索引跳跃扫描（Index Skip Scan），让"不遵守最左前缀"的查询也有可能用上索引。
举个例子，联合索引 (f1, f2)，查询 WHERE f2 = 40。在 8.0 之前只能扫全索引树（type=index），在 8.0 之后优化器可能这样做：
- 取 f1 的第一个唯一值（如 f1=1），构造
f1=1 AND f2=40做范围查询 - 取 f1 的第二个唯一值（如 f1=2），构造
f1=2 AND f2=40做范围查询 - 依次枚举完所有 f1 的唯一值，合并结果
EXPLAIN 中会显示 Using index for skip scan，type 变成 range，扫描行数大幅减少（比如从 160 行降到 16 行）。
但它有个重要前提：f1 的区分度要很低（比如性别只有两个值）。如果 f1 区分度很高（如出生日期），枚举 f1 值的开销太大，优化器不会选择跳跃扫描。
其他限制：只能依赖单表查询、不能用 GROUP BY 或 DISTINCT、查询列必须都在索引中。
所以结论不变：建索引时，还是要把区分度高、查询频繁的字段放在最左边。
四、回表与覆盖索引
4.1 什么是回表？
当你用非聚簇索引查询，但 SELECT 的列不全在这个索引里时，查询流程分两步：
这个"先查二级索引，再查聚簇索引"的过程就是回表。回表意味着两次 B+ 树查找，多了一轮磁盘 I/O。如果二级索引命中了 100 行，就要回表 100 次——代价非常大。
4.2 覆盖索引：不回表的秘诀
如果索引中已经包含了查询需要的所有列（包括 SELECT 的列和 WHERE 的列），就不用回表了——这就叫覆盖索引。
-- 假设有联合索引 idx_age_name(age, name)，id 是主键
-- 需要回表：SELECT * 要的列超出了索引范围
EXPLAIN SELECT * FROM student WHERE age = 20;
-- type=ref, Extra=NULL（需要回表取其他列）
-- 不需要回表（覆盖索引）：age、name、id 都在索引里
EXPLAIN SELECT age, name FROM student WHERE age = 20;
-- type=ref, Extra=Using index（覆盖索引，无需回表）覆盖索引在 EXPLAIN 的 Extra 列会显示 Using index。
覆盖索引的两个好处：
- 避免回表，减少一次 B+ 树查找，I/O 次数减半
- 把随机 I/O 变成顺序 I/O——二级索引本身是按 key 排序的，顺序读取比回表时的随机读取快得多
实践建议
开发中不要用 SELECT *，精确指定列名才有机会触发覆盖索引。这是性能优化中投入产出比最高的习惯之一。
一个有趣的现象：!= 通常会导致索引失效（后面会讲），但如果查询的列刚好被索引覆盖，优化器可能仍然选择扫描索引树而不是全表扫描，因为索引树比数据表小得多。
五、索引下推 ICP
索引条件下推（Index Condition Pushdown, ICP）是 MySQL 5.6 引入的优化，默认开启。
5.1 一个例子说清楚
假设有联合索引 (zipcode, lastname, firstname)，执行：
SELECT * FROM people
WHERE zipcode = '95054'
AND lastname LIKE '%etrunia%'
AND address LIKE '%Main Street%';没有 ICP 时的流程：
假如 zipcode='95054' 匹配了 1000 行，就要回表 1000 次，然后才发现其中 990 行的 lastname 不满足条件——白回表了。
有 ICP 时的流程：
虽然 lastname LIKE '%etrunia%' 单独看不能走索引（%在前面），但 lastname 的值已经存在索引叶子节点里了。ICP 在索引层就用这个值做了过滤，把不满足条件的行提前排除，可能只剩 10 行需要回表。
EXPLAIN 中会显示 Using index condition。
5.2 ICP 不只适用于 LIKE
很多人以为 ICP 只和 LIKE 有关。其实只要联合索引中某个列"无法参与索引定位"，但它的值仍然存在索引中，ICP 就可以拿来做过滤。常见场景：
- 联合索引中间列跳过了（如查 a 和 c，b 被跳过，c 的值仍可用于 ICP 过滤）
- 类型不匹配导致隐式转换（如 varchar 列传了 int 值）
- 函数操作导致失效（但函数计算后的值仍可比较）
-- 联合索引 (a, b)，a 和 b 都是 varchar
-- b 传了数字 1，类型不匹配导致 b 无法参与索引查找
-- 但 ICP 仍然可以在索引层用 b 的值做过滤，减少回表
SELECT d FROM t2 WHERE a = 'ni' AND b = 1;5.3 ICP 的使用条件
- 访问类型为 range、ref、eq_ref、ref_or_null
- 适用于 InnoDB 和 MyISAM（InnoDB 仅对二级索引有效，因为聚簇索引本身就不需要回表）
- 如果已经是覆盖索引（不需要回表），ICP 没有意义，不会触发
- 子查询条件不能使用 ICP
六、常见面试题精选
Q1：联合索引 (A,B,C)，按 AB、AC、BC 查询分别能走索引吗？
| 查询条件 | 走索引情况 |
|---|---|
| A | 能走 |
| AB | 能走，用到 A 和 B |
| AC | 部分走，只用到 A（跳过了 B，C 用不上） |
| ABC | 全部走 |
| B / C / BC | 不走（缺少最左列 A） |
其中 AB 的效果优于 AC：AB 可以利用 A 和 B 两层索引精确定位，而 AC 跳过了 B，实际只能用到 A。WHERE 中字段书写顺序（BA vs AB）不影响结果。
Q2：InnoDB 为什么选 B+ 树而不是 B 树或红黑树？
| 数据结构 | 问题 |
|---|---|
| 红黑树 | 二叉树，每节点一个 key，树高 20+层，I/O 次数太多 |
| B 树 | 非叶子也存数据，key 容量少，树偏高；范围查询需中序遍历 |
| B+ 树 | 非叶子只存 key，树最矮（2~4 层）；叶子双向链表串联，范围查询极高效 |
一句话：B+ 树最"矮胖"，I/O 次数最少，范围查询最方便，缓存命中率最高。
Q3：什么是回表？如何减少回表？
回表是通过二级索引查到主键后，再到聚簇索引中取完整数据的过程。减少回表的三种方式：
- 使用主键查询——直接命中聚簇索引，无需回表
- 覆盖索引——让 SELECT 和 WHERE 涉及的列都在索引里，EXPLAIN 显示
Using index - 索引下推（ICP）——在索引层提前过滤不满足条件的行，减少需要回表的行数
Q4：什么是索引合并？
当查询条件涉及多个单列索引时，MySQL 可能同时使用多个索引再合并结果（type=index_merge）。三种策略：
Using intersect：AND 条件，取多个索引结果的交集Using union：OR 条件，取多个索引结果的并集Using sort_union：需要排序的并集
-- key1 和 key2 各有独立索引
SELECT * FROM t WHERE key1 = 10 OR key2 = 20;
-- EXPLAIN: type=index_merge, Extra=Using union(key1,key2)Q5：唯一索引和主键索引有什么区别？
| 维度 | 主键索引 | 唯一索引 |
|---|---|---|
| 唯一性 | 必须唯一 | 必须唯一 |
| 是否允许 NULL | 不允许 | 允许（多个 NULL 视为互不相同） |
| 数量限制 | 一张表只有一个 | 可以有多个 |
| 索引结构 | 聚簇索引 | 通常是非聚簇索引 |
| 是否回表 | 不需要 | 通常需要 |
| 外键引用 | 可以 | 不可以 |
特殊情况：如果表没有主键，InnoDB 会选一个非空唯一索引当聚簇索引——这时这个唯一索引就变成了聚簇索引。
小结
| 概念 | 一句话总结 |
|---|---|
| 索引 | 有序数据结构，减少磁盘 I/O，加速查询 |
| B+ 树 | 非叶子只存 key，叶子存数据 + 双向链表，又矮又快 |
| 聚簇索引 | 主键索引，叶子存整行数据，找到索引就找到数据 |
| 非聚簇索引 | 二级索引，叶子存主键值，需要回表 |
| 最左前缀 | 联合索引从左到右匹配，跳过中间列后右边列失效 |
| 覆盖索引 | 查询的列都在索引里，无需回表 |
| 索引下推 | 在索引层提前过滤，减少回表次数 |
| 索引跳跃扫描 | 8.0+ 对低区分度前导列的优化，自动补齐最左列 |