B+Tree 深度解析
这是后端工程师最需要深入理解的数据结构——没有之一。InnoDB 的索引组织、查询性能、磁盘 I/O 模型全都建立在一棵 B+Tree 上。
为什么是 B+Tree 而不是 BST/红黑树？
答案关键词：磁盘 I/O。
数据库索引是存在磁盘上的，数据量远超内存容量。一次磁盘寻道约 5-10ms，一次内存访问约 100ns——差距是 5 万到 10 万倍。对于数据库来说，”算法复杂度 O(log n)”不是用 CPU 执行步数衡量的，而是用磁盘 I/O 次数衡量的。
B+Tree 的核心设计目标：矮胖——让树的高度尽可能低，从而减少磁盘 I/O 次数。
1 | B+Tree 结构 (InnoDB 典型: m=3 阶, 实际可达 1000+ 阶): |
B+Tree 选择矩形而非三角的原因 —— 扇出 (Fanout)：
每个 InnoDB Page 是 16KB。假设主键为 8 bytes 的 BIGINT，指针为 6 bytes（页号），一个索引记录 14 bytes。一个 16KB 的 Page 可以存约 1170 个索引项（实际受 Page Header 等开销影响，约 1000 个）。
这就是扇出 (fanout) ≈ 1000——每个非叶子节点可以指向约 1000 个子节点。
- 高度 h=1（只有根和叶子）：可容纳约 1,000 条记录
- 高度 h=2：可容纳约 1,000 × 1,000 = 1,000,000 条记录
- 高度 h=3：可容纳约 1,000³ = 1,000,000,000 条记录
一行数据 1KB 时，叶子节点每个 Page 存 16 条记录。3 层 B+Tree 可以支撑 (1000² × 16) ≈ 1600万行——查一条数据最多只需要 3 次磁盘 I/O。如果要存几十亿行，树高最多 4 层。
作为对比：如果是一棵二叉树（BST/红黑树），即使完全平衡，1 亿行数据约 2^27 需要约 27 层——也就是最多 27 次磁盘 I/O，比 B+Tree 的 3-4 次差了近 10 倍。
这就是 InnoDB 选 B+Tree 最根本的原因——极致的磁盘 I/O 优化。
B-Tree vs B+Tree 的关键区别
| 特性 | B-Tree | B+Tree (InnoDB 实际使用) |
|---|---|---|
| 数据存储位置 | 所有节点都存数据 | 仅叶子节点存数据 |
| 非叶子节点 | 索引 + 数据 | 仅索引（占空间极小） |
| 叶子节点之间 | 没有链接 | 双向链表串联 |
| 范围查询 | 需要回溯（中序遍历） | 叶子链表顺序扫描即可 O(k) |
| 扇出 | 较小（因为存数据） | 极大（因为只存索引） |
B+Tree 把数据集中在叶子节点，非叶子节点只存键值 + 指针，同样的 16KB Page 能放下更多索引项 → 更高的扇出 → 更矮的树 → 更少的 I/O。
聚簇索引 (Clustered Index) 组织
InnoDB 的主键索引就是聚簇索引——数据行直接存储在 B+Tree 的叶子节点上，而非叶子的 Value 就是一个 Page 指针。这与 MyISAM 的”数据文件独立、索引存数据地址”完全不同：
1 | InnoDB 聚簇索引: MyISAM 非聚簇索引: |
聚簇索引的优势：主键查询一次 B+Tree 就能拿到完整行数据。劣势：二级索引的叶子节点存的是主键值（而不是数据地址），所以通过二级索引查询需要回表——先查二级索引拿到主键，再查聚簇索引拿到行数据。这就是为什么建议用覆盖索引避免回表。
InnoDB 索引的详细分析（包括页内结构、联合索引、索引优化策略）参见 MySQL 深度解析。