跳到主要内容

哈希索引

问题​

什么是哈希索引？它和 B+ 树索引有什么区别？什么时候用哈希索引更好？

答案​

哈希索引的原理​

哈希索引通过 哈希函数 将索引键映射到哈希表中的桶（Bucket），实现 O(1)O(1) 的定点查找。

工作流程：

  1. 对索引列的值计算哈希值
  2. 用哈希值定位到对应的桶
  3. 桶中存储指向实际数据行的指针
  4. 如果有哈希冲突，通过链表/开放寻址解决

哈希索引 vs B+ 树索引​

对比项哈希索引B+ 树索引
等值查询O(1)O(1) 极快O(log⁡n)O(\log n) 快
范围查询❌ 不支持✅ 叶子链表扫描
排序❌ 不支持✅ 有序遍历
部分匹配❌ 不支持✅ 最左前缀
LIKE 'abc%'❌ 不支持✅ 前缀匹配
ORDER BY❌ 不能利用✅ 可以利用
GROUP BY❌ 不能利用✅ 可以利用
哈希冲突退化为 O(n)O(n)无此问题
IS NULL❌ 不支持✅ 支持
哈希索引的致命限制

哈希索引 只能用于等值查询（=、IN、<=>）。以下场景全部无法使用：

  • WHERE age > 20（范围查询）
  • WHERE name LIKE 'A%'（前缀匹配）
  • ORDER BY created_at（排序）
  • 联合索引的部分列查询

这就是为什么大多数数据库默认使用 B+ 树而不是哈希索引。

MySQL 中的哈希索引​

Memory 引擎​

MySQL 的 Memory（HEAP）引擎支持显式创建哈希索引：

-- Memory 引擎支持 HASH 索引
CREATE TABLE lookup (
    id INT NOT NULL,
    code VARCHAR(20),
    INDEX USING HASH (code)
) ENGINE = MEMORY;

-- Memory 引擎也支持 BTREE 索引
CREATE TABLE lookup2 (
    id INT NOT NULL,
    code VARCHAR(20),
    INDEX USING BTREE (code)
) ENGINE = MEMORY;
Memory 引擎的局限
  • 数据存在内存中，MySQL 重启后数据丢失
  • 不支持 BLOB/TEXT 列
  • 使用固定长度行格式（VARCHAR 按 CHAR 存储）
  • 生产环境中很少使用

InnoDB 自适应哈希索引（AHI）​

InnoDB 不支持手动创建哈希索引，但有一个自动优化机制 —— 自适应哈希索引（Adaptive Hash Index, AHI）。

AHI 的工作原理：

  1. InnoDB 监控 B+ 树索引页的访问模式
  2. 当某个索引页被频繁等值查找时，自动为其建立哈希索引
  3. 哈希索引从 B+ 树的索引键值映射到数据页
  4. 后续等值查找直接命中哈希，跳过 B+ 树遍历

AHI 的配置：

-- 查看 AHI 状态
SHOW ENGINE INNODB STATUS;
-- 在 INSERT BUFFER AND ADAPTIVE HASH INDEX 部分查看

SHOW VARIABLES LIKE 'innodb_adaptive_hash_index';
-- ON（默认开启）

-- 关闭 AHI（高并发竞争时可能有益）
SET GLOBAL innodb_adaptive_hash_index = OFF;

什么时候考虑关闭 AHI：

  • 高并发写入场景（AHI 维护有锁竞争）
  • 大量范围查询（AHI 对范围查询无效，白占内存）
  • 通过 SHOW ENGINE INNODB STATUS 看到 AHI 命中率低

PostgreSQL 中的哈希索引​

PostgreSQL 原生支持哈希索引：

-- 创建哈希索引
CREATE INDEX idx_email_hash ON users USING HASH (email);

PostgreSQL 哈希索引的演进：

  • < 10.0：不写 WAL，崩溃恢复后不可用，主从复制不支持 → 几乎没人用
  • ≥ 10.0：支持 WAL、支持复制，可以在生产环境使用
  • 在单列等值查询上，哈希索引比 B-tree 略快，且占用空间更小

Redis 中的哈希​

Redis 的底层数据结构中，Hash 类型 在数据量小时用 ziplist，数据量大时用 hashtable（dict）。本质上就是哈希索引。Redis 是纯内存数据库，没有磁盘 IO 的考量，哈希表非常适合。

详见 Redis 数据结构。

一致性哈希​

在分布式数据库的分片场景中，一致性哈希 用于数据路由，解决节点增减时大量数据迁移的问题。

常见面试问题​

Q1: 哈希索引为什么不能做范围查询？​

答案：

哈希函数将键值映射为哈希值，这个映射不保留原始键值的顺序关系。例如：

  • hash('Alice') = 3
  • hash('Bob') = 7
  • hash('Charlie') = 1

键值 Alice < Bob < Charlie 的顺序性在哈希后完全丢失。所以无法通过哈希值找到 "age 在 20 到 30 之间" 的所有记录，只能全表扫描。

B+ 树叶子节点按键值有序排列且通过链表相连，天然支持范围查询。

Q2: 什么是自适应哈希索引？什么时候应该关闭？​

答案：

AHI 是 InnoDB 自动维护的内存中的哈希索引，对频繁等值查找的热点数据建立哈希映射，将 B+ 树的 O(log⁡n)O(\log n) 优化为 O(1)O(1)。

应该关闭的场景：

  1. 读写比低：大量写入，AHI 维护成本 > 收益
  2. 高并发竞争：AHI 使用分区锁（8 个分区），高并发时可能成为瓶颈
  3. 命中率低：通过 SHOW ENGINE INNODB STATUS 查看，如果 AHI 命中率 < 50%，考虑关闭
  4. 大量范围查询：AHI 只对等值查询有效

Q3: 哈希冲突怎么处理？对索引性能有什么影响？​

答案：

常用的解决方法：

  1. 链地址法（Chaining）：冲突的元素放在同一个桶的链表中
  2. 开放寻址法：冲突时探测下一个空闲槽位

对性能的影响：

  • 少量冲突：性能仍为 O(1)O(1)
  • 大量冲突：退化为 O(n)O(n) 链表遍历
  • 极端情况下（所有值映射到同一个桶），等同于全表扫描

Q4: 在什么场景下哈希索引比 B+ 树索引好？​

答案：

  1. 纯等值查找场景：如缓存键查找、会话 ID 查找
  2. 键值存储：如 Redis、Memcached
  3. 哈希连接（Hash Join）：MySQL 8.0+ 的 Hash Join 在等值连接时使用哈希表
  4. 内存数据库：无需考虑磁盘 IO 的场景

实际上大多数 OLTP 场景都需要范围查询和排序，所以 B+ 树是更通用的选择。

相关链接​