**一、B+ 树的基本结构**
B+ 树是一种多路平衡查找树，特点是：
- **所有数据都存储在叶子节点**：非叶子节点仅存储索引（键值），不存储数据行。
- **叶子节点之间用指针相连**：形成有序链表，支持范围查询。
- **高度平衡**：所有叶子节点到根节点的路径长度相同。
*（注：实际 B+ 树每个节点可包含数百个键值，非上图中的简单示例）*
**二、MySQL 如何使用 B+ 树**
**1. 聚集索引（Clustered Index）**
- **定义**：表的主键索引称为聚集索引，叶子节点直接存储整行数据。
- **示例**：
对于表 `users(id INT PRIMARY KEY, name VARCHAR(20))`，其聚集索引结构为：
```
根节点: [10, 20, 30] → 指向子节点
叶子节点1: [1, 'Alice'], [2, 'Bob'], ..., [10, 'John']
叶子节点2: [11, 'Mike'], [12, 'Sarah'], ..., [20, 'Tom']
...
```
- **特点**：
- 数据行按主键顺序物理存储。
- 一个表只能有一个聚集索引（主键）。
- 查询主键时直接定位到数据行，效率极高（通常 1-3 次磁盘 I/O）。
**2. 辅助索引（Secondary Index）**
- **定义**：非主键索引称为辅助索引，叶子节点存储主键值而非整行数据。
- **示例**：
若在 `name` 列创建索引，则辅助索引结构为：
```
根节点: ['Alice', 'John', 'Mike'] → 指向子节点
叶子节点1: ['Alice', 1], ['Bob', 2], ..., ['John', 10]
叶子节点2: ['Mike', 11], ['Sarah', 12], ..., ['Tom', 20]
```
- **查询流程**：
```sql
SELECT * FROM users WHERE name = 'Mike';
```
1. 通过辅助索引找到 `name='Mike'` 对应的主键值 `11`。
2. 通过主键值在聚集索引中查找完整数据行（**回表**操作）。
**3. 索引优化**
- **覆盖索引**：查询的字段全部包含在索引中，无需回表。
```sql
-- name 索引包含 name 和主键 id，无需回表
SELECT name, id FROM users WHERE name LIKE 'A%';
```
- **复合索引**：多列联合索引，遵循“最左前缀匹配”原则。
```sql
CREATE INDEX idx_name_age ON users(name, age);
-- 支持 WHERE name=? 和 WHERE name=? AND age=?，但不支持 WHERE age=?
```
**三、为什么选择 B+ 树？**
**1. 磁盘 I/O 优化**
- **节点大小适配磁盘页**：每个节点大小通常为 16KB（与 MySQL 页大小一致），一次 I/O 读取一个节点。
- **减少 I/O 次数**：B+ 树高度通常为 2-4 层，百万级数据仅需 2-4 次 I/O。
**2. 范围查询高效**
- 叶子节点的链表结构支持顺序遍历，适合 `WHERE age BETWEEN 20 AND 30` 这类查询。
**3. 插入/删除稳定**
- B+ 树的平衡特性保证插入、删除操作的时间复杂度为 O(log n)。
**四、与其他结构的对比**
| 数据结构 | 适用场景 | 缺点 |
|----------|------------------------|--------------------------|
| B+ 树 | 磁盘存储、范围查询 | 不适合频繁随机插入 |
| 哈希表 | 等值查询（如 Redis） | 不支持范围查询 |
| LSM 树 | 写密集场景（如 RocksDB）| 读放大问题 |
**五、实际存储细节**
**1. 页（Page）**
- MySQL 存储的最小单位，默认 16KB。
- 一个页包含多个行数据，页之间通过指针相连。
**2. 索引组织表（Index-Organized Table）**
- InnoDB 存储引擎的表数据按主键索引（聚集索引）的顺序存储，因此主键选择很重要。
**3. 溢出页（Overflow Page）**
- 对于大字段（如 `TEXT`、`BLOB`），部分数据会存储在溢出页中，主页仅存储指针。
**六、总结**
MySQL 基于 B+ 树构建索引和存储数据，核心优势在于：
1. **高效的磁盘 I/O**：通过节点大小与磁盘页匹配，减少读取次数。
2. **范围查询支持**：叶子节点链表结构加速范围扫描。
3. **数据有序性**：按主键物理排序，适合排序和分页。
理解 B+ 树的原理有助于优化索引设计（如避免回表、利用覆盖索引）和查询性能。