一、B+ 树：索引的底层数据结构
1.1 为什么是 B+ 树？
在深入 B+ 树之前，先理解为什么 MySQL 选择它而不是其他数据结构：
| 数据结构 | 磁盘 I/O 次数 | 适用场景 | 问题 |
|---|---|---|---|
| 数组 | O(log n) 二分查找 | 静态数据 | 插入删除需要移动数据 |
| 二叉搜索树 | O(log n) 但可能退化为 O(n) | 内存中 | 树高度不可控，磁盘 I/O 多 |
| AVL/红黑树 | O(log n) 但高度约 log₂(n) | 内存中 | 2000万数据高度约25层 |
| B 树 | O(log_m n)，m 为阶数 | 磁盘存储 | 非叶子节点也存数据 |
| B+ 树 | O(log_m n)，更低的高度 | 磁盘存储 | 所有数据在叶子节点 |
关键洞察：磁盘 I/O 是数据库的瓶颈。B+ 树通过高扇出（每个节点存储更多键）将树高控制在 3-4 层。
1.2 B+ 树的核心特征
sql
\-\- 示例：一个 B+ 树索引结构 \-\- 阶数 m = 5（每个节点最多 5 个指针，4 个键值） \[50, 100, 150\] \-\- 根节点 / | \ \ / | \ \ \[10,20,30,40\] \[60,70,80,90\] \[120,130,140\] \[160,170,180,190\] / | | | \ ... ... ... ... 叶子节点 ↓ ↓ ↓ ↓ ↓ \[数据\] \[数据\] \[数据\] \[数据\] \[数据\] \-\- 数据都在叶子B+ 树的核心特征：
| 特征 | 说明 | 优势 |
|---|---|---|
| 所有数据在叶子节点 | 内部节点只存键值和指针 | 内部节点能存更多键 → 树更矮 |
| 叶子节点形成链表 | 叶子节点有指向下一个叶子节点的指针 | 范围查询高效 |
| 叶子节点存储数据 | 根据数据存储方式分为聚簇/二级索引 | 详见后文 |
| 节点大小 = 页大小 | MySQL 默认 16KB | 一次 I/O 读取一页 |
1.3 B+ 树的高度计算
python
\# 计算 B+ 树的高度（以 InnoDB 为例） import math \# 参数 page_size = 16 * 1024 \# 16KB key_size = 8 \# BIGINT 类型键值 8 字节 pointer_size = 6 \# 指针大小 6 字节 row_size = 200 \# 估算每行数据 200 字节 \# 每个非叶子节点可存储的键数量 slot_size = key_size + pointer_size \# 14 字节 keys\_per\_node = page_size // slot_size \# 16384 // 14 ≈ 1170 \# 每个叶子节点可存储的数据行数 rows\_per\_leaf = page_size // row_size \# 16384 // 200 ≈ 81 \# 计算 3 层 B+ 树能存储的行数 \# 层1（根）：1170 个指针 \# 层2：1170 * 1170 = 1,368,900 个指针 \# 层3（叶子）：1,368,900 * 81 ≈ 110,880,900 行 print(f"2层B+树可存储约 {1170 * 81:,} 行") \# 约 94,770 行 print(f"3层B+树可存储约 {1170 * 1170 * 81:,} 行") \# 约 1.1 亿行结论：B+ 树通常只有 2-4 层，意味着查找任何数据只需要 2-4 次磁盘 I/O。
1.4 B+ 树的查找过程
sql
\-\- 示例表 CREATE TABLE user ( id INT PRIMARY KEY, name VARCHAR(50), age INT, INDEX idx_age (age) ); \-\- 执行查询 SELECT * FROM user WHERE id = 25;查找过程（聚簇索引）：
text
1. 加载根节点到内存（磁盘I/O #1）
根节点包含：[10, 20, 30, 40, …] 的键值
判断 25 在 20 和 30 之间 → 走第二个指针
2. 加载第二层节点（磁盘I/O #2）
该节点包含：[21, 22, 23, 24, 25, 26, …]
找到 25 对应的指针
3. 加载叶子节点（磁盘I/O #3）
读取包含 id=25 的完整行数据
返回结果
二、聚簇索引 vs 二级索引
2.1 核心区别
| 特性 | 聚簇索引 | 二级索引 |
|---|---|---|
| 数据存储位置 | 叶子节点存储完整行数据 | 叶子节点存储主键值 |
| 每表数量 | 只有 1 个 | 可以有多个 |
| 默认索引 | PRIMARY KEY 自动创建 | 普通 INDEX / UNIQUE |
| 查询效率 | 直接找到数据（1次回表） | 找到主键后需要回表 |
| 占用空间 | 较大（存储完整行） | 较小（只存键+主键） |
2.2 聚簇索引结构
sql CREATE TABLE student ( id INT PRIMARY KEY, \-\- 聚簇索引 name VARCHAR(50), class VARCHAR(20), score INT );聚簇索引的 B+ 树结构：
text
内部节点（只存键值）： \[100, 200, 300, ...\] / | \ / | \ 叶子节点（存完整行数据）： ┌─────────────────────────────────────────────────────┐ │ 100 | name='Alice' | class='A' | score=95 │ ├─────────────────────────────────────────────────────┤ │ 101 | name='Bob' | class='A' | score=87 │ ├─────────────────────────────────────────────────────┤ │ 102 | name='Carol' | class='B' | score=92 │ ├─────────────────────────────────────────────────────┤ │ ... → 下一个叶子节点 │ └─────────────────────────────────────────────────────┘查询过程：
sql
SELECT * FROM student WHERE id = 101;
-- 直接命中叶子节点，一次 I/O 拿到所有数据
2.3 二级索引结构
sql
-- 创建二级索引
CREATE INDEX idx_name ON student(name);
二级索引的 B+ 树结构：
text
内部节点：索引键值 + 指针
[‘Bob’, ‘David’, ‘Frank’, …]
/ |
/ |
叶子节点：索引键值 + 主键值
┌─────────────────────────────────────────────────────┐
│ ‘Alice’ | 100 │
├─────────────────────────────────────────────────────┤
│ ‘Bob’ | 101 │
├─────────────────────────────────────────────────────┤
│ ‘Carol’ | 102 │
└─────────────────────────────────────────────────────┘
查询过程（需要回表）：
sql
SELECT * FROM student WHERE name = ‘Bob’;
-- 步骤1：在二级索引 idx_name 中查找 ‘Bob’
-- 找到主键值 101（磁盘I/O #1）
-- 步骤2：回表 - 用主键 101 到聚簇索引中查找完整数据
-- 找到完整行（磁盘I/O #2）
2.4 覆盖索引（避免回表）
sql
-- 如果查询只需要索引中的字段，无需回表
SELECT name FROM student WHERE name = ‘Bob’;
-- ✅ 直接在 idx_name 的叶子节点就能拿到 name，无需回表
SELECT id, name FROM student WHERE name = ‘Bob’;
-- ✅ id 是主键，也存储在 idx_name 的叶子节点
SELECT * FROM student WHERE name = ‘Bob’;
-- ❌ 需要回表，因为 * 包含 class 和 score
覆盖索引示例：
sql
-- 创建覆盖索引（包含所有查询字段）
CREATE INDEX idx_name_score ON student(name, score);
-- 下面的查询只需要这个索引，无需回表
SELECT name, score FROM student WHERE name = ‘Bob’;
SELECT id, name, score FROM student WHERE name = ‘Bob’;
三、最左匹配原则
3.1 核心原理
最左匹配原则：MySQL 使用联合索引时，会从左到右依次匹配查询条件，遇到范围查询（>、<、between、like）后停止匹配。
sql
-- 创建联合索引
CREATE INDEX idx_a_b_c ON table_name (a, b, c);
-- 索引的排序结构：
-- 先按 a 排序，a 相同再按 b 排序，b 相同再按 c 排序
3.2 索引排序可视化
sql
-- 表数据
INSERT INTO test VALUES
(1, 1, 1), (1, 1, 2), (1, 2, 1), (1, 2, 2),
(2, 1, 1), (2, 1, 2), (2, 2, 1), (2, 2, 2);
-- 联合索引 (a, b, c) 的排序结果：
(1,1,1) → (1,1,2) → (1,2,1) → (1,2,2) → (2,1,1) → (2,1,2) → (2,2,1) → (2,2,2)
3.3 哪些查询走索引？
| WHERE 条件 | 是否走索引 | 原因 |
|---|---|---|
a = 1 | ✅ 走索引 | 匹配第一列 |
a = 1 AND b = 2 | ✅ 走索引 | 匹配前两列 |
a = 1 AND b = 2 AND c = 3 | ✅ 走索引 | 匹配全部三列 |
b = 2 AND c = 3 | ❌ 不走索引 | 第一列缺失，无法定位 |
a = 1 AND c = 3 | ⚠️ 部分索引 | a 过滤后，c 无法用索引（中间缺 b） |
a > 1 AND b = 2 | ⚠️ 部分索引 | a 是范围查询，b 无法用索引 |
a = 1 AND b > 2 AND c = 3 | ⚠️ 部分索引 | b 是范围查询，c 无法用索引 |
3.4 详细分析
sql
-- 场景1：完美匹配 ✅
SELECT * FROM test WHERE a = 1 AND b = 2 AND c = 3;
-- 索引定位：(1,2,3) 精确位置
-- 场景2：左侧缺失 ❌
SELECT * FROM test WHERE b = 2 AND c = 3;
-- 无法使用索引，因为不知道 a 的值，无法定位起始位置
-- 场景3：中间缺失 ⚠️
SELECT * FROM test WHERE a = 1 AND c = 3;
-- 过程：
-- 1. 索引先按 a=1 定位到范围
-- 2. 但这个范围内，b 有多种值，c 不是有序的
-- 3. 只能用于过滤 a，c 需要回表后再过滤
-- 场景4：范围查询后的列失效 ⚠️
SELECT * FROM test WHERE a = 1 AND b > 2 AND c = 3;
-- 过程：
-- 1. a=1 定位
-- 2. b>2 范围查找，找到所有 b>2 的记录
-- 3. 在这个范围内，c 是无序的，无法用索引
-- 场景5：使用 ORDER BY（注意排序方向）
SELECT * FROM test WHERE a = 1 ORDER BY b, c;
-- ✅ 索引已经按 (a,b,c) 排序，直接取数据，无需 filesort
SELECT * FROM test WHERE a = 1 ORDER BY b DESC, c ASC;
-- ❌ 排序方向不一致，需要 filesort
3.5 最佳实践
sql
-- 1. 等值查询在前，范围查询在后
-- 推荐：
CREATE INDEX idx_status_time ON orders (status, created_at);
SELECT * FROM orders WHERE status = ‘paid’ AND created_at > ‘2024-01-01’;
-- 不推荐：
CREATE INDEX idx_time_status ON orders (created_at, status);
-- 原因：时间范围查询后，status 索引失效
-- 2. 区分度高的列在前
-- 假设 gender 只有 ‘M’/‘F’，user_id 唯一
-- 推荐：
CREATE INDEX idx_user_gender ON orders (user_id, gender);
-- 不推荐：
CREATE INDEX idx_gender_user ON orders (gender, user_id);
-- 3. 索引下推（ICP - Index Condition Pushdown）
-- MySQL 5.6+ 支持，可以在索引层面过滤，减少回表
四、索引失效场景（完整清单）
4.1 失效场景速查表
| 失效场景 | 示例 | 原因 |
|---|---|---|
| 函数操作 | WHERE YEAR(date) = 2024 | 索引存储的是原值，不是函数结果 |
| 类型转换 | WHERE phone = 13800138000（phone是varchar） | 隐式转换，函数操作 |
| 计算操作 | WHERE age + 1 = 25 | 对索引列计算 |
| LIKE ‘%abc’ | WHERE name LIKE '%Bob' | 通配符在前，无法匹配B+树排序 |
| OR 条件 | WHERE a = 1 OR b = 2 | OR 两边的列都需要索引 |
| NOT 条件 | WHERE a != 1/WHERE NOT (a=1) | 范围太大，优化器认为全表扫描更快 |
| IS NULL / IS NOT NULL | WHERE a IS NULL | 取决于 NULL 值比例 |
| 使用 != 或 <> | WHERE a <> 1 | 同 NOT 条件 |
| 联合索引未用最左列 | WHERE b = 1 AND c = 2 | 无法定位起始位置 |
| 范围查询后的列 | WHERE a = 1 AND b > 2 AND c = 3 | 范围后列无序 |
4.2 详细示例
sql
\-\- 表结构 CREATE TABLE user ( id INT PRIMARY KEY, name VARCHAR(50), age INT, email VARCHAR(100), phone VARCHAR(20), create_date DATE, INDEX idx_name (name), INDEX idx_age (age), INDEX idx_phone (phone), INDEX idx_date (create_date), INDEX idx\_name\_age (name, age) ); \-\- ❌ 1\. 对索引列使用函数 EXPLAIN SELECT * FROM user WHERE LOWER(name) = 'bob'; \-\- 解决：存储时统一小写，或使用虚拟列 \-\- ❌ 2\. 隐式类型转换 EXPLAIN SELECT * FROM user WHERE phone = 13800138000; \-\- phone 是 VARCHAR \-\- 实际执行：WHERE CAST(phone AS SIGNED) = 13800138000 \-\- ❌ 3\. 对索引列进行计算 EXPLAIN SELECT * FROM user WHERE age + 1 = 25; \-\- 改写为：WHERE age = 24 \-\- ❌ 4\. LIKE 前缀模糊匹配 EXPLAIN SELECT * FROM user WHERE name LIKE '%Bob%'; \-\- ✅ 可以使用：WHERE name LIKE 'Bob%' \-\- ❌ 5\. OR 条件（两边都需要独立索引） EXPLAIN SELECT * FROM user WHERE name = 'Bob' OR age = 25; \-\- 解决：UNION 或使用 IN (如果可能) \-\- ✅ OR 的替代方案 SELECT * FROM user WHERE name = 'Bob' UNION SELECT * FROM user WHERE age = 25; \-\- ❌ 6\. NOT 条件 EXPLAIN SELECT * FROM user WHERE name != 'Bob'; \-\- ❌ 7\. 联合索引未使用最左列 EXPLAIN SELECT * FROM user WHERE age = 25; \-\- idx\_name\_age 无效 \-\- 虽然 age 是索引第二列，但无法使用 \-\- ❌ 8\. 范围查询后的列 EXPLAIN SELECT * FROM user WHERE name = 'Bob' AND age > 25; \-\- 这个例子中 age 是范围，但如果后面还有列，后面列会失效 \-\- ⚠️ 9\. 数据分布不均（优化器选择） \-\- 如果表中 99% 的数据 age > 10，MySQL 可能选择全表扫描 EXPLAIN SELECT * FROM user WHERE age > 10;4.3 特殊情况：看似失效实则有效
sql
\-\- 1\. IS NULL 在某些情况下有效 EXPLAIN SELECT * FROM user WHERE name IS NULL; \-\- 如果 NULL 值很少，可能走索引 \-\- 2\. 使用索引列排序且无 WHERE EXPLAIN SELECT * FROM user ORDER BY name; \-\- 可以走索引，但可能不如 filesort 快 \-\- 3\. IN 查询可以走索引 EXPLAIN SELECT * FROM user WHERE name IN ('Bob', 'Alice', 'Tom'); \-\- IN 相当于多个等值查询 \-\- 4\. BETWEEN 对等值查询有效 EXPLAIN SELECT * FROM user WHERE age BETWEEN 20 AND 30; \-\- 范围查询，但后面的列会失效4.4 实战：优化 SQL 示例
sql
\-\- 原 SQL：各种问题 SELECT * FROM orders WHERE YEAR(create_time) = 2024 AND status != 'cancelled' AND amount + 10 > 100 AND user_phone = 13800138000 \-\- phone 是 VARCHAR ORDER BY create_time DESC; \-\- 优化后 CREATE INDEX idx\_create\_time_status ON orders(create_time, status); CREATE INDEX idx\_user\_phone ON orders(user_phone); SELECT * FROM orders WHERE create_time >= '2024-01-01' AND create_time < '2025-01-01' AND status IN ('pending', 'paid', 'shipped') \-\- 排除 cancelled AND amount > 90 \-\- 移除了计算 AND user_phone = '13800138000' \-\- 字符串 ORDER BY create_time DESC;五、总结与最佳实践
5.1 核心要点速记
text
B+ 树特征：
├── 所有数据在叶子节点
├── 叶子节点形成双向链表
└── 高度通常 2-4 层
聚簇索引：
├── 每表唯一，叶子存完整行
└── 主键自动创建
二级索引：
├── 每表多个，叶子存主键
└── 查询需要回表
最左匹配：
├── 联合索引从左到右匹配
├── 等值查询先于范围查询
└── 遇到范围查询后失效
失效场景：
├── 函数/计算/类型转换
├── LIKE ‘%xx’
├── OR 两边都要索引
└── 联合索引缺左列
5.2 设计建议
| 场景 | 建议 |
|---|---|
| 主键选择 | 使用自增 BIGINT，避免 UUID（插入随机，页分裂严重） |
| 索引数量 | 单表不超过 5-6 个，维护成本高 |
| 选择性 | 索引列区分度越高越好，性别类不适合单独建索引 |
| 覆盖索引 | 高频查询字段建覆盖索引，避免回表 |
| 顺序 | 等值查询列在前，范围查询列在后 |
5.3 验证方法
sql
-- 使用 EXPLAIN 分析查询
EXPLAIN SELECT * FROM user WHERE name = ‘Bob’;
-- 关键字段：
-- type: const > ref > range > index > ALL（越左越好）
-- key: 实际使用的索引名
-- rows: 扫描行数，越小越好
-- Extra: Using index（覆盖索引）、Using filesort（需要排序）
-- 使用 FORCE INDEX 测试
SELECT * FROM user FORCE INDEX(idx_name) WHERE name = ‘Bob’;
-- 查看索引使用情况
SHOW INDEX FROM user;
