13-MySQL 索引底层原理¶
本章核心：深入理解 B+ 树索引原理，这是数据库面试的必考重点
📋 本章概览¶
预计学习时间： 4-5 小时 前置章节：第 07 章：数据库优化与调优 面试重要度：★★★★★
🎯 学习目标¶
- 理解 B+ 树的结构和查询原理
- 掌握聚簇索引与非聚簇索引的区别
- 理解索引覆盖、索引下推等优化技术
- 能够回答常见索引相关面试题
1. 为什么需要索引¶
1.1 没有索引的查询¶
Text Only
假设表 users 有 100 万条记录，执行：
SELECT * FROM users WHERE id = 500000;
没有索引：
┌─────────────────────────────────────────────────────────────────────┐
│ 全表扫描（Full Table Scan） │
│ │
│ 数据页1 → 数据页2 → ... → 数据页N │
│ [读取] [读取] [读取] │
│ │
│ 需要扫描所有数据页，直到找到 id=500000 │
│ 最坏情况：读取 100 万条记录 │
│ I/O 次数：假设每页 100 条，需要读取 10000 个数据页 │
│ │
└─────────────────────────────────────────────────────────────────────┘
有索引：
┌─────────────────────────────────────────────────────────────────────┐
│ B+ 树索引查找 │
│ │
│ 根节点 → 内部节点 → 叶子节点 → 数据页 │
│ [1次I/O] [1次I/O] [1次I/O] [1次I/O] │
│ │
│ 树高 3-4 层，最多 3-4 次 I/O 即可定位 │
│ │
└─────────────────────────────────────────────────────────────────────┘
1.2 为什么选择 B+ 树¶
| 数据结构 | 查询复杂度 | 问题 |
|---|---|---|
| 哈希表 | O(1) | 不支持范围查询，哈希冲突 |
| 二叉搜索树 | O(log n) | 可能退化为链表 O(n) |
| AVL/红黑树 | O(log n) | 树高较大， I/O 次数多 |
| B+ 树 | O(log n) | 矮胖， I/O 次数少，范围查询高效 |
B+ 树的核心优势：
- 矮胖结构：每个节点可存储更多 key ，树高度低（通常 3-4 层）
- 减少磁盘 I/O：树高低意味着更少的磁盘访问
- 范围查询高效：叶子节点通过链表连接，顺序扫描方便
- 稳定的查询性能：任何记录都需要相同的 I/O 次数
2. B+ 树结构详解¶
2.1 B+ 树的组成¶
Text Only
┌─────────────────────────────────────────────────────────────────────┐
│ B+ 树结构图 │
├─────────────────────────────────────────────────────────────────────┤
│ │
│ [根节点] │
│ ┌─────┴─────┐ │
│ [28] [65] │
│ │ │ │
│ ┌───────────┴─┐ ┌────┴───────────┐ │
│ │ │ │ │ │
│ [内部节点] [内部节点] [内部节点] [内部节点] │
│ ┌──┴──┐ ┌──┴──┐ ┌──┴──┐ ┌──┴──┐ │
│ [15] [28] [38] [50] [56] [65] [75] [90] │
│ │ │ │ │ │ │ │ │ │
│ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ │
│ ┌──────────────────────────────────────────────────┐ │
│ │ 叶子节点层 │ │
│ │ [1,5,10,15] ↔ [18,20,25,28] ↔ [30,35,38] ↔ ... │ │
│ │ ↓ ↓ ↓ │ │
│ │ [数据] [数据] [数据] │ │
│ │ 或行指针 或行指针 或行指针 │ │
│ └──────────────────────────────────────────────────┘ │
│ │
│ 特点： │
│ 1. 非叶子节点只存储 key，不存储数据 │
│ 2. 所有数据都在叶子节点 │
│ 3. 叶子节点通过双向链表连接（范围查询友好） │
│ 4. 非叶子节点 key 用于分割搜索空间 │
│ │
└─────────────────────────────────────────────────────────────────────┘
2.2 B+ 树 vs B 树¶
Text Only
┌─────────────────────────────────────────────────────────────────────┐
│ B+ 树 vs B 树 对比 │
├─────────────────────────────────────────────────────────────────────┤
│ │
│ B 树： │
│ ┌──────────────────────────────┐ │
│ │ [key1, data1] [key2, data2] │ ← 非叶子节点也存数据 │
│ │ / \ │ │
│ │ [child1] [child2] │ │
│ └──────────────────────────────┘ │
│ │
│ B+ 树： │
│ ┌──────────────────────────────┐ │
│ │ [key1] [key2] │ ← 非叶子节点只存 key │
│ │ / | \ │ │
│ │ [key,data] ↔ [key,data] │ ← 数据都在叶子节点 │
│ └──────────────────────────────┘ │
│ │
├─────────────────────────────────────────────────────────────────────┤
│ │
│ B+ 树优势： │
│ 1. 非叶子节点不存数据 → 单节点能存更多 key → 树更矮 │
│ 2. 叶子节点链表连接 → 范围查询只需顺序遍历 │
│ 3. 所有查询都到叶子节点 → 查询性能稳定 │
│ │
│ B 树优势： │
│ 1. 如果数据在非叶子节点找到，可以提前返回 │
│ 2. 适合随机查询多、范围查询少的场景 │
│ │
└─────────────────────────────────────────────────────────────────────┘
2.3 InnoDB 的 B+ 树页结构¶
Text Only
┌─────────────────────────────────────────────────────────────────────┐
│ InnoDB 数据页结构（16KB） │
├─────────────────────────────────────────────────────────────────────┤
│ │
│ ┌─────────────────────────────────────────────────────────────┐ │
│ │ File Header (38B) │ 页的通用信息（页号、校验和等） │ │
│ ├─────────────────────────────────────────────────────────────┤ │
│ │ Page Header (56B) │ 本页专有信息（槽数量、记录数等） │ │
│ ├─────────────────────────────────────────────────────────────┤ │
│ │ Infimum + Supremum │ 虚拟的最小、最大记录（边界守卫） │ │
│ ├─────────────────────────────────────────────────────────────┤ │
│ │ │ │
│ │ User Records │ 用户数据区域（从前往后增长） │ │
│ │ [记录1] → [记录2] → [记录3] → ... │ │
│ │ │ │
│ ├───────────────────────── ↓ Free Space ↑ ────────────────────┤ │
│ │ │ │
│ │ Page Directory │ 页目录（从后往前增长） │ │
│ │ [槽1] [槽2] [槽3] ... │ 每个槽指向一组记录 │ │
│ │ │ │
│ ├─────────────────────────────────────────────────────────────┤ │
│ │ File Trailer (8B) │ 页尾校验信息 │ │
│ └─────────────────────────────────────────────────────────────┘ │
│ │
│ 页内记录按主键有序排列，通过单链表连接 │
│ 页目录（Page Directory）用于页内二分查找 │
│ │
└─────────────────────────────────────────────────────────────────────┘
3. 聚簇索引与非聚簇索引¶
3.1 聚簇索引（ Clustered Index ）¶
Text Only
┌─────────────────────────────────────────────────────────────────────┐
│ 聚簇索引（主键索引） │
├─────────────────────────────────────────────────────────────────────┤
│ │
│ 特点： │
│ 1. 叶子节点存储完整的行数据 │
│ 2. 数据按主键顺序物理存储 │
│ 3. 一张表只能有一个聚簇索引 │
│ 4. InnoDB 的主键就是聚簇索引 │
│ │
│ 结构示意： │
│ │
│ [根节点] │
│ / \ │
│ [28] [65] │
│ / \ / \ │
│ ┌──────┴────┴─────┴──────┴───────┐ │
│ │ 叶子节点 │ │
│ │ [id=1, name='张三', age=20] │ │
│ │ [id=2, name='李四', age=25] │ │
│ │ [id=3, name='王五', age=30] │ │
│ │ （完整行数据） │ │
│ └─────────────────────────────────┘ │
│ │
│ 查询示例：SELECT * FROM users WHERE id = 2; │
│ 过程：根节点 → 内部节点 → 叶子节点（直接获得完整数据） │
│ │
└─────────────────────────────────────────────────────────────────────┘
3.2 非聚簇索引（二级索引/辅助索引）¶
Text Only
┌─────────────────────────────────────────────────────────────────────┐
│ 非聚簇索引（二级索引） │
├─────────────────────────────────────────────────────────────────────┤
│ │
│ 特点： │
│ 1. 叶子节点存储的是主键值，而非完整行数据 │
│ 2. 查询非索引字段需要"回表" │
│ 3. 一张表可以有多个二级索引 │
│ │
│ 结构示意（以 name 字段为例）： │
│ │
│ [根节点] │
│ / \ │
│ [李] [王] │
│ / \ / \ │
│ ┌──────┴────┴─────┴──────┴───────┐ │
│ │ 叶子节点 │ │
│ │ [name='李四', id=2] ← 只存主键 │ │
│ │ [name='王五', id=3] │ │
│ │ [name='张三', id=1] │ │
│ └─────────────────────────────────┘ │
│ │
│ 查询示例：SELECT * FROM users WHERE name = '李四'; │
│ 过程： │
│ 1. 在二级索引中查找 name='李四'，获得 id=2 │
│ 2. 拿着 id=2 去聚簇索引查找完整数据（回表） │
│ │
│ ⚠️ 回表是额外的 I/O 开销！ │
│ │
└─────────────────────────────────────────────────────────────────────┘
3.3 回表过程详解¶
Text Only
┌─────────────────────────────────────────────────────────────────────┐
│ 回表（Back to Table） │
├─────────────────────────────────────────────────────────────────────┤
│ │
│ SQL: SELECT * FROM users WHERE name = '李四'; │
│ │
│ 步骤1：在 name 索引中查找 │
│ ┌────────────────────┐ │
│ │ name 索引（B+树） │ 找到：name='李四' → id=2 │
│ │ [李四, id=2] │ │
│ └────────────────────┘ │
│ │ │
│ │ 拿着 id=2 │
│ ↓ │
│ 步骤2：去聚簇索引（主键索引）查找完整数据 │
│ ┌────────────────────────────────────────┐ │
│ │ 聚簇索引（B+树） │ │
│ │ [id=2, name='李四', age=25, ...] │ ← 找到完整行 │
│ └────────────────────────────────────────┘ │
│ │
│ 回表的代价： │
│ - 额外的一次 B+ 树查找 │
│ - 可能的随机 I/O（聚簇索引中数据可能不连续） │
│ - 当回表次数很多时，性能可能不如全表扫描 │
│ │
└─────────────────────────────────────────────────────────────────────┘
4. 索引优化技术¶
4.1 覆盖索引（ Covering Index ）¶
SQL
-- 覆盖索引：查询的字段都在索引中，无需回表
-- 创建复合索引
CREATE INDEX idx_name_age ON users(name, age);
-- ✅ 覆盖索引查询（不需要回表）
SELECT name, age FROM users WHERE name = '李四';
-- EXPLAIN 显示：Using index
-- ❌ 需要回表（查询了不在索引中的字段）
SELECT name, age, email FROM users WHERE name = '李四';
-- 需要回表获取 email
Text Only
┌─────────────────────────────────────────────────────────────────────┐
│ 覆盖索引原理 │
├─────────────────────────────────────────────────────────────────────┤
│ │
│ 复合索引 idx_name_age(name, age) 的叶子节点： │
│ ┌────────────────────────────────────────────┐ │
│ │ [name='李四', age=25, id=2] │ │
│ │ [name='王五', age=30, id=3] │ │
│ │ [name='张三', age=20, id=1] │ │
│ └────────────────────────────────────────────┘ │
│ │
│ 查询 SELECT name, age WHERE name='李四'： │
│ 索引叶子节点中已有 name 和 age，直接返回，无需回表！ │
│ │
│ 优化建议： │
│ 1. 高频查询设计覆盖索引 │
│ 2. 将 SELECT * 改为只查需要的字段 │
│ 3. 利用复合索引覆盖更多查询 │
│ │
└─────────────────────────────────────────────────────────────────────┘
4.2 最左前缀原则¶
SQL
-- 复合索引 idx_a_b_c(a, b, c)
-- ✅ 命中索引
WHERE a = 1 -- 使用 a
WHERE a = 1 AND b = 2 -- 使用 a, b
WHERE a = 1 AND b = 2 AND c = 3 -- 使用 a, b, c
WHERE a = 1 AND c = 3 -- 只使用 a（c 被跳过）
-- ❌ 不命中索引
WHERE b = 2 -- 缺少最左列 a
WHERE c = 3 -- 缺少最左列 a
WHERE b = 2 AND c = 3 -- 缺少最左列 a
Text Only
┌─────────────────────────────────────────────────────────────────────┐
│ 最左前缀原则图解 │
├─────────────────────────────────────────────────────────────────────┤
│ │
│ 复合索引 (a, b, c) 的排序方式： │
│ │
│ 先按 a 排序 → a 相同时按 b 排序 → b 相同时按 c 排序 │
│ │
│ 数据示例： │
│ (1, 1, 1) │
│ (1, 1, 2) │
│ (1, 2, 1) ← 整体按 (a, b, c) 有序 │
│ (1, 2, 3) │
│ (2, 1, 1) │
│ (2, 1, 2) │
│ │
│ 为什么 WHERE b=2 不能用索引？ │
│ 因为 b 不是全局有序的！只有在 a 确定后，b 才有序 │
│ │
│ 类比电话簿：先按姓排序，同姓再按名排序 │
│ 只知道名找人 → 必须扫描整本电话簿 │
│ 知道姓找人 → 直接翻到对应页 │
│ │
└─────────────────────────────────────────────────────────────────────┘
4.3 索引下推（ Index Condition Pushdown, ICP ）¶
SQL
-- MySQL 5.6+ 支持索引下推
-- 复合索引 idx_name_age(name, age)
SELECT * FROM users WHERE name LIKE '张%' AND age = 20;
Text Only
┌─────────────────────────────────────────────────────────────────────┐
│ 索引下推原理 │
├─────────────────────────────────────────────────────────────────────┤
│ │
│ 不使用 ICP（MySQL 5.5）： │
│ 1. 用 name LIKE '张%' 在索引中找到所有姓张的记录 │
│ 2. 对每条记录回表，获取完整数据 │
│ 3. 在 Server 层用 age=20 过滤 │
│ │
│ 问题：可能回表了很多 age≠20 的记录，浪费 I/O │
│ │
│ 使用 ICP（MySQL 5.6+）： │
│ 1. 用 name LIKE '张%' 在索引中找到所有姓张的记录 │
│ 2. 在索引层直接用 age=20 过滤（索引中有 age） │
│ 3. 只对满足条件的记录回表 │
│ │
│ 优势：减少回表次数，提升查询效率 │
│ │
│ EXPLAIN 显示：Using index condition │
│ │
└─────────────────────────────────────────────────────────────────────┘
4.4 MRR （ Multi-Range Read ）优化¶
Text Only
┌─────────────────────────────────────────────────────────────────────┐
│ MRR（多范围读）优化 │
├─────────────────────────────────────────────────────────────────────┤
│ │
│ 问题场景：二级索引范围查询，需要回表 │
│ │
│ SELECT * FROM users WHERE age BETWEEN 20 AND 30; │
│ │
│ 不使用 MRR： │
│ 索引中找到: id=5, id=1, id=8, id=3 ...（主键可能不有序） │
│ 回表顺序: 5 → 1 → 8 → 3 ...（随机 I/O，效率低） │
│ │
│ 使用 MRR： │
│ 1. 在索引中收集所有满足条件的主键 │
│ 2. 对主键排序 │
│ 3. 按主键顺序回表（顺序 I/O，效率高） │
│ │
│ 回表顺序: 1 → 3 → 5 → 8 ...（顺序 I/O） │
│ │
│ 开启 MRR：set optimizer_switch='mrr=on,mrr_cost_based=off'; │
│ EXPLAIN 显示：Using MRR │
│ │
└─────────────────────────────────────────────────────────────────────┘
5. 索引失效场景¶
5.1 常见索引失效情况¶
SQL
-- 1. 对索引列使用函数
-- ❌ 索引失效
SELECT * FROM users WHERE YEAR(create_time) = 2024;
-- ✅ 优化为范围查询
SELECT * FROM users WHERE create_time >= '2024-01-01' AND create_time < '2025-01-01';
-- 2. 隐式类型转换
-- phone 是 VARCHAR 类型
-- ❌ 索引失效（字符串与数字比较，MySQL 将字符串转为数字）
SELECT * FROM users WHERE phone = 13800138000;
-- ✅ 使用正确类型
SELECT * FROM users WHERE phone = '13800138000';
-- 3. 模糊查询前缀通配符
-- ❌ 索引失效
SELECT * FROM users WHERE name LIKE '%张%';
SELECT * FROM users WHERE name LIKE '%张';
-- ✅ 可以使用索引
SELECT * FROM users WHERE name LIKE '张%';
-- 4. OR 连接非索引字段
-- 假设只有 name 有索引，email 没有
-- ❌ 索引失效
SELECT * FROM users WHERE name = '张三' OR email = 'test@test.com';
-- ✅ 改用 UNION
SELECT * FROM users WHERE name = '张三'
UNION
SELECT * FROM users WHERE email = 'test@test.com';
-- 5. 使用 != 或 <>
-- ❌ 可能导致索引失效（取决于数据分布）
SELECT * FROM users WHERE status != 0;
-- ✅ 如果可能，改用范围或 IN
SELECT * FROM users WHERE status IN (1, 2, 3);
-- 6. IS NULL / IS NOT NULL
-- 取决于存储引擎和字段特性，可能失效
-- 建议：设置合理的默认值，避免 NULL
5.2 索引失效诊断¶
SQL
-- 使用 EXPLAIN 分析查询
EXPLAIN SELECT * FROM users WHERE name = '张三';
-- 关键字段解读：
-- type:
-- ALL (全表扫描，最差)
-- index (索引扫描)
-- range (范围扫描)
-- ref (非唯一索引等值查询)
-- eq_ref (唯一索引等值查询)
-- const (主键/唯一索引常量查询，最优)
-- key: 实际使用的索引（NULL 表示未使用索引）
-- rows: 预计扫描行数
-- Extra:
-- Using index (覆盖索引)
-- Using index condition (索引下推)
-- Using where (需要在 Server 层过滤)
-- Using filesort (额外排序)
-- Using temporary (使用临时表)
6. 面试高频题¶
6.1 为什么 InnoDB 使用 B+ 树而不是 B 树¶
要点： 1. 非叶子节点更小： B+ 树非叶子节点只存 key ，单个节点能存更多 key ，树更矮 2. 范围查询高效： B+ 树叶子节点通过链表连接，范围扫描只需顺序遍历 3. 查询稳定：所有查询都走到叶子节点，性能稳定
6.2 聚簇索引和非聚簇索引的区别¶
要点： 1. 聚簇索引：叶子节点存完整行数据，数据按主键物理有序，一表只有一个 2. 非聚簇索引：叶子节点存主键值，查非索引字段需回表，可以有多个
6.3 什么是回表？怎么避免¶
回表：通过二级索引找到主键后，再去聚簇索引查找完整数据。
避免方法： 1. 覆盖索引：让查询的字段都在索引中 2. 减少 SELECT *：只查需要的字段 3. 合理设计复合索引
6.4 什么是最左前缀原则¶
复合索引 (a, b, c) 按 a→b→c 顺序排序，查询时必须从最左列开始匹配，不能跳过中间列。
6.5 索引越多越好吗¶
不是！索引的代价： 1. 空间开销：每个索引都是一棵 B+ 树，占用存储 2. 写入代价： INSERT/UPDATE/DELETE 需要维护所有相关索引 3. 优化器负担：索引太多增加查询优化器选择难度
建议：根据查询需求设计索引，定期清理未使用的索引。
6.6 自增主键 vs UUID 主键¶
| 特性 | 自增主键 | UUID |
|---|---|---|
| 插入性能 | 好（顺序写入，无页分裂） | 差（随机写入，频繁页分裂） |
| 索引大小 | 小（ 4/8 字节） | 大（ 36 字节） |
| 分布式 | 需要额外方案 | 天然唯一 |
| 安全性 | 可推测（有序） | 不可推测 |
推荐：单机优先自增主键，分布式可用雪花算法（有序+唯一）。
6.7 为什么推荐使用自增主键¶
- 顺序插入：新记录追加到最后，不会导致页分裂
- 索引紧凑：主键占用空间小，二级索引也更小
- 范围查询友好：按时间范围查询等价于按主键范围查询
7. 实战建议¶
7.1 索引设计原则¶
SQL
-- 1. 选择性高的列优先
-- 选择性 = 不重复的值 / 总行数
SELECT COUNT(DISTINCT status) / COUNT(*) FROM orders; -- 选择性低（如 0.001）
SELECT COUNT(DISTINCT order_no) / COUNT(*) FROM orders; -- 选择性高（接近 1）
-- 2. 经常出现在 WHERE、ORDER BY、GROUP BY 的列
-- 3. 小表不需要建索引（全表扫描更快）
-- 4. 频繁更新的列谨慎建索引
-- 5. 复合索引列顺序：等值条件 → 范围条件 → 排序字段
-- 好的设计：(status, create_time, user_id)
SELECT * FROM orders WHERE status = 1 AND create_time > '2024-01-01' ORDER BY user_id;
7.2 索引监控¶
SQL
-- 查看索引使用情况
SELECT
TABLE_SCHEMA, TABLE_NAME, INDEX_NAME,
SEQ_IN_INDEX, COLUMN_NAME, CARDINALITY
FROM information_schema.STATISTICS
WHERE TABLE_SCHEMA = 'your_db';
-- 查看未使用的索引（MySQL 8.0+）
SELECT * FROM sys.schema_unused_indexes;
-- 查看冗余索引
SELECT * FROM sys.schema_redundant_indexes;
参考资料： - 《高性能 MySQL 》（第 4 版） - 《 MySQL 技术内幕： InnoDB 存储引擎》 - MySQL 官方文档： InnoDB Index Types