Lesson 60 · 数据库与中间件实战
MySQL 索引原理:B+ 树、聚簇索引与覆盖索引
MySQL 索引原理:B+ 树、聚簇索引与覆盖索引
B+ 树为什么比 B 树更适合做索引?聚簇索引 vs 非聚簇索引、回表查询、覆盖索引、最左前缀匹配——面试高频题全解。
B+ 树 vs B 树——为什么 InnoDB 选择了 B+ 树?
要理解 MySQL 索引,必须先搞懂底层数据结构。InnoDB 的索引基于 B+ 树,而不是 B 树、红黑树或 Hash 表。这背后有三个关键原因。
为什么 B+ 树比 Hash 表更适合做数据库索引?
Hash 表查询单行是 O(1),但不支持范围查询(WHERE age > 25)和排序(ORDER BY),也不支持最左前缀匹配。B+ 树虽然单行查询是 O(logN),但综合性能远优于 Hash。
B+ 树高度估算:假设每个节点(页)16KB,主键 INT (4字节),指针 6字节
每个非叶节点可存:16KB / (4+6) ≈ 1638 个 key
2 层 B+ 树:1638 × 16 = 2.6 万行(假设每个叶子存 16 行)
3 层 B+ 树:1638 × 1638 × 16 = 4300 万行
结论:千万级数据只需 3 次磁盘 IO,根节点常驻内存只需 2 次
| 数据结构 | 树高/层数 | 范围查询 | 查询稳定性 | 空间利用率 |
|---|---|---|---|---|
| B+ 树 | 3~4 层(千万级) | ✅ 叶子链表遍历 | ✅ 每次都到叶子 | ✅ 非叶只存 key |
| B 树 | 3~4 层 | ❌ 需中序遍历 | ❌ 内部节点就可能命中 | 一般 |
| 红黑树 | O(logN) 但常数大 | ❌ 不支持 | ✅ | ❌ 指针开销大 |
| Hash 表 | O(1) | ❌ 完全不支持 | ✅ | ✅ |
B+ 树的三大优势:① 非叶节点不存数据 → 每页存更多 key → 树更矮 → 磁盘 IO 更少(3 层 B+ 树可存 2000 万+行);② 叶子双向链表 → 范围查询/排序天然高效;③ 所有查询都要到叶子 → 查询性能稳定 O(logN)。
InnoDB 聚簇索引——主键与数据"住在一起"
InnoDB 中,聚簇索引(Clustered Index)就是把数据行存在 B+ 树的叶子节点里。换句话说,主键索引的叶子节点直接存储了完整的数据行。一张表只能有一个聚簇索引。
CREATE TABLE user ( id INT PRIMARY KEY AUTO_INCREMENT, name VARCHAR(50), age INT, email VARCHAR(100) ); -- InnoDB 自动按 PRIMARY KEY 建聚簇索引 -- 如果没有主键,InnoDB 选唯一非空索引;都没有就生成隐藏 rowid
为什么建议用自增主键而不是 UUID?
UUID 是随机值,插入时会导致 B+ 树频繁页分裂(page split)——因为新数据要插到中间位置,导致大量数据搬移和随机磁盘 IO。自增主键总是在末尾追加,顺序 IO 性能远好于随机 IO。
自增主键 (1, 2, 3, 4, 5...): 新数据总是插入到 B+ 树最右侧的叶子节点 当前页满了 → 申请新页 → 顺序 IO → 极快 磁盘预读(read-ahead)也能命中 → 进一步优化 UUID (550e8400, a1b2c3d4, ...): 新数据随机分布,可能插入任何位置 当前页满了 → 页分裂:一半数据搬到新页 → 随机 IO 页分裂还会导致:内存碎片、B+ 树变高、查询变慢 实际影响(MySQL 官方测试): 自增主键插入速度 ≈ UUID 的 3~10 倍 UUID 表的索引体积比自增主键大 2~3 倍 如果业务必须用 UUID(如分布式 ID): 方案 1:雪花算法(Snowflake)→ 趋势递增的 Long 型 ID 方案 2:有序 UUID → UUID() 改为有序版本(MySQL 8.0 UUID_TO_BIN)
聚簇索引 = 数据本身。InnoDB 表必须有且只有一个聚簇索引。主键查询只需一次 B+ 树遍历即可拿到完整数据行。
二级索引 + 回表查询
二级索引(Secondary Index,也叫辅助索引 / 非聚簇索引)的叶子节点存的不是完整数据行,而是主键值。通过二级索引查到主键后,还需要拿着主键回到聚簇索引查完整数据——这就是回表。
二级索引查询代价 = O(logN) IO(二级索引树)+ O(logN) IO(回表聚簇索引树)
如果返回 K 行:总 IO ≈ logN + K × logN(每行都要回表)
当回表次数很多时,MySQL 优化器会怎么做?
当优化器估算回表的 IO 成本大于全表扫描时,会放弃使用二级索引,直接走全表扫描。这就是为什么有时候明明建了索引,EXPLAIN 却显示 type=ALL。
EXPLAIN SELECT * FROM user WHERE age = 25; +----+------+-----+------+----------+-------+ | id | type | key | rows | filtered | Extra | +----+------+-----+------+----------+-------+ | 1 | ref | idx | 128 | 100.00 | NULL | +----+------+-----+------+----------+-------+ type 列含义(从优到差): system > const > eq_ref > ref > range > index > ALL - const: 主键/唯一索引等值查询,最多返回 1 行 - eq_ref: JOIN 时被驱动表用主键关联,每次返回 1 行 - ref: 非唯一索引等值查询,可能返回多行 - range: 索引范围扫描(>, <, BETWEEN, IN) - index: 全索引扫描(扫描整棵索引树) - ALL: 全表扫描(最差,需要优化) Extra 列重要标识: - Using index: 覆盖索引,不需要回表 ✅ - Using filesort: 需要额外排序 ❌ - Using temporary: 使用了临时表 ❌
优化器决策公式:索引扫描成本 = 扫描行数 × 单行 IO 成本 + 回表行数 × 回表 IO 成本
当 索引扫描成本 > 全表扫描成本 时,优化器选择全表扫描
经验值:当查询结果超过表数据的 20%~30% 时,全表扫描通常更优
-- 如果你确信优化器的判断有误,可以强制指定索引 SELECT * FROM user FORCE INDEX(idx_age) WHERE age = 25; -- 也可以忽略某个索引 SELECT * FROM user IGNORE INDEX(idx_age) WHERE name = 'Alice'; -- 注意:生产环境慎用 FORCE INDEX -- 优化器通常比人更了解数据分布 -- 如果优化器不选索引,优先检查统计信息是否准确(ANALYZE TABLE)
覆盖索引——消灭回表的终极武器
如果查询的所有列都包含在某个二级索引中,就不需要回表了——这叫做覆盖索引(Covering Index)。EXPLAIN 的 Extra 列会显示 Using index。
-- 建联合索引 ALTER TABLE user ADD INDEX idx_name_age (name, age); -- ✅ 覆盖索引:查询列 name, age 都在 idx_name_age 中 SELECT name, age FROM user WHERE name = 'Alice'; -- EXPLAIN Extra: Using index ← 不回表! -- ❌ 非覆盖索引:需要 email 列,但索引中没有 SELECT name, age, email FROM user WHERE name = 'Alice'; -- EXPLAIN Extra: 无 Using index ← 需要回表拿 email
"覆盖索引是指查询所需的所有列都能在某个索引中找到,无需回表查聚簇索引。在 EXPLAIN 中表现为 Extra 列出现 Using index。优化方法是在联合索引中包含 SELECT 的列,但要注意索引不能太宽,否则维护成本增加。"
最左前缀匹配原则
联合索引 (a, b, c) 在 B+ 树中的排序规则是:先按 a 排序,a 相同再按 b 排序,b 相同再按 c 排序。因此查询条件必须从最左列开始连续匹配。
| 联合索引 | 查询条件 | 能否走索引 | 原因 |
|---|---|---|---|
| (a, b, c) | WHERE a=1 | ✅ a | 最左匹配 |
| (a, b, c) | WHERE a=1 AND b=2 | ✅ a,b | 连续匹配 |
| (a, b, c) | WHERE a=1 AND b=2 AND c=3 | ✅ a,b,c | 完全匹配 |
| (a, b, c) | WHERE b=2 | ❌ | 缺少最左列 a |
| (a, b, c) | WHERE a=1 AND c=3 | ✅ a(c 不行) | b 断了,c 无法利用 |
| (a, b, c) | WHERE a=1 AND b>5 AND c=3 | ✅ a,b(c 不行) | b 是范围查询,c 无法利用 |
| (a, b, c) | WHERE a=1 ORDER BY b | ✅ a,b | b 已排序,免 filesort |
-- MySQL 8.0 引入 Index Skip Scan -- 联合索引 (a, b),查询 WHERE b = 2 -- 如果 a 列的不同值很少(比如 gender: M/F), -- 优化器可能拆成:WHERE a='M' AND b=2 UNION WHERE a='F' AND b=2 -- 但这不是普遍适用的优化,面试时提一下即可
为什么范围查询后的列无法使用索引?
联合索引 (a,b,c) 中,当 b 是范围条件(如 b>5)时,b 之后的 c 在 B+ 树中并不是有序的——因为 c 的排序前提是"b 值相同",但范围查询跨了多个 b 值,c 的有序性被打破了。
最左前缀 = 从左到右连续匹配,遇到范围查询(>、<、BETWEEN、LIKE)就断。设计联合索引时,把等值查询的列放前面,范围查询的列放后面。
索引合并(Index Merge)
当查询条件涉及多个单列索引时,MySQL 可能会同时使用多个索引,再合并结果。这就是索引合并,在 EXPLAIN 的 type 列显示为 index_merge。
-- 假设表有两个单列索引: idx_a(a), idx_b(b) -- 1. Intersection 交集合并 SELECT * FROM t WHERE a = 1 AND b = 2; -- 分别走 idx_a 和 idx_b,取交集 → 减少回表 -- 2. Union 并集合并 SELECT * FROM t WHERE a = 1 OR b = 2; -- 分别走 idx_a 和 idx_b,取并集 -- 3. Sort-Union 排序并集 SELECT * FROM t WHERE a < 5 OR b > 10; -- 先各自扫描取主键,排序后再合并
索引合并是好的优化吗?
索引合并说明索引设计不够好。如果你频繁需要 index_merge intersection,说明应该建联合索引 (a,b);如果频繁需要 union,考虑业务是否需要调整查询方式。索引合并是优化器的"兜底方案",不是最优解。
索引失效的常见场景
面试中"索引失效"几乎是必考项。以下汇总了最常见的索引失效场景:
| # | 失效场景 | 示例 | 原因 / 解决 |
|---|---|---|---|
| 1 | 对索引列使用函数/运算 | WHERE YEAR(create_time)=2024 | 函数破坏了 B+ 树有序性。改为 WHERE create_time >= '2024-01-01' AND create_time < '2025-01-01' |
| 2 | 隐式类型转换 | WHERE phone = 13800001234(phone 是 VARCHAR) | MySQL 对 VARCHAR 列做隐式转换 → 等同函数调用。加引号即可 |
| 3 | LIKE 以 % 开头 | WHERE name LIKE '%张' | 前缀不确定,无法走 B+ 树。用全文索引或 ES |
| 4 | OR 条件中有非索引列 | WHERE a=1 OR b=2(b 无索引) | 必须全表扫才能判断 b。两个列都建索引或改 UNION |
| 5 | NOT IN / NOT EXISTS | WHERE id NOT IN (1,2,3) | 多数情况优化器放弃索引。视数据量考虑改写 |
| 6 | 违反最左前缀 | 索引 (a,b,c),查询 WHERE b=2 | 缺少最左列 a。调整索引或查询 |
| 7 | 索引列参与比较 | WHERE id + 1 = 10 | 对列做了运算。改为 WHERE id = 9 |
| 8 | 字符集不一致的关联 | 两表 JOIN 但连接字段字符集不同 | 转换函数导致失效。统一字符集 |
-- phone 列类型是 VARCHAR(20),有索引 -- ❌ 索引失效:MySQL 把 VARCHAR 转成数字再比较 SELECT * FROM user WHERE phone = 13800001234; -- 等价于 WHERE CAST(phone AS SIGNED) = 13800001234 -- 对索引列使用了函数 → 索引失效! -- ✅ 加引号,类型一致 SELECT * FROM user WHERE phone = '13800001234';
1. 选择性高的列优先建索引 选择性 = COUNT(DISTINCT col) / COUNT(*) 越接近 1 越好 性别(gender) 选择性差 → 不适合单独建索引 身份证号(id_card) 选择性好 → 适合建索引 2. 联合索引优于多个单列索引 经常 WHERE a=? AND b=? → 建 (a,b) 比 idx_a + idx_b 更高效 3. 考虑查询覆盖 SELECT a, b FROM t WHERE a=? → 建 (a, b) 实现覆盖索引 4. 避免过多索引 每个索引都有维护成本(INSERT/UPDATE/DELETE 变慢) 单表索引一般不超过 5~6 个 5. 长字符串用前缀索引 ALTER TABLE t ADD INDEX idx_name(name(10)); 只对前 10 个字符建索引 → 节省空间,提高写入性能
回答索引失效问题时,先说原理(破坏了 B+ 树的有序性 / 无法在树上做二分查找),再举具体例子。面试官最爱追问的是"隐式类型转换"和"LIKE '%xx'"——把这两个讲透就够用了。
全篇回顾
- B+ 树:叶子存数据 + 双向链表 → 范围查询高效,树更矮 IO 更少
- 聚簇索引:主键 B+ 树叶子 = 完整数据行,一张表只能有一个
- 二级索引 + 回表:叶子存主键 → 需要再查聚簇索引拿完整行
- 覆盖索引:查询列都在索引中 → 不回表 → Using index
- 最左前缀:联合索引从左到右匹配,范围查询后断裂
- 索引合并:多索引联合使用,但说明索引设计有改进空间
- 索引失效:函数/运算、隐式转换、LIKE '%xx'、OR 含非索引列等