MySQL 索引底层 B+ 树原理
有一次线上出现了慢查询，DBA 让我加个索引，我二话不说就加了，结果性能反而更差了。那时候我就意识到，不懂索引底层原理，加索引就是在碰运气。
今天咱们就来扒一扒 MySQL InnoDB 引擎里索引的底层结构——B+ 树，看完这篇，你就能明白为什么有时候索引能救命，有时候却是累赘。
为什么不用二叉搜索树？
先别急着看 B+ 树，咱们先想想，为什么 MySQL 不用二叉搜索树（BST）？
假设我们有一张用户表，主键是 id，数据是这样的：
id: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10...
如果用二叉搜索树存，大概长这样：
5
/ \
2 8
/ \ / \
1 3 6 9
\ \
4 10
```
看着挺均匀对吧？但问题是**树的高度**。
如果有 100 万条数据，二叉搜索树的高度大概是 log₂(1000000) ≈ 20 层。每次查询要从根节点找到叶子节点，意味着要访问 20 次节点。
**关键点来了**：数据库的数据是存在磁盘上的，每次访问一个节点，就要进行一次磁盘 I/O。20 次磁盘 I/O，就算固态硬盘也扛不住啊！
## 多路平衡树（B 树）登场
既然二叉树太"瘦高"，那我们就搞个"矮胖"的树——每个节点存更多的关键字，降低树的高度。
这就是 B 树（Balance Tree）的思路：
[node0: 10, 20]
/ |
[node1] [node2] [node3]
```
一个节点可以存多个关键字，假设每个节点最多存 100 个关键字，那 100 万条数据，树的高度只需要 log₁₀₀(1000000) ≈ 3 层！
但是，B 树有个问题：范围查询效率低。
比如你要查 id between 10 and 100，用 B 树的话，得从一个叶子节点跳到另一个叶子节点，而这些叶子节点之间没有指针连接，只能回到父节点重新遍历。
B+ 树：MySQL 的最终选择
InnoDB 存储引擎用的是 B+ 树，它在 B 树的基础上做了两个关键改造：
改造 1：数据只存在叶子节点
B 树的非叶子节点既存关键字，也存数据。而 B+ 树的非叶子节点只存关键字和子节点指针，所有的数据都存储在叶子节点。
B 树（非叶子节点存数据）:
[node: key1+data1, key2+data2 | ptr1, ptr2, ptr3]
B+ 树（非叶子节点只存关键字）:
[node: key1, key2 | ptr1, ptr2, ptr3]
叶子节点: key1+data1, key2+data2, ...
这样做的好处是：非叶子节点能存更多的关键字。一个 16KB 的页（InnoDB 的页大小是 16KB），如果只存关键字和指针，大概能存 1000 个关键字。那 3 层 B+ 树就能存 1000 × 1000 × 1000 = 10 亿条数据！
改造 2：叶子节点用双向链表连接
这是 B+ 树最巧妙的地方。所有叶子节点按照关键字顺序，用双向链表连接起来：
叶子节点1 ←→ 叶子节点2 ←→ 叶子节点3 ←→ ...
[1,2,3] [4,5,6] [7,8,9]
这样做的好处是什么？ 范围查询简直飞起！
比如要查 id between 10 and 100：
- 先从 B+ 树找到
id=10的叶子节点（3 次 I/O） -
- 然后顺着链表往后扫，直到
id=100（顺序 I/O，超快）
如果是 B 树，第二步就得来回跳，效率天差地别。
- 然后顺着链表往后扫，直到
InnoDB 的 B+ 树长啥样？
咱们来点实际的，看看 InnoDB 的 B+ 树到底怎么存的。
页（Page）是基本单位
InnoDB 的所有数据都存在**页（Page）**里，每个页固定 16KB。B+ 树的每个节点，就是一个页。
一个页的结构大概是这样：
+----------------------------------+
| 文件头 (38 bytes) |
+----------------------------------+
| 数据页头 (56 bytes) |
+----------------------------------+
| Infimum + Supremum 记录 |
+----------------------------------+
| 用户记录（你的数据行） |
+----------------------------------+
| 空闲空间 |
+----------------------------------+
| 页目录（目录槽） |
+----------------------------------+
| 文件尾 (8 bytes) |
+----------------------------------+
聚集索引（Clustered Index）
InnoDB 的主键索引就是聚集索引，B+ 树的叶子节点存的是完整的行数据。
假设我们有张用户表：
CREATE TABLE users (
id INT PRIMARY KEY,
name VARCHAR(50),
age INT
);
INSERT INTO users VALUES
(1, 'Alice', 25),
(2, 'Bob', 30),
(3, 'Charlie', 35),
...
(1000, 'Zack', 40);
那聚集索引的 B+ 树大概长这样：
[根节点/页]
key: 500 | ptr1, ptr2
/ \
/ \
[非叶子节点1] [非叶子节点2]
key: 250, 500 key: 750, 1000
/ | \ / | \
/ | \ / | \
[叶子1] [叶子2] [叶子3] [叶子4] [叶子5] [叶子6]
id:1-249 250-499 500-749 750-1000
```
**注意**：叶子节点之间是双向链表连接的，我这里没画出来。
### 二级索引（Secondary Index）
如果你在 `name` 字段上建索引：
```sql
CREATE INDEX idx_name ON users(name);
这个 idx_name 就是二级索引，它的 B+ 树叶子里存的是 name 和主键值，不是完整行数据。
二级索引 idx_name 的 B+ 树：
叶子节点: [name='Alice', id=1], [name='Bob', id=2], ...
那如果用二级索引查询会发生什么？
SELECT * FROM users WHERE name = 'Alice';
执行流程：
- 在
idx_name的 B+ 树里找到name='Alice'的叶子节点，拿到id=1 -
- 回表：拿着
id=1去聚集索引的 B+ 树里找完整行数据
所以，二级索引查询要遍历两棵 B+ 树，比主键查询慢。
- 回表：拿着
B+ 树的高度一般是多少？
前面咱们算过，假设每个非叶子节点能存 1000 个关键字，那：
- 1 层：1000 条数据
-
- 2 层：1000 × 1000 = 100 万条
-
- 3 层：1000 × 1000 × 1000 = 10 亿条
实际情况呢？我拿我们线上一个 500 万行的表测试过，用这个 SQL 能看到索引树的高度：
- 3 层：1000 × 1000 × 1000 = 10 亿条
SELECT
b.name AS index_name,
a.name AS table_name,
file_format,
row_format,
page_no,
page_type
FROM information_schema.innodb_sys_tables a
JOIN information_schema.innodb_sys_indexes b ON a.table_id = b.table_id
WHERE a.name = 'your_database/your_table';
```
实际上，大多数 MySQL 表的索引 B+ 树高度都是 **2~3 层**，4 层的都很少见。
这也是为什么 MySQL 官方说，单表数据量超过 2000 万才需要考虑分表——因为 3 层 B+ 树足够撑起这个数据量了。
## 插入数据时 B+ 树会怎么变？
前面咱们说的都是查询，那插入数据呢？B+ 树怎么保持平衡？
### 页分裂（Page Split）
假设一个页最多能存 3 条记录，现在页里已经有 `[10, 20, 30]` 了，再来个 `id=15` 的记录：
原来: [10, 20, 30]
插入15后: [10, 15, 20, 30] ← 溢出了！
这时候就会发生**页分裂**：
1. 创建一个新的页
2. 2. 把原页的一半数据搬到新页
3. 3. 在非叶子节点记录新页的指针
分裂后:
原页: [10, 15]
新页: [20, 30]
非叶子节点: key=20 | ptr_old, ptr_new
**页分裂的代价很高**，因为要搬数据、更新父节点。所以 InnoDB 有**页合并**（Page Merge）机制：如果两个相邻的页数据很少，会合并成一个页，避免空间浪费。
## 为什么建议用自增主键？
现在你能猜到答案了吧？
如果用 UUID 或者雪花算法生成的主键，插入是无序的，会导致：
- **频繁的页分裂**：新插入的数据可能要插到某个页的中间，导致那个页分裂
- - **随机 I/O**：页分裂会产生大量随机磁盘 I/O，性能差
而自增主键（`AUTO_INCREMENT`）是递增的，新数据永远插到 B+ 树的最右边：
- **几乎不会页分裂**：新数据直接加在最后一个叶子节点后面
- - **顺序 I/O**：磁盘写入是顺序的，性能炸裂
当然，自增主键也有缺点（比如分库分表时可能冲突），但在单机场景下，自增主键确实是最优选择。
## 实战建议
说了这么多原理，给几个实战建议：
### 1. 主键别太长
前面说过，非叶子节点存的是主键关键字。如果主键是 UUID（36 个字符），那一个 16KB 的页能存多少个关键字？远远少于用 INT（4 字节）或 BIGINT（8 字节）。
**结论**：主键越小，非叶子节点能存的关键字越多，B+ 树越"矮胖"，查询越快。
### 2. 别建太多索引
每个二级索引都是一棵独立的 B+ 树。如果你建了 10 个索引，那插入一条数据时，要更新 10 棵 B+ 树（1 棵聚集索引 + 9 棵二级索引）。
**结论**：索引不是越多越好，只建必要的。
### 3. 用 EXPLAIN 看是不是真的用了索引
有时候你以为用了索引，其实没有。比如：
```sql
-- 索引: idx_name (name)
-- 这个会用索引
SELECT * FROM users WHERE name = 'Alice';
-- 这个不会用索引（因为用了函数）
SELECT * FROM users WHERE LEFT(name, 5) = 'Alice';
用 EXPLAIN 看看执行计划，确认走了索引再上线。
总结
- B+ 树是 MySQL InnoDB 的索引底层结构，核心优势是矮胖（减少磁盘 I/O）和叶子节点链表（范围查询快）
-
- 聚集索引的叶子节点存完整行数据，二级索引的叶子节点存主键值（需要回表）
-
- B+ 树一般 2~3 层，能撑起千万级数据量
-
- 用自增主键能减少页分裂，提升插入性能
-
- 索引不是越多越好，要用
EXPLAIN验证
如果你能把这些点讲清楚，面试的时候绝对是加分项。就算没面试，懂了这些，你也能更好地设计表结构和索引，少踩坑。
- 索引不是越多越好，要用
参考资料：
- 《MySQL 技术内幕：InnoDB 存储引擎》
-
- MySQL 官方文档：InnoDB Index Tree Structure
-
- 姜承尧《MySQL 内核：InnoDB 存储引擎》
实战代码都在我本地跑过，你可以放心复制。 如果有问题，欢迎评论区交流，我看到就回。
- 姜承尧《MySQL 内核：InnoDB 存储引擎》
AtomGit 是由开放原子开源基金会联合 CSDN 等生态伙伴共同推出的新一代开源与人工智能协作平台。平台坚持“开放、中立、公益”的理念，把代码托管、模型共享、数据集托管、智能体开发体验和算力服务整合在一起，为开发者提供从开发、训练到部署的一站式体验。
更多推荐
2
0- 0
已为社区贡献7条内容
所有评论(0)