B+树索引结构

MySQL InnoDB使用B+树作为索引的存储结构，B+树是一种多路平衡搜索树。

B+树核心特性

结构特点

                    [根节点: 20|50]
                   /       |        \
          [10|15]    [30|40]    [70|80]
          /   \      /    \     /    \
       叶子→叶子→叶子→叶子→叶子→叶子→叶子
                  ↑
             数据指针/数据

与B树的区别

InnoDB中的B+树

节点结构

非叶子节点（索引页）：
┌────────────────────────────────────┐
│ 页头 | 目录槽 | 键值 + 子页指针      │
└────────────────────────────────────┘
每个键值对应一个子页指针

叶子节点（数据页）：
┌────────────────────────────────────┐
│ 页头 | 目录槽 | 记录1 | 记录2 | ...  │
└────────────────────────────────────┘
存储完整记录或主键值

页面大小

-- InnoDB默认页大小16KB
SHOW VARIABLES LIKE 'innodb_page_size';

-- 每页存储记录数
-- 假设主键BIGINT(8字节)+指针(6字节)=14字节
-- 16KB / 14字节 ≈ 1170个键值

-- 三层B+树可存储记录数
-- 1170 × 1170 × 16 ≈ 2000万+条记录

查询效率分析

时间复杂度

B+树高度 h = log_m(N)
m: 阶数（分支因子）
N: 记录总数

InnoDB三层B+树：
- 高度 h = 3
- 可存储千万级记录
- 查询仅需3次磁盘IO

示例计算

假设：
- 页大小 = 16KB
- 主键 = BIGINT(8字节)
- 指针 = 6字节

每页索引项 ≈ 16KB / 14字节 ≈ 1170

三层树容量 = 1170³ × 每页记录数
          ≈ 16亿 × 每页记录数

聚簇索引B+树

聚簇索引（主键索引）：

        [根节点]
       /    \
    [中间节点]
    /    \
[叶子节点] ← 完整数据行

叶子节点存储：完整数据行（按主键排序）

二级索引B+树

二级索引（辅助索引）：

        [根节点]
       /    \
    [中间节点]
    /    \
[叶子节点] ← 主键值

叶子节点存储：索引列值 + 主键值
查询数据需回表：主键值 → 聚簇索引查数据

索引查找过程

-- 主键查询（聚簇索引）
SELECT * FROM users WHERE id = 100;
-- 直接定位叶子节点，获取完整数据

-- 二级索引查询
SELECT * FROM users WHERE name = '张三';
-- 1. 二级索引树找到name='张三'的主键值
-- 2. 回表到聚簇索引查完整数据

范围查询优势

-- B+树叶子节点链表连接，范围查询高效
SELECT * FROM users WHERE id BETWEEN 100 AND 200;

-- 叶子节点顺序访问
[100] → [101] → [102] → ... → [200]

页分裂与合并

页分裂

插入数据导致页满时：
1. 分配新页
2. 移动一半数据到新页
3. 父节点添加新索引项
4. 可能触发级联分裂

页合并

删除数据导致页空间过少时：
1. 检查相邻页
2. 合并到同一页
3. 更新父节点索引

页分裂影响性能，建议使用自增主键减少分裂。

要点总结

• B+树仅叶子节点存储数据，非叶节点只存键值和指针
• 叶子节点通过链表连接，范围查询高效
• 三层B+树可存储千万级记录，查询最多3次IO
• 聚簇索引叶子存完整数据，二级索引叶子存主键值
• 自增主键可减少页分裂，提升写入性能