一般来说，索引本身也很大，不可能全部存储在内存中，因此索引往往以索引文件的形式存储的磁盘上。这样的话，索引查找过程中就要产生磁盘 I/O 消耗，相对于内存存取，I/O 存取的消耗要高几个数量级，所以评价一个数据结构作为索引的优劣最重要的指标就是在查找过程中磁盘 I/O 操作次数的渐进复杂度。换句话说，索引的结构组织要尽量减少查找过程中磁盘 I/O 的存取次数。

“以磁盘 IO 次数为评价标尺”是全文的题眼。顺着这把标尺，可以推导出 B-Tree/B+Tree 的每一个设计选择：为什么是多路而非二叉、为什么节点大小等于页、为什么数据沉到叶子。本文完成这条推导链，并对照被淘汰的候选结构。

标尺：一次磁盘 IO 的代价模型

  • 内存访问 ~100ns，磁盘随机 IO ~10ms（机械）/ ~0.1ms（SSD）——差 3-5 个数量级
  • 磁盘按页/块（InnoDB 16KB）为单位读写：读一个字节与读一页成本几乎相同
  • 推论一：算法复杂度要换算成 IO 次数才有意义；log2(N) 次 IO 的二叉树可能输给 log1000(N) 次 IO 的多路树
  • 推论二：每个节点应占满一页，一次 IO 读入尽可能多的”路”

推导一：多路（m 叉）而非二叉

二叉搜索树树高 log2(N)：千万节点约 24 层 = 24 次 IO。m 路树树高 log_m(N)：m=1000 时千万节点仅 3 层。m 的上限由页容量决定：非叶节点存”键+指针”，16KB 页可装约千级——这就是 B-Tree 阶数的物理来源，不是拍脑袋。

推导二：节点占满页 + 局部性预读

  • B-Tree 节点大小对齐磁盘页，一次 IO 读入整节点；InnoDB 还有预读（读入相邻页）利用顺序局部性
  • 填充率控制（约 15/16）：留空间给插入，减少分裂频率；分裂/合并维持平衡保证树高不退化

推导三：B+Tree 对 B-Tree 的两处改进

  • 非叶不存数据只存键：同页装更多键 → m 更大 → 树更矮（B-Tree 非叶存数据浪费页空间）
  • 叶节点链表串联：范围查询沿叶链顺序扫（顺序 IO），B-Tree 范围查询需中序遍历回溯（随机 IO）

数据库的负载是”等值+范围+排序”混合，B+Tree 三者全优；纯等值点查极端场景哈希更快，但数据库不能只为点查设计。

候选结构淘汰赛

结构 淘汰理由
有序数组 查询快但插入 O(n) 搬运，写不可接受
哈希 O(1) 点查但无范围/排序/前缀能力
二叉搜索树 树高 log2(N)，IO 次数多；且易退化为链
AVL/红黑树 平衡但仍是二叉，树高问题依旧（适合内存结构如 TreeMap）
B-Tree 非叶存数据浪费页、范围查询弱于 B+Tree
跳表 范围友好但指针开销大、页利用率低（内存场景 Redis 选用它是对的）
LSM-Tree 写优化（顺序写 memtable+compaction），读需多层合并——写多读少场景（RocksDB/Cassandra）它赢，读多写少的 OLTP 主索引仍是 B+Tree

最后一行重要：B+Tree 不是唯一答案，而是读多写少+磁盘页模型下的最优；LSM 在写密集场景反超，说明”为什么用 B-Tree”的完整答案是”在什么负载与存储介质下”。

内存数据库的反例佐证

Redis 用跳表（zset）而非 B+Tree：数据在内存，IO 标尺失效，评价标尺换成”实现简单+范围遍历友好+无平衡旋转”——标尺变了，最优解就变。这反过来证明：B-Tree 族的全部设计都是为磁盘 IO 这一个标尺服务的。

为什么用 B-Tree（及 B+Tree）：因为索引的胜负手是磁盘 IO 次数，而多路矮树+页对齐节点+叶链表，是在”页为单位读写”的物理约束下把 IO 次数压到 log_m(N) 且 m 最大的唯一形态。记住标尺，推导自然成立。