164 lines
6.4 KiB
Markdown
164 lines
6.4 KiB
Markdown
|
---
|
|||
|
|
tags: [mysql, bplus-tree, clustered-index, secondary-index, page-split]
|
|||
|
|
create time: 2026-08-08 18:00
|
|||
|
|
update time: 2026-08-08 18:00
|
|||
|
|
---
|
|||
|
|
|
|||
|
|
# B+树索引原理
|
|||
|
|
|
|||
|
|
## 概述
|
|||
|
|
|
|||
|
|
InnoDB 存储引擎的默认索引结构是 B+树（Balanced Plus Tree），它是 MySQL 实现高效范围查询和精确匹配的核心数据结构。理解 B+树的设计哲学——为什么选它而不是 B 树或红黑树——是掌握 MySQL 查询性能底层逻辑的第一步。
|
|||
|
|
|
|||
|
|
## 核心原理
|
|||
|
|
|
|||
|
|
### B 树与 B+树的本质区别
|
|||
|
|
|
|||
|
|
B+树并非独立发明，而是 B 树的演化版本。两者的核心差异在于**数据存放位置**：
|
|||
|
|
|
|||
|
|
- **B 树**：每个节点都存储键值和对应数据记录
|
|||
|
|
- **B+树**：非叶子节点只存键（不存数据），所有数据统一在叶子节点
|
|||
|
|
|
|||
|
|
这意味着同样大小的页（通常 16KB），B+树的非叶子节点可以容纳更多键，从而降低树的高度。
|
|||
|
|
|
|||
|
|
| 对比维度 | B 树 | B+树 |
|
|||
|
|
|---------|------|------|
|
|||
|
|
| 数据存储 | 所有节点均存数据 | 仅叶子节点存数据 |
|
|||
|
|
| 非叶子节点作用 | 既做路由又存数据 | 纯路由，无数据负担 |
|
|||
|
|
| 叶子节点连接 | 无连接 | 双向链表串联 |
|
|||
|
|
| 范围查询 | 需中序遍历，效率低 | 直接遍历叶子链表，一步到位 |
|
|||
|
|
| 磁盘 IO 次数 | 较高 | 更低（同等数据量下树更矮） |
|
|||
|
|
| 查询稳定性 | 不同路径长度可能不同 | 所有查询路径等长 |
|
|||
|
|
|
|||
|
|
```mermaid
|
|||
|
|
graph TD
|
|||
|
|
subgraph "B 树 - 每个节点含数据"
|
|||
|
|
B_Root["根节点\nK1 D1"] -->|"≤K1"| B_L["左子节点\nK2 D2"]
|
|||
|
|
B_Root -->|"K1<K≤K2"| B_M["中间节点\nK3 D3"]
|
|||
|
|
B_Root -->|">K2"| B_R["右子节点\nK4 D4"]
|
|||
|
|
end
|
|||
|
|
|
|||
|
|
subgraph "B+树 - 仅叶子节点含数据"
|
|||
|
|
N_Root["根节点\nK2"] -->|"≤K2"| N_Inter["内节点\nK1 K3"]
|
|||
|
|
N_Root -->|">K2"| N_Right["内节点\nK4 K5"]
|
|||
|
|
N_Inter -->|"≤K1"| L1["叶子 K1→D1"]
|
|||
|
|
N_Inter -->|"K1~K3"| L2["叶子 K2→D2"]
|
|||
|
|
N_Inter -->|"K3~K4"| L3["叶子 K3→D3"]
|
|||
|
|
N_Right -->|"K4~K5"| L4["叶子 K4→D4"]
|
|||
|
|
N_Right -->|">K5"| L5["叶子 K5→D5"]
|
|||
|
|
L1 -.->|"双向链表"| L2
|
|||
|
|
L2 -.-> L3
|
|||
|
|
L3 -.-> L4
|
|||
|
|
L4 -.-> L5
|
|||
|
|
end
|
|||
|
|
```
|
|||
|
|
|
|||
|
|
> [!NOTE] 关键直觉
|
|||
|
|
> 树的高度每降低一层，意味着一次查询减少一次磁盘 IO。B+树通过让内节点只存索引而不存数据，让单个页能放下更多键，从而将 1 亿行数据的树高控制在 3~4 层，而 B 树可能需要 4~5 层。
|
|||
|
|
|
|||
|
|
### 页分裂与页合并机制
|
|||
|
|
|
|||
|
|
B+树的每个节点对应 InnoDB 的一个数据页（Page），默认大小为 16KB。当数据插入导致页满时，触发再平衡操作。
|
|||
|
|
|
|||
|
|
**页分裂规则**：
|
|||
|
|
- 原页保留最左侧约一半的记录，新页获得剩余记录
|
|||
|
|
- 父节点增加一个分割键（split key），指向新页
|
|||
|
|
- 如果父节点也满了，递归向上分裂，直到找到不满的父节点或到达根节点
|
|||
|
|
- 根节点分裂时，树的高度 +1
|
|||
|
|
|
|||
|
|
**页合并规则**：
|
|||
|
|
- 删除操作使页填充率低于一定阈值（默认约 50%，可通过 `innodb_fill_factor` 调整）时，尝试与相邻页合并
|
|||
|
|
- 合并方向优先选择右侧页；若右侧页也无法合并，则尝试左侧
|
|||
|
|
- 合并后，父节点中的分割键被移除
|
|||
|
|
|
|||
|
|
> [!WARNING] 常见误区
|
|||
|
|
> 很多人认为页分裂发生在"页使用率达到 100%"时，实际上 InnoDB 在预分页阶段就会考虑空间利用率。InnoDB 采用"首次分裂占 7/8，后续平分"的策略来预留碎片空间，避免频繁分裂。
|
|||
|
|
|
|||
|
|
### 聚簇索引与非聚簇索引
|
|||
|
|
|
|||
|
|
这是 InnoDB 索引体系中最核心的概念之一。
|
|||
|
|
|
|||
|
|
**聚簇索引（Clustered Index）**：
|
|||
|
|
- InnoDB 的数据文件和索引文件是同一份——这就是"聚簇"的含义
|
|||
|
|
- 主键索引就是聚簇索引，叶子节点存储整行完整数据
|
|||
|
|
- 一张表有且仅有**一个**聚簇索引
|
|||
|
|
|
|||
|
|
**二级索引（Secondary Index / Non-Clustered Index）**：
|
|||
|
|
- 除主键之外的所有索引都是二级索引
|
|||
|
|
- 叶子节点存储的是**索引列的值 + 主键值**，而非完整行数据
|
|||
|
|
- 通过二级索引查到主键后，再用主键回表查询完整数据
|
|||
|
|
|
|||
|
|
```mermaid
|
|||
|
|
graph LR
|
|||
|
|
subgraph "聚簇索引（主键索引）叶子节点"
|
|||
|
|
CI1["PK=1 → 完整行"]
|
|||
|
|
CI2["PK=5 → 完整行"]
|
|||
|
|
CI3["PK=10 → 完整行"]
|
|||
|
|
end
|
|||
|
|
|
|||
|
|
subgraph "二级索引（name字段）叶子节点"
|
|||
|
|
SI1["name='Alice' → PK=1"]
|
|||
|
|
SI2["name='Bob' → PK=5"]
|
|||
|
|
SI3["name='Charlie' → PK=10"]
|
|||
|
|
end
|
|||
|
|
|
|||
|
|
SI1 --> CI1
|
|||
|
|
SI2 --> CI2
|
|||
|
|
SI3 --> CI3
|
|||
|
|
```
|
|||
|
|
|
|||
|
|
> [!TIP] 面试常考点
|
|||
|
|
> 问："为什么主键要尽量短？" 答案：因为所有二级索引叶子节点都存储了主键值，主键越长，二级索引越大，内存中能缓存的索引页数越少，命中率越低。这也是推荐使用自增 BIGINT 而非 UUID 作为主键的原因之一。
|
|||
|
|
|
|||
|
|
### 覆盖索引的起点
|
|||
|
|
|
|||
|
|
B+树的二级索引结构天然支持"覆盖索引"优化——当查询的列全部存在于某个二级索引中时，无需回表即可返回结果。这一话题将在 [[覆盖索引与回表优化]] 中详细展开。
|
|||
|
|
|
|||
|
|
## 代码示例
|
|||
|
|
|
|||
|
|
以下 SQL 演示如何通过执行计划观察聚簇索引与二级索引的使用差异：
|
|||
|
|
|
|||
|
|
```sql
|
|||
|
|
-- 建表并建立索引
|
|||
|
|
CREATE TABLE users (
|
|||
|
|
id BIGINT AUTO_INCREMENT PRIMARY KEY,
|
|||
|
|
name VARCHAR(64) NOT NULL,
|
|||
|
|
email VARCHAR(128) UNIQUE,
|
|||
|
|
age INT NOT NULL,
|
|||
|
|
INDEX idx_name_age (name, age)
|
|||
|
|
);
|
|||
|
|
|
|||
|
|
-- 使用覆盖索引：不需要回表
|
|||
|
|
EXPLAIN SELECT name FROM users WHERE name = 'Alice';
|
|||
|
|
-- Extra: Using index （直接从 idx_name_age 二级索引获取 name）
|
|||
|
|
|
|||
|
|
-- 需要回表：二级索引查不到所需列
|
|||
|
|
EXPLAIN SELECT * FROM users WHERE name = 'Alice';
|
|||
|
|
-- Extra: Using where（先走 idx_name_age 拿到 id，再回聚簇索引取全行）
|
|||
|
|
```
|
|||
|
|
|
|||
|
|
## 实践场景
|
|||
|
|
|
|||
|
|
**场景一：选型主键**
|
|||
|
|
- 优先使用自增 BIGINT 或 BIGINT UNSIGNED 作为主键，保持顺序写入减少页分裂
|
|||
|
|
- 绝对避免用 UUID 或随机字符串作为主键——乱序插入会导致频繁的页分裂和碎片
|
|||
|
|
|
|||
|
|
**场景二：联合索引的顺序设计**
|
|||
|
|
- 区分度高的列放前面（如 user_id 优于 status）
|
|||
|
|
- 等值查询列在前，范围查询列在后（范围查询会中断最左前缀匹配）
|
|||
|
|
|
|||
|
|
**场景三：监控页分裂**
|
|||
|
|
```sql
|
|||
|
|
-- 查看表中页的使用情况
|
|||
|
|
SELECT table_name, data_length, index_length
|
|||
|
|
FROM information_schema.tables
|
|||
|
|
WHERE engine = 'InnoDB';
|
|||
|
|
|
|||
|
|
-- 填充率低说明页分裂频繁，考虑 OPTIMIZE TABLE
|
|||
|
|
```
|
|||
|
|
|
|||
|
|
## 扩展阅读
|
|||
|
|
- [[覆盖索引与回表优化]]
|
|||
|
|
- [[Explain 执行计划解读]]
|
|||
|
|
- [[ACID 与 MVCC 机制]]
|