14、哈希表在数据库索引中的应用：哈希索引 vs B+树索引、MySQL哈希索引原理、自适应哈希索引

聊到哈希表在数据库里的应用，我第一个想到的就是索引。说实话，很多人一听到「数据库索引」，脑子里蹦出来的就是 B+ 树。这没错，B+ 树确实是主流。但哈希索引在很多场景下，才是真正的性能杀手。

我自己早期做项目时，就踩过一个坑。一张用户登录日志表，每天几百万条写入，查询模式极其简单——就是根据用户 ID 查最新一条记录。我一开始用了默认的 B+ 树索引，结果随着数据量增长，查询越来越慢。后来改成哈希索引，性能直接翻了好几倍。嗯，从那以后我就记住了：选索引类型，一定要看你的查询模式。

哈希索引 vs B+ 树索引

这两种索引，本质上是两种不同的数据结构在数据库里的落地。咱们先看看它们各自的特点。

对比维度 哈希索引 B+ 树索引
底层结构 哈希表（数组+链表/开放寻址） 平衡多路搜索树
查询类型 仅支持等值查询（=、IN） 支持等值、范围、排序、模糊匹配
单条查询速度 O(1)，极快 O(log n)，稳定
范围查询 不支持（需要全表扫描） 天然支持，叶子节点链表有序
排序支持 不支持 支持，索引本身有序
存储空间 较小（仅存哈希值和指针） 较大（存储完整键值和指针）
哈希冲突处理 需要解决（链地址法/再哈希） 无冲突概念

你看这个表格就清楚了。哈希索引的优势在于单点查询，B+ 树的优势在于范围查询和排序。说白了，如果你的业务全是「根据主键查记录」，哈希索引就是最优解。但如果你需要「查某段时间内的所有订单」，那 B+ 树才是正解。

核心结论：哈希索引不是要取代 B+ 树，而是互补。MySQL 的 InnoDB 引擎默认用 B+ 树，但它在内存里偷偷维护了一个「自适应哈希索引」，用来加速热点数据的等值查询。这个后面会细说。

MySQL 哈希索引原理

MySQL 里哈希索引有两种存在形式：一种是 Memory 引擎显式支持的哈希索引，另一种是 InnoDB 引擎自带的「自适应哈希索引」（Adaptive Hash Index，简称 AHI）。

咱们先看 Memory 引擎的哈希索引。它的原理其实很简单：

  1. 对索引列的键值计算哈希值
  2. 用哈希值定位到哈希桶
  3. 在桶内遍历链表，找到匹配的记录

举个例子，假设你有一张表：

CREATE TABLE user_login (
    user_id INT NOT NULL,
    login_time DATETIME,
    ip_address VARCHAR(15),
    INDEX hash_idx USING HASH (user_id)
) ENGINE=MEMORY;

当你执行 SELECT * FROM user_login WHERE user_id = 10086 时，MySQL 会：

  • 计算 10086 的哈希值，比如得到 0x7A3F
  • 定位到哈希桶 #0x7A3F
  • 在桶内的链表里找到 user_id=10086 的记录

整个过程就是 O(1) 的复杂度。但注意，Memory 引擎的哈希索引不支持范围查询。你写 WHERE user_id > 10000，它就傻眼了，只能全表扫描。

避坑指南：我曾经在一个项目中，用 Memory 引擎的哈希索引存了会话数据。一开始跑得飞快，但后来发现一个问题——哈希冲突严重时，链表变得很长，查询性能从 O(1) 退化到了 O(n)。更坑的是，Memory 引擎是表级锁，并发一高就炸了。所以哈希索引虽快，但别滥用。

自适应哈希索引（AHI）

这才是 InnoDB 的杀手锏。InnoDB 默认用 B+ 树，但它会在内存里自动为频繁访问的索引页建立哈希索引。这个过程完全由 InnoDB 内部管理，不需要你手动创建。

它的工作原理是这样的：

  • InnoDB 监控 B+ 树索引的访问模式
  • 如果发现某个索引页被频繁等值查询（比如连续 100 次以上）
  • 就在内存中为该页的键值建立哈希索引
  • 后续查询直接走哈希索引，跳过 B+ 树的树搜索

说白了，就是 InnoDB 帮你「智能加速」。你想想看，一个 B+ 树索引，查一条记录要走 3~4 层树搜索。但如果有了 AHI，直接 O(1) 定位到页，再在页内二分查找，速度能快不少。

个人经验：我调优过一个电商订单系统，QPS 到了 5000 左右时，CPU 的 `btr_search` 占比很高。后来我打开了 AHI 的监控，发现命中率只有 60%。通过调整 `innodb_adaptive_hash_index_parts` 参数（分区数），减少了 AHI 的锁竞争，命中率提升到了 85% 以上，CPU 直接降了 20%。

AHI 的启用和监控也很简单：

-- 查看 AHI 是否开启
SHOW VARIABLES LIKE 'innodb_adaptive_hash_index';

-- 查看 AHI 的使用情况
SHOW ENGINE INNODB STATUS\G
-- 在输出中搜索 "Hash table size" 和 "hash searches/s"

输出里你会看到类似这样的信息：

-------------------------------------
INSERT BUFFER AND ADAPTIVE HASH INDEX
-------------------------------------
Hash table size 34673467, node heap has 1 buffer(s)
0.00 hash searches/s, 0.00 non-hash searches/s

这里的 hash searches/s 就是 AHI 的命中次数。如果这个值很高，说明 AHI 在干活。如果很低，说明你的查询模式不太适合哈希索引。

什么时候该用哈希索引？

我总结了几条经验，供你参考：

  • 等值查询为主：比如根据用户 ID、订单号、设备 ID 查记录
  • 数据量大但查询模式固定：比如日志表、流水表，只查最近一条
  • 不需要排序和范围：如果你需要 ORDER BY 或 BETWEEN，哈希索引帮不上忙
  • 内存充足：哈希索引全在内存里，内存不够就别硬上

反过来，如果你的查询涉及范围、排序、分组、模糊匹配，老老实实用 B+ 树。别想着用哈希索引走捷径，会翻车的。

一句话总结：哈希索引是「快准狠」的单点查询利器，B+ 树是「稳全广」的通用索引方案。MySQL 的 AHI 把两者的优势结合了起来——平时用 B+ 树兜底，热点数据用哈希索引加速。这才是工程上的最优解。

好了，哈希索引在数据库中的应用就聊到这儿。下一节咱们会深入哈希表的内存布局和扩容策略，这些底层细节才是真正拉开性能差距的地方。

公众号:蓝海资料掘金营，微信deep3321

← 上一章 📖 返回目录 下一章 →