MySQL 索引原理详解 ⭐⭐⭐

面试题：说一下 B+ 树索引实现原理

核心回答

MySQL InnoDB 存储引擎使用 B+ 树作为索引的数据结构，B+ 树是一种多路平衡查找树，专为磁盘存储优化设计。

为什么使用 B+ 树？

磁盘 IO 优化：

对比其他数据结构：

数据结构 问题 B+ 树优势
二叉搜索树 可能退化成链表，高度不平衡 多叉树，高度低且平衡
AVL/红黑树 二叉树，高度较高 多叉树，减少磁盘 IO 次数
B 树 非叶子节点也存数据，范围查询慢 数据只存叶子节点，范围查询快
哈希表 不支持范围查询 支持高效的范围查询

B+ 树的结构特点

                    [10, 20, 30]                    ← 根节点（非叶子节点）
                   /    |    \
            [5,8]   [15,18]   [25,28]   [35,40]     ← 内部节点
           /  |      |   |      |   |      |   \
    [1,2,3,4][6,7][11,12][16,17][21,22][26,27][31,32][36,37]  ← 叶子节点（存数据）
       ↓       ↓      ↓      ↓      ↓      ↓      ↓      ↓
    链表连接（便于范围查询）

核心特点：

  1. 多叉树：每个节点可存储多个键值，降低树高
  2. 数据只存叶子节点：非叶子节点只存键值和指针，可存储更多索引
  3. 叶子节点有序链表连接：支持高效的范围查询和排序
  4. 高度平衡：所有叶子节点到根节点距离相同

B+ 树 vs B 树

特性 B 树 B+ 树
数据存储 所有节点都存数据 只有叶子节点存数据
叶子节点 无链表连接 有序链表连接
范围查询 需中序遍历 直接遍历叶子节点链表
查询稳定性 可能在非叶子节点找到 必须查到叶子节点，稳定性好
空间利用率 较低 较高

InnoDB 索引类型

1. 聚簇索引（Clustered Index）

特点：

默认聚簇索引：

聚簇索引结构：
[主键值] → [完整行数据]

2. 非聚簇索引（Secondary Index）

特点：

非聚簇索引结构：
[索引列值] → [主键值]

回表查询：

-- 假设有索引 idx_name(name)
SELECT * FROM user WHERE name = '张三';
-- 1. 在 idx_name 索引找到 name='张三' 对应的主键值
-- 2. 用主键值在聚簇索引中查找完整行数据

3. 覆盖索引（Covering Index）

定义：查询的所有列都在索引中，无需回表。

-- 索引：idx_name_age(name, age)
SELECT name, age FROM user WHERE name = '张三';
-- name 和 age 都在索引中，无需回表

索引查询过程

SELECT * FROM user WHERE id = 10086;

查询步骤：

  1. 加载根节点：从磁盘加载 B+ 树根节点到内存
  2. 二分查找：在节点内二分查找，确定下一层节点
  3. 逐层下降：重复步骤 1-2，直到叶子节点
  4. 获取数据：在叶子节点找到对应记录

示例：

根节点：[1000, 5000, 15000, 30000]
查找 id=10086：
1. 10086 > 1000, 继续
2. 10086 > 5000, 继续
3. 10086 < 15000, 进入 5000-15000 区间

内部节点：[5100, 7500, 10000, 12500]
4. 10086 > 5100, 继续
5. 10086 > 7500, 继续
6. 10086 > 10000, 继续
7. 10086 < 12500, 进入 10000-12500 区间

叶子节点：[10001, 10020, 10050, 10086, 10100]
8. 找到 id=10086，返回完整数据

索引设计原则

1. 最左前缀原则

-- 联合索引：idx_a_b_c(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 a = 1 AND c = 3    -- 部分使用（只用 a）

2. 索引选择性

选择性 = 不重复值数量 / 总记录数，越接近 1 越好。

-- 不好的索引：性别（选择性低，只有男/女）
-- 好的索引：手机号、身份证号（选择性高）

3. 避免冗余索引

-- 已有索引 (a, b)，再建 (a) 就是冗余
ALTER TABLE t ADD INDEX idx_a(a);
ALTER TABLE t ADD INDEX idx_ab(a, b);  -- idx_a 可以删除

索引失效场景

-- 1. 使用函数
WHERE YEAR(create_time) = 2024  -- 失效
WHERE create_time >= '2024-01-01' AND create_time < '2025-01-01'  -- 有效

-- 2. 类型转换
WHERE phone = 13800138000  -- phone 是 varchar，会隐式转换，失效
WHERE phone = '13800138000'  -- 有效

-- 3. 使用 != 或 <>
WHERE age != 18  -- 可能失效（取决于数据分布）

-- 4. LIKE 以 % 开头
WHERE name LIKE '%张%'  -- 失效
WHERE name LIKE '张%'   -- 有效（使用索引）

-- 5. OR 条件
WHERE id = 1 OR age = 20  -- 如果 age 没有索引，可能失效

-- 6. 联合索引不满足最左前缀
-- 索引 (a, b, c)
WHERE b = 2 AND c = 3  -- 失效

索引优化技巧

1. 覆盖索引优化

-- 优化前：需要回表
SELECT id, name, age FROM user WHERE name = '张三';

-- 优化后：创建覆盖索引，无需回表
ALTER TABLE user ADD INDEX idx_name_age(name, age);
SELECT id, name, age FROM user WHERE name = '张三';

2. 索引下推（Index Condition Pushdown）

MySQL 5.6+ 特性，在存储引擎层过滤数据，减少回表次数。

-- 索引：idx_name_age(name, age)
SELECT * FROM user WHERE name LIKE '张%' AND age = 20;

-- 没有 ICP：先找到所有 name LIKE '张%' 的记录，再回表过滤 age
-- 有 ICP：在存储引擎层就过滤 age=20，减少回表

3. 前缀索引

-- 对于长字符串，使用前缀索引
ALTER TABLE user ADD INDEX idx_email(email(10));

-- 计算合适的前缀长度
SELECT 
    COUNT(DISTINCT LEFT(email, 5)) / COUNT(DISTINCT email) as sel5,
    COUNT(DISTINCT LEFT(email, 10)) / COUNT(DISTINCT email) as sel10
FROM user;

高频面试题

Q1: 为什么 InnoDB 选择 B+ 树而不是 B 树？

  1. B+ 树数据只存叶子节点：非叶子节点可存储更多键值，树更矮，IO 更少
  2. B+ 树叶子节点链表连接：范围查询只需遍历链表，B 树需中序遍历
  3. B+ 树查询更稳定：所有查询都到叶子节点，性能一致

Q2: 什么是回表？如何避免？

Q3: 聚簇索引和非聚簇索引的区别？

特性 聚簇索引 非聚簇索引
叶子节点数据 完整行数据 主键值
数量 一个表只有一个 可以有多个
查询效率 高（直接取数据） 可能需要回表
插入效率 需要维护数据顺序 只需维护索引

Q4: 联合索引 (a, b, c) 的查询使用情况？

WHERE a = 1              -- 使用索引
WHERE a = 1 AND b = 2    -- 使用索引
WHERE a = 1 AND c = 3    -- 使用 a 列
WHERE b = 2              -- 不使用索引
WHERE a = 1 AND b > 2 AND c = 3  -- 使用 a, b，c 不使用（b 是范围查询）

Q5: 一个 B+ 树能存多少数据？

假设：

计算：

参考链接：