文件系统的元数据通常基于 B 树或 B+ 树组织；而在[14丨存储与数据库：RAID]中，我们讨论了磁盘阵列如何提供可靠的物理存储基础。然而，有了可靠的磁盘只是第一步——如何在外存上高效地组织和检索数据，才是存储系统真正的核心难题。
内存数据结构（哈希表、红黑树、跳表等）的访问以纳秒计，而磁盘访问以毫秒计，两者相差约 10^6 倍。这意味着一个设计精良的内存算法在磁盘上可能完全不可用。B+ 树正是为外存而生的数据结构：它通过降低树高和顺序化访问，将磁盘 I/O 次数从 O(N) 压缩到 O(log_f N)（f 为扇出），是关系型数据库和文件系统的索引基石。
本节的核心问题是：为什么 B+ 树是外存数据结构的最优选择？它与内存数据结构有何本质区别？
理解 B+ 树之前，必须先理解外存与内存访问模型的根本差异：
| 维度 | 内存 | 磁盘（HDD） | 磁盘（SSD） |
|---|---|---|---|
| 访问单位 | 字节（Byte） | 扇区（512B/4KB） | 页（4KB~16KB） |
| 随机读延迟 | ~100ns | ~10ms | ~100μs |
| 顺序读吞吐 | ~10GB/s | ~200MB/s | ~3GB/s |
| 随机/顺序比 | ~1:1 | ~1:1000 | ~1:10 |
| 访问模式 | 任意地址 O(1) | 必须整页读入 | 必须整页读入 |
核心洞察：磁盘以"页"为最小访问单位，且顺序访问远快于随机访问。因此，外存数据结构的设计目标是：
一棵 m 阶 B+ 树满足以下性质：
关键参数计算（以 MySQL InnoDB 为例）：
树高与记录数的关系：
| 树高 | 最大记录数 | I/O 次数 |
|---|---|---|
| 2 | 1170 × 16 ≈ 18,720 | 2 |
| 3 | 1170 × 1170 × 16 ≈ 21,902,400 | 3 |
| 4 | 1170^3 × 16 ≈ 25.6 亿 | 4 |
这意味着：一张 2000 万行的表，通过主键索引查找仅需 3 次磁盘 I/O。这就是 B+ 树的威力。
范围查询的关键优势：一旦定位到起始叶节点，后续访问沿链表顺序进行，每次 I/O 读取整个叶节点页，最大化了页内数据的利用率。
插入操作可能触发节点分裂：
删除操作可能触发节点合并或 redistribute（重分布），是插入的逆过程。实践中为避免频繁合并，许多实现采用延迟合并策略——节点低于半满时不立即合并，仅标记为 underflow，在后续操作中再处理。
| 维度 | B+ 树 | B 树 | 哈希表 | LSM-Tree |
|---|---|---|---|---|
| 点查询 | O(log_f N) | O(log_f N) | O(1) | O(1)~O(log N) |
| 范围查询 | O(log_f N + K) | O(log_f N + K) | 不支持 | O(K) |
| 插入 | O(log_f N) | O(log_f N) | O(1) | O(1) |
| 空间利用率 | ≥ 50% | ≥ 50% | 不定 | 写放大 |
| 顺序访问 | 优秀（链表） | 较差（需中序遍历） | 不支持 | 需 Compaction |
| 数据位置 | 仅叶节点 | 所有节点 | — | 多层组件 |
B+ 树相对 B 树的优势：
阶数 m 的选择直接影响扇出和树高：
最优选择：令节点大小等于磁盘/SSD 的页大小（或其整数倍），使一次 I/O 恰好读入一个节点。这也是 InnoDB 默认页大小为 16KB 的依据。
权衡：聚簇索引对主键范围查询最优，但插入顺序若非主键序将导致频繁页分裂。InnoDB 的自增主键策略正是为了避免这一问题。
填充因子控制叶节点预留空闲空间的比例：
权衡：读密集场景用高填充因子；写密集场景用低填充因子。InnoDB 默认填充因子约 15/16（即 6.25% 空闲），兼顾两者。
| 维度 | B+ 树 | LSM-Tree |
|---|---|---|
| 写模式 | 就地更新（Read-Modify-Write） | 追加写入（Append-Only） |
| 写性能 | 随机写，受页分裂影响 | 顺序写，极高吞吐 |
| 读性能 | O(log_f N)，稳定 | 需查多层 + 布隆过滤器，不稳定 |
| 空间放大 | 页分裂碎片 | 过期版本 + 层级冗余 |
| 写放大 | 页分裂（1~2 次 I/O） | Compaction（多次重写） |
| 适用场景 | 读多写少（OLTP） | 写多读少（时序、日志） |
许式伟在[37丨键值存储与数据库]中强调"存储即数据结构"——B+ 树和 LSM-Tree 的选择，本质上是对读优化 vs 写优化这一根本权衡的回应。
InnoDB 是 B+ 树在工业界的标杆实现，其关键设计：
现代文件系统（如 Btrfs、ReiserFS、NTFS）广泛使用 B+ 树管理元数据：
大部分现代文件系统基于 B 树或 B+ 树组织元数据，这一设计思路一脉相承。
UUID 作为主键导致：
正确做法：使用自增整数作为主键，确保插入始终在 B+ 树最右端，避免页分裂。UUID 可作为业务唯一标识存储为普通列。
在低选择性列（如性别、状态枚举）上建索引：
正确做法：索引应建在高选择性列上（选择性 = 不同值数 / 总行数，应接近 1）。低选择性列适合与高选择性列组合为复合索引。
每增加一个二级索引：
正确做法：根据实际查询模式建立索引，定期审计并删除未使用索引。
延伸阅读：下一节[16丨存储与数据库：SQL]将从索引结构上升到查询语言层面，讨论 SQL 如何基于关系模型对 B+ 树索引进行声明式查询，以及查询优化器如何选择最优的索引访问路径。