MySQL 索引为什么最终选了 B+Tree

面试被问过一个老问题：MySQL 索引为什么用 B+Tree，不用 Hash 表？

当时含糊 answer 了几句，回来仔细扒了扒，发现这里面的门道比想象中多。

今天我们就把 Hash 索引和 B+Tree 挨个拆开看看，搞清楚它们各自的结构、优缺点，以及 MySQL 为什么最终把 B+Tree 定成默认选项。

先说 Hash 索引：等值查询快到飞起

Hash 索引的原理很直接：对索引列的值算一个哈希值，哈希值和数据的存储位置对应起来，存进一个哈希表里。

查询的时候，同样对查询条件算一次哈希，直接定位到对应的桶（bucket），一步到位。

打个比方，Hash 索引像是小区的门牌号直接对应一个门禁密码，你知道密码，直接开门，不用一层一层找。

这个结构在 MySQL 里主要体现在 Memory 引擎的默认索引类型上：

-- Memory引擎默认就是Hash索引
CREATE TABLE tmp_session (
    session_id VARCHAR(64) PRIMARY KEY,
    user_id INT
) ENGINE=MEMORY;
​

InnoDB 本身不支持我们手动创建 Hash 索引，但它有个叫**自适应哈希索引（Adaptive Hash Index，AHI）**的内部机制，会在检测到某些索引值被频繁等值查询时，自动在内存里建一份 Hash 索引加速，这个过程完全自动，用户感知不到，也控制不了。

Hash 索引的优点

• 等值查询极快：时间复杂度 O(1)，只要哈希不冲突，一步到位，比树形结构逐层查找快得多。
• 结构简单：实现起来比树形结构简单，占用空间也可能更小。

Hash 索引的缺点

这才是重点，也是为什么 MySQL 不拿它当默认索引的原因：

• 不支持范围查询：哈希值和原始值的大小关系是打乱的，WHERE age > 20 这种范围查询，Hash 索引完全没法用，只能全表扫描。
• 不支持排序：ORDER BY 需要数据本身有序，Hash 索引里的数据是按哈希值分布的，跟原始值大小毫无关系。
• 不支持联合索引的部分匹配：多列联合索引场景下，Hash 索引要求把所有列的值拼起来一起算哈希，只传第一列是查不出来的（这点跟 B+Tree 的最左前缀原则不一样）。
• 哈希冲突问题：不同的值算出同一个哈希，就得在同一个桶里遍历比较，数据量大、冲突多的时候性能会打折扣。

所以 Hash 索引的适用场景其实很窄：只有等值查询、没有范围查询和排序需求的场景才适合，比如一些 KV 缓存表。

这也是为什么很多同学说“新版 MySQL 好像不用 Hash 索引了”——不是被弃用，而是它的应用场景本来就被 B+Tree 全面压制了，只在 Memory 引擎和 InnoDB 内部优化里还能看到它的身影。

主角登场：B+Tree

B+Tree 是 B-Tree（B 树）的一个变种，专门为磁盘存储和范围查询做了优化。

B+Tree 的结构长什么样

用文字画一下它的层级结构（简化版，实际 InnoDB 的 B+Tree 通常只有 3~4 层就能存千万级数据）：

                    [ 根节点：索引层 ]
                    |   50   |   90   |
                   /        |         \
         [索引层]        [索引层]        [索引层]
         |20|35|          |60|75|          |95|99|
        /  |  \          /  |  \          /  |  \
     [叶子][叶子][叶子] [叶子][叶子][叶子] [叶子][叶子][叶子]
      10-19 20-34 35-49  50-59 60-74 75-89  90-94 95-98 99+
       ↕     ↕     ↕      ↕     ↕     ↕      ↕     ↕    ↕
     （叶子节点之间用双向指针串成一条链表）
​

关键特征就这么几条：

• 只有叶子节点存真实数据，非叶子节点（索引层）只存索引键值，用来指引查找方向，不存数据本身，这样非叶子节点能塞下更多键值，让树更“矮胖”，减少磁盘 IO 次数。
• 叶子节点之间用双向链表连起来，这一条是 B+Tree 比 B 树多出来的关键设计，范围查询的时候，找到起点后直接顺着链表往后扫，不用每次都从根节点重新查。
• 所有数据都在叶子节点，且按顺序排列，天然支持范围查询和排序，ORDER BY、BETWEEN、>、< 都能用上索引。

我们平时说 InnoDB 的主键索引是“聚簇索引”，指的就是：叶子节点直接存的是整行数据，而不是数据的地址；普通索引（二级索引）的叶子节点存的是主键值，查到以后还要“回表”再去主键索引找一次完整数据。

为什么不用 B 树（不带 + 号的那种）

B 树的每个节点（包括非叶子节点）都存数据，这就意味着：

• 非叶子节点因为要存数据，能塞的键值数量变少，树会更“瘦高”，查询时磁盘 IO 次数变多。
• 范围查询做不到简单的链表顺序遍历，得不断在树里跳来跳去。

所以 B+Tree 去掉了非叶子节点的数据存储，专门给索引键值腾地方，换来更矮的树高和更快的范围查询。

B+Tree 的优点

• 范围查询和排序效率高：叶子节点链表天然有序，BETWEEN、ORDER BY、GROUP BY 都能高效利用索引。
• 树高可控、IO 次数少：非叶子节点不存数据，能容纳的键值多，三四层就能覆盖千万级数据量，每次查询的磁盘 IO 次数是可预期的。
• 支持最左前缀匹配：联合索引 (a, b, c) 上，查 WHERE a=1、WHERE a=1 AND b=2 都能用上索引，不要求把所有列都传全。
• 等值查询也不差：虽然不如 Hash 的 O(1)，但 O(log n)已经足够快，千万级数据也就三四次比较。

B+Tree 的缺点

• 等值查询理论上比 Hash 慢：毕竟要逐层比较，不是一步到位。不过实际差距在毫秒级以下，业务上基本感知不到。
• 索引维护成本更高：插入删除数据可能触发节点分裂或合并，重新平衡树结构，写入性能相对会打点折扣。
• 索引本身占用空间：非叶子节点也要占存储空间，虽然不存数据，但键值本身也是开销。

两者放一起对比一下

说了这么多，简单列个对照表帮我们记忆（口头总结，不是正经表格，方便脑子里过一遍）：

• 等值查询：Hash 完胜（O(1) vs O(log n)），但差距在实际业务里几乎感知不到。
• 范围查询/排序：B+Tree 完胜，Hash 基本用不了。
• 联合索引部分匹配：B+Tree 支持最左前缀，Hash 不支持。
• 写入维护成本：Hash 相对简单，B+Tree 要考虑节点分裂合并。
• 适用场景：Hash 适合纯 KV 等值查找（如内存表、缓存），B+Tree 适合通用 OLTP 查询场景。

所以 MySQL（InnoDB）默认选 B+Tree，本质上是抓大放小：牺牲一点点理论上的等值查询速度，换来对范围查询、排序、联合索引最左前缀的全面支持，这些能力覆盖了绝大多数实际业务场景。

如果你的场景真的只有纯等值查询、没有范围和排序需求，Memory 引擎的 Hash 索引依然是可以考虑的选项，只是这类场景在真实业务里确实不算多。

小结

面试官问这个问题，其实考的不是“哪个更好”，而是“你是否理解不同数据结构解决不同问题的取舍”。

Hash 索引在纯等值查询上是降维打击，但它的短板（不支持范围查询、排序、最左前缀）刚好是业务里最常见的需求。

B+Tree 通过叶子节点链表和分层索引的设计，在等值查询稍作妥协的前提下，把范围查询、排序、联合索引这些通用需求都覆盖到了，这才是它能成为默认选项的真正原因。

PS：不知道为什么，很多文章讲 B+Tree 只讲结构不讲为什么，看完感觉知道了个寂寞。希望这次画的这个图能让你对着它在脑子里过一遍查找过程，理解会深一些。

那 B+Tree 和 Hash 索引就先讲到这里，感兴趣的话可以自己用 EXPLAIN 看看 SQL 到底走了哪种索引。