第 04 篇 为什么是 B+ 树：从磁盘 IO 反推数据结构选型

开篇钩子

哈希表 O(1)，红黑树 O(log n)，都比 B+ 树的复杂度公式漂亮。为什么数据库集体选了 B+ 树？因为它们比较的是CPU 指令数，而数据库真正的瓶颈是磁盘 IO 次数。一次随机磁盘 IO 约 10ms，而一次内存访问约 100ns——换算过来：一次磁盘 IO ≈ 10 万次内存访问。把这个换算刻在脑子里，所有数据库索引的设计决策就都有了解释。

1. 磁盘 IO 是真正的瓶颈

内存访问时间：约 100ns（0.0001ms）。磁盘随机 IO：约 10ms（机械硬盘寻道+旋转）。差距：10 万倍。

即便是 SSD，随机 IO 约 0.1ms，与内存访问仍有 1000 倍差距。

这意味着：减少一次磁盘 IO，抵得上在内存里做 10 万次访问（与开篇钩子里的换算是同一个数字）。数据结构的选型标准不是"每次操作的 CPU 指令数最少"，而是"一次查询触发的磁盘 IO 次数最少"。

2. 逐个淘汰其他数据结构

哈希表：等值查询 O(1)，完美。但范围查询（WHERE age BETWEEN 20 AND 30）和排序（ORDER BY age）完全无法支持，因为哈希之后数据无序。数据库索引必须同时支持等值、范围、排序，哈希表直接出局。

有序数组</