K
💻CS 数据库

MySQL 索引与 B+ 树

难度：⭐⭐ | 高频指数：🔥🔥🔥

面试回答

常见问法

  • 为什么 MySQL 用 B+ 树做索引，不用 B 树、红黑树或哈希？
  • 聚簇索引和非聚簇索引有什么区别？
  • 什么是覆盖索引？
  • 最左前缀原则是什么？
  • 哪些情况会导致索引失效？

回答

为什么用 B+ 树：

数据结构不适合做索引的原因
哈希表不支持范围查询、不支持排序
红黑树树高太大（O(log₂n)），磁盘 IO 次数多
B 树非叶子节点也存数据，每个节点能放的 key 少，树更高
B+ 树 ✓非叶子节点只存 key，更矮更胖；叶子节点链表连接，范围查询高效

B+ 树的核心优势：

  1. 非叶子节点只存索引 key，一个节点能放更多 key，树更矮（通常 3-4 层）
  2. 叶子节点通过双向链表连接，范围查询只需遍历链表
  3. 所有数据都在叶子节点，查询路径长度一致，性能稳定

聚簇索引 vs 非聚簇索引：

  • 聚簇索引（主键索引）：叶子节点存储完整的行数据。InnoDB 的主键索引就是聚簇索引。
  • 非聚簇索引（二级索引）：叶子节点存储主键值。查询时如果需要其他列，要回表（用主键再查一次聚簇索引）。

追问

1. 什么是覆盖索引？

如果一个查询所需的所有列都在索引中，不需要回表，就叫覆盖索引。

-- 假设有联合索引 (name, age)
SELECT name, age FROM users WHERE name = '张三';
-- 索引中已经有 name 和 age，不需要回表 → 覆盖索引

2. 最左前缀原则？

联合索引 (a, b, c) 相当于创建了 (a)、(a, b)、(a, b, c) 三个索引。查询条件必须从最左列开始匹配才能用到索引。

-- 能用到索引
WHERE a = 1
WHERE a = 1 AND b = 2
WHERE a = 1 AND b = 2 AND c = 3

-- 不能用到索引
WHERE b = 2
WHERE b = 2 AND c = 3
WHERE c = 3

3. 索引失效的常见场景？

  • 对索引列使用函数：WHERE YEAR(create_time) = 2024
  • 隐式类型转换：WHERE varchar_col = 123（字符串列用数字查）
  • LIKE 左模糊：WHERE name LIKE '%张'
  • OR 条件中有非索引列
  • 不满足最左前缀
  • 索引列参与计算：WHERE age + 1 = 18

原理展开

1. B+ 树结构

                    [10 | 20 | 30]              ← 根节点（非叶子）
                   /    |     |    \
        [1|3|5|8] [10|12|15] [20|22|25] [30|35|40]  ← 叶子节点
            ↔          ↔          ↔          ↔      ← 双向链表

InnoDB 中一个节点 = 一个页（16KB）：

  • 假设主键是 bigint（8B），指针 6B，一个非叶子节点能放约 16KB / 14B ≈ 1170 个 key
  • 三层 B+ 树：1170 × 1170 × 16 ≈ 2000 万行数据
  • 所以大部分表只需要 3 次磁盘 IO 就能定位到数据

2. 聚簇索引的存储方式

主键索引（聚簇索引）：
叶子节点存储：[主键值 | 完整行数据]

二级索引：
叶子节点存储：[索引列值 | 主键值]

回表过程：
1. 在二级索引中找到主键值
2. 用主键值去聚簇索引中查找完整行数据

为什么 InnoDB 必须有主键：

  • 聚簇索引需要主键来组织数据
  • 如果没有显式主键，InnoDB 会选择唯一非空索引
  • 如果都没有，InnoDB 会生成隐藏的 6 字节 row_id

3. 联合索引的存储结构

联合索引 (a, b, c) 的 B+ 树：
按 a 排序，a 相同按 b 排序，b 相同按 c 排序

叶子节点：
[1,1,1] [1,1,2] [1,2,1] [2,1,1] [2,1,3] [2,2,1]

最左前缀原则的本质：

  • B+ 树是按索引列的顺序排序的
  • 跳过前面的列，后面的列就不是有序的，无法利用索引

4. 索引下推（Index Condition Pushdown）

-- 联合索引 (name, age)
SELECT * FROM users WHERE name LIKE '张%' AND age = 25;

没有索引下推：

  1. 用索引找到所有 name 以”张”开头的记录
  2. 回表取完整行
  3. 在服务层过滤 age = 25

有索引下推（MySQL 5.6+）：

  1. 用索引找到所有 name 以”张”开头的记录
  2. 在索引层直接过滤 age = 25（因为索引中有 age）
  3. 只对满足条件的记录回表

减少了回表次数，提升性能。

5. 索引设计原则

选择性高的列优先：

  • 选择性 = 不同值的数量 / 总行数
  • 性别（男/女）选择性低，不适合单独建索引
  • 手机号选择性高，适合建索引

常用的索引优化策略：

-- 1. 覆盖索引避免回表
CREATE INDEX idx_name_age ON users(name, age);
SELECT name, age FROM users WHERE name = '张三';  -- 不回表

-- 2. 前缀索引节省空间
CREATE INDEX idx_email ON users(email(10));  -- 只索引前 10 个字符

-- 3. 联合索引顺序：选择性高的放前面
CREATE INDEX idx_status_city ON orders(city, status);
-- city 选择性高于 status，放前面

6. 为什么不用哈希索引

哈希索引的限制：

  • 不支持范围查询（WHERE age > 18）
  • 不支持排序（ORDER BY）
  • 不支持最左前缀匹配
  • 哈希冲突时性能退化

Memory 引擎默认用哈希索引，适合等值查询场景。 InnoDB 的自适应哈希索引：InnoDB 会自动为热点页建立哈希索引，加速等值查询。

7. EXPLAIN 分析索引使用

EXPLAIN SELECT * FROM users WHERE name = '张三';

关键字段：

  • type：访问类型。const > eq_ref > ref > range > index > ALL
  • key：实际使用的索引
  • rows：预估扫描行数
  • Extra：
    • Using index：覆盖索引
    • Using index condition：索引下推
    • Using filesort：需要额外排序
    • Using temporary：需要临时表

易错点

  • 说”B+ 树比 B 树快”——不是快，是磁盘 IO 少。B+ 树非叶子节点不存数据，一个节点能放更多 key，树更矮。
  • 混淆聚簇索引和主键——聚簇索引是一种存储方式，主键是逻辑概念。InnoDB 中主键索引恰好是聚簇索引。
  • 说”建了索引查询就快”——索引失效、选择性低、数据量小时索引可能不生效。
  • 忘记回表的概念——二级索引查询如果需要非索引列，必须回表。
  • 说”联合索引 (a,b,c) 能加速 WHERE b=1”——不满足最左前缀，用不到索引。
  • 不知道 EXPLAIN——面试中经常问”怎么判断索引是否生效”。

记忆技巧

  • B+ 树三大优势：矮（IO 少）、链（范围快）、稳（路径等长）
  • 聚簇 vs 非聚簇：聚簇存数据，非聚簇存主键（要回表）
  • 最左前缀口诀：联合索引从左匹配，跳列就废
  • 索引失效六大场景：函数、转换、左模糊、OR、跳列、计算
  • 三层 B+ 树：约 2000 万行，3 次 IO

面试速答版

MySQL InnoDB 用 B+ 树做索引，因为非叶子节点只存 key 使树更矮（3 层可存 2000 万行），叶子节点链表连接支持高效范围查询。聚簇索引叶子节点存完整行数据（主键索引），非聚簇索引叶子节点存主键值（需要回表）。覆盖索引是查询列都在索引中不需要回表。联合索引遵循最左前缀原则，必须从最左列开始匹配。索引失效常见场景：对索引列用函数、隐式类型转换、左模糊 LIKE、不满足最左前缀。用 EXPLAIN 分析索引使用情况。

Related · 数据库
MySQL 索引与 B+ 树锁与并发控制