title: “为什么数据库索引选择B+树而不是Hash？从磁盘IO特性到范围查询的技术真相” date: “2026-03-07T05:05:02+08:00” description: “为什么数据库索引选择B+树而不是Hash？从磁盘IO特性到范围查询的技术真相” draft: false categories: [“数据库”, “系统设计”] tags: [“B+树”, “Hash索引”, “数据库索引”, “InnoDB”, “PostgreSQL”, “磁盘IO”, “范围查询”]
1972年，Rudolf Bayer和Edward McCreight在波音研究实验室工作时遇到了一个棘手问题：如何高效地组织存储在磁盘上的大量有序数据？他们在当年发表的论文"Organization and Maintenance of Large Ordered Indexes"中提出了B树（B-tree），这个数据结构在此后的半个世纪里统治了数据库索引设计。但有一个疑问始终困扰着许多开发者：Hash表在内存中拥有O(1)的查找效率，为什么数据库偏偏选择了看起来更慢的B+树？
答案藏在磁盘的物理特性里。
磁盘IO才是真正的瓶颈
在讨论索引选择之前，需要先理解一个关键事实：现代计算机体系中，CPU与磁盘之间的速度差距是数量级的。
一次典型的HDD磁盘随机读取需要5-10毫秒，这听起来不算长，但对于CPU来说，这相当于执行了数千万条指令。即使是现代SSD，随机读取延迟也在0.1毫秒左右——仍然是内存访问延迟的100倍以上。
L1缓存访问：约1.2纳秒
L2缓存访问：约4纳秒
L3缓存访问：约13纳秒
主内存访问：约60-100纳秒
SSD随机读取：约0.1毫秒（100,000纳秒）
HDD随机读取：约5-10毫秒（5,000,000-10,000,000纳秒）
这意味着，在磁盘存储场景下，索引设计的首要目标不是减少计算量，而是减少磁盘访问次数。一个数据结构即使计算复杂度是O(n²)，但如果能把磁盘IO从10次降到2次，它在数据库场景下也比O(log n)但需要5次磁盘访问的方案更优。
B+树的高扇出设计
B+树的核心设计理念是"让每个节点尽可能大，刚好填满一个磁盘页"。
InnoDB默认使用16KB的页大小。假设主键是8字节的BIGINT，每个节点指针占用6字节，那么一个非叶子节点可以存储多少个键值对？
非叶子节点存储：主键值(8字节) + 子节点指针(6字节) = 14字节/条目
可用空间：16KB - 页头开销(约120字节) ≈ 16,264字节
扇出 ≈ 16,264 / 14 ≈ 1,161
这意味着每个非叶子节点可以指向超过1000个子节点。Jeremy Cole在他的经典分析中给出了更精确的数据：一个典型的InnoDB B+树非叶子节点可以存储约1203个指针，叶子节点可以存储约468条记录（取决于行大小）。
这种高扇出设计带来了惊人的效果：
| 树高度 | 最大记录数 |
|---|---|
| 1层 | 468 |
| 2层 | 563,004 |
| 3层 | 676,987,812 |
| 4层 | 813,650,400,036 |
一张存储6亿条记录的表，B+树高度仅为3层。换句话说，任何一条记录的查找最多只需要3次磁盘IO。而且，由于B+树的根节点几乎永远驻留在内存中（它太小了，只有16KB），实际查询往往只需要1-2次磁盘IO。
范围查询：Hash表的致命短板
假设你要执行一个简单的范围查询：
SELECT * FROM orders WHERE order_date BETWEEN '2024-01-01' AND '2024-01-31';
如果使用Hash索引，数据库需要做什么？Hash函数将每个键映射到一个"随机"的位置，2024-01-01和2024-01-02在Hash表中可能相距甚远。要找到这个区间内的所有记录，数据库别无选择，只能扫描整个索引——O(n)的操作。
B+树则完全不同。它的叶子节点通过双向链表连接，天然有序。找到起始键2024-01-01后，只需要沿着链表向后遍历，直到遇到第一个大于2024-01-31的键为止。这个过程的时间复杂度是O(log n + k)，其中k是结果集大小。
MySQL官方文档对B+树索引支持的查询类型有明确说明：
支持的运算符：=, >, >=, <, <=, BETWEEN, LIKE 'prefix%'
不支持的：LIKE '%suffix', 函数运算
而Hash索引只能处理等值比较：
支持的运算符：=, <=>
不支持：<, >, <=, >=, BETWEEN, ORDER BY, LIKE
这不仅仅是功能限制，更是Hash数据结构的本质特性：它"忘记"了键之间的顺序关系。
PostgreSQL的Hash索引之痛
PostgreSQL对Hash索引的态度经历了一个戏剧性的转变。在PostgreSQL 10之前，官方文档中赫然写着这样的警告：
Hash索引操作目前没有WAL日志记录，因此数据库崩溃后可能需要重建Hash索引。此外，在复制环境中Hash索引无法正确工作。出于这些原因，不建议在生产环境中使用Hash索引。
这个问题困扰了PostgreSQL社区多年。直到2017年10月发布的PostgreSQL 10，Hash索引才获得了完整的WAL支持，变得崩溃安全且可复制。
PostgreSQL核心开发者Robert Haas在博客中写道：在此之前，Hash索引在并发环境下表现不佳，缺乏WAL日志导致崩溃后数据不一致，这些问题"可能很微妙"，用户往往在出问题后才发现。
为什么修复这个问题花了这么长时间？因为Hash索引的并发控制比B+树复杂得多。B+树的分裂操作有明确的锁顺序，可以避免死锁；而Hash表的桶分裂可能涉及多个桶的重哈希，并发控制极其复杂。
Hash的"理论优势"为何无法兑现
理论上，Hash索引在等值查询上应该更快：O(1) vs O(log n)。但现实中，这个优势很难体现。
首先，O(log n)中的n在这里是树的高度，而不是数据量。对于一张6亿行的表，B+树高度只有3，log₃(6亿) ≈ 3次比较。这和O(1)的差距微乎其微。
其次，Hash索引有自己的性能陷阱。当发生Hash碰撞时，多个键会被映射到同一个桶中，需要线性查找。虽然好的Hash函数可以降低碰撞概率，但无法完全消除。在最坏情况下——所有键都碰撞到同一个桶——Hash查找退化为O(n)。
更重要的是，Hash索引无法利用数据的局部性。B+树的叶子节点在磁盘上是物理连续的，一次IO可以读取多条相关记录。而Hash表中的记录位置取决于Hash函数的输出，完全随机，每次查找都可能触发一次独立的磁盘IO。
InnoDB的折中：Adaptive Hash Index
MySQL的InnoDB引擎采用了一个巧妙的折中方案：默认使用B+树索引，但在内存中构建一个自适应Hash索引（Adaptive Hash Index，AHI）。
AHI的工作原理很简单：InnoDB观察哪些索引页被频繁访问，如果某个页的访问模式呈现明显的热点特征，它会在内存中为这个页构建一个Hash索引，将键直接映射到内存中的页位置。
B+树查找路径：根节点 → 中间节点 → 叶子节点 → 数据
AHI查找路径：Hash表 → 直接定位到内存中的页
PlanetScale的技术团队做过测试：对于一张3.9亿行的表，开启AHI后，重复查询的QPS提升了约16%。这不是一个惊天动地的数字，但考虑到B+树本身已经非常快，这个提升仍然有价值。
需要注意的是，AHI只对内存中的数据有效。如果Buffer Pool太小，频繁发生页面淘汰，AHI的收益会被抵消甚至变成负收益。MySQL 8.4版本（2024年4月发布）开始，AHI默认被禁用，原因正是它在某些场景下可能引入不必要的开销。
什么时候Hash索引值得考虑
说了这么多B+树的优势，Hash索引就没有用武之地了吗？也不是。
MySQL的MEMORY存储引擎默认使用Hash索引，适用于以下场景：
- 数据完全在内存中，磁盘IO不再是瓶颈
- 查询模式几乎全部是等值查找
- 不需要范围查询、排序或分组
一个典型案例是会话存储（Session Store）。每个会话ID通过Hash直接定位，不需要遍历，也不需要范围查询。这种场景下，Hash索引的O(1)查找确实能带来优势。
PostgreSQL在修复Hash索引的问题后，EDB的测试显示Hash索引在某些等值查询场景下比B+树快10%-22%。但社区的建议仍然是：除非你完全理解Hash索引的特性，否则默认选择B+树。
索引选择的本质是权衡
B+树成为数据库索引的默认选择，不是因为它是完美的，而是因为它在各种场景下都能提供"足够好"的性能。
| 维度 | B+树 | Hash |
|---|---|---|
| 等值查询 | O(log n) | O(1) |
| 范围查询 | O(log n + k) | 不支持 |
| 排序 | 支持 | 不支持 |
| 磁盘IO | 可预测，少 | 可能较多 |
| 空间效率 | 高 | 取决于负载因子 |
| 并发控制 | 成熟 | 较复杂 |
B+树像一个瑞士军刀：也许不是最快的，但几乎什么都能做。Hash索引像一把手术刀：在特定场景下更快更精准，但用错地方会搞砸一切。
当你在CREATE INDEX时省略索引类型，数据库默认创建B+树索引，这个设计决策背后是半个世纪的工程智慧。它提醒我们：在系统设计中，通用性往往比极端优化更有价值。
参考资料
- Bayer, R., & McCreight, E. (1972). Organization and Maintenance of Large Ordered Indexes. Acta Informatica, 1(3), 173-189.
- Comer, D. (1979). The Ubiquitous B-Tree. ACM Computing Surveys, 11(2), 121-137.
- MySQL Reference Manual - Comparison of B-Tree and Hash Indexes
- PostgreSQL Documentation - Index Types
- Jeremy Cole - B+Tree Index Structures in InnoDB
- Robert Haas - PostgreSQL’s Hash Indexes Are Now Cool
- PlanetScale - The MySQL Adaptive Hash Index
- Percona - Is Adaptive Hash Index in InnoDB right for my workload?