MySQL 自适应哈希索引（Adaptive Hash Index）

如果你在使用 MySQL，可能已经接触到基于 B-树 构建的索引。B-树是一种强大的数据结构，被频繁用于关系型数据库中的索引。如果你使用的是 InnoDB 存储引擎，它是索引的唯一选择（除了空间索引）。然而，MySQL 还有一个秘密武器，可以让这些类型的索引查找速度更快：**自适应哈希索引（Adaptive Hash Index, AHI）**。在深入了解它的工作原理之前，先来回顾一下 B-树、InnoDB 缓冲池以及它们如何在索引查找中协同工作。

B-树索引

B-树数据结构已经被应用于计算机系统数十年，在文件系统和数据存储应用的上下文中尤其有用，因为每个节点可以存储多个值。这在与存储系统交互的算法中非常实用，因为可以根据存储单元（例如硬盘的页面大小）设置节点的大小，从而优化存储效率。
顾名思义，B-树是一种特殊类型的树结构，但它在以下方面与普通树不同：

每个节点最多可存储 N 个值，而非一个；
每个节点最多可拥有 N+1 个子节点；
所有元素按从左到右的顺序存储；
所有叶节点位于树的同一级别。

以下是基于数据库中用户名字构建的 B-树示例：

MySQL 自适应哈希索引（Adaptive Hash Index）插图 — **B-树示例图**

在该示例中，N = 2，且所有节点中的值槽都已填满。对于 InnoDB 的 B-树索引，N 通常会更大，因为它由 InnoDB 页面能容纳的值数决定（默认为 16k）。此外，为了加速未来插入操作，节点通常会预留一定的空间缓冲。
当你在 InnoDB 表上创建索引时，MySQL 会构建一个 B-树，包含索引列中的所有值。在节点值的前后指针分别指向值小于和大于该节点数据的子节点。因此，从左到右遍历该结构可以按顺序访问所有数据元素。
一般情况下，B-树节点的大小可以由开发者自由决定。而在 InnoDB 中，索引节点的大小与 InnoDB 页面大小一致。由于页面较大，每个节点可能存储数百个值。
假设我们想在这棵树中查找名字为 paul 的用户：

MySQL 自适应哈希索引（Adaptive Hash Index）插图1 — **B-树查找示例图**

执行流程如下：

比较 paul 和 ian，确定 ian < paul；
检查发现 paul < remy，因此沿中间指针向下访问；
依次比较 paul 与 liam 和 omar，paul 均大于两者，沿第三指针向下访问；
在叶节点中发现 paul 的数据。

这种查找方法比线性扫描所有元素快得多。然而，它的复杂度仍不是 **O(1)**，通常需要多次比较和页面加载操作。在节点值较少且数据集较小时，B-树相较线性搜索的优势不明显。但对于大型数据集，优势非常显著。即使对于包含数百万行的表，InnoDB B-树索引通常也不需要超过 5 层。

InnoDB 缓冲池

当使用 InnoDB 时，所有数据（包括列上的索引）都存储在磁盘页中。在执行查询时，MySQL 需要能够将这些数据的子集加载到 RAM 中以加快访问速度。在 MySQL 中，这片用来存储 InnoDB 数据的内存区域称为 **缓冲池（buffer pool）**，其大小可以通过 innodb_buffer_pool_size 配置选项设置。MySQL 运行时，从磁盘读取（默认为 InnoDB 的 16k 页面）并将页面存入这片 RAM 区域。
通常情况下，缓冲池越大，数据库性能越好，直至缓冲池大小能完全覆盖数据集大小。如果数据集大小超过缓冲池容量，MySQL 最终会根据修改的 **最近最少使用（LRU）算法**逐渐从缓冲池中驱逐页面，为新页面腾出空间。
由于这种结构，当 MySQL 开始执行 B-树索引查找时，最初许多页面需要从磁盘加载，这是一种昂贵的 I/O 操作。然而，随着查找次数增多，许多页面会驻留在缓冲池中，因此每次访问 B-树节点和比较操作速度会提升，因为它们主要依赖内存而非磁盘。这虽然提高了性能，但仍需要多次在 B-树中访问页面以完成搜索。

哈希查找与性能

另一种快速查找大数据集的方法是使用 **哈希（hashing）**。使用哈希方法时，我们将所有数据（例如用户姓名）存储在一个大的哈希表中。执行查询时，例如查找名字为 paul 的用户，哈希函数会生成可重复的输出索引，该索引用于直接查找哈希表中对应的数据。
在没有冲突的情况下，哈希表查找是 O(1) 操作。如果数据集存储在内存中，这种方法甚至比 B-树索引查找速度更快。

MySQL 自适应哈希索引（Adaptive Hash Index）插图2 — **哈希表查找示例图**

虽然 MySQL 广泛支持 BTREE 和 HASH 索引，但 InnoDB 引擎并不支持 HASH 索引。如果你尝试在基于 InnoDB 的表上创建 USING HASH 索引，MySQL 会改为创建 B-树索引。例如：

CREATE INDEX alias_index ON user(username) USING HASH;

上述命令执行时不会报错，但通过 information_schema 查看后会发现：

SELECT table_name, index_name, index_type
FROM information_schema.statistics
WHERE table_schema = 'quiz'
AND table_name = 'user';

+------------+-------------+------------+
| TABLE_NAME | INDEX_NAME  | INDEX_TYPE |
+------------+-------------+------------+
| user       | alias_index | BTREE      |
| user       | PRIMARY     | BTREE      |
+------------+-------------+------------+

这说明 HASH 索引实际上并未创建，而是改为创建了 BTREE 索引。
尽管缺少磁盘上的 HASH 索引支持令人遗憾，但这并不意味着哈希无法用于索引查找。

自适应哈希索引（Adaptive Hash Index）

尽管 InnoDB 不支持磁盘存储的 HASH 索引，MySQL 提供了一项功能，可以进行用于索引查找的内存哈希操作。这项功能称为 **自适应哈希索引（Adaptive Hash Index, AHI）**，可以加速已经较快的 B-树查找，提升查询性能。AHI 作为一个层，位于 MySQL 执行层与内存缓冲池之间。

顾名思义，自适应哈希索引会在运行时动态构造，并根据工作负载的特性调整使用方式。如果 MySQL 观察到某个值在 B-树索引中被反复查找，可以基于该值或其前缀在 AHI 中创建一个条目。对于相同值的后续查找（根据 MySQL 观察的重复使用），它会使用 AHI 而不是 B-树索引。AHI 的键是底层索引的值（或值的前缀），而值是指向该数据所在位置的指针，指针的目标是 InnoDB 缓冲池。

如何与缓冲池协同工作

AHI 的指针仅指向缓冲池中的数据。因此，缓冲池必须足够大才能激活 AHI。如果缓冲池太小且驱逐频繁，AHI 的使用就不值得了。不过，MySQL 能根据缓冲池的行为自动调整 AHI 的使用。如果条件不适合（如查找重复少、缓冲池小等），MySQL 会减少甚至停止使用 AHI。
虽然 AHI 能加速查询，但维护这个特殊哈希索引也存在一定的开销。该功能可以通过 innodb_adaptive_hash_index 配置选项启用或禁用。默认情况下通常是启用的，但如果你确定工作负载不会从中获益，可以在配置文件中设置 innodb_adaptive_hash_index=0 禁用它。

测试自适应哈希索引的性能

让我们运行一些测试，看看自适应哈希索引如何帮助提升工作负载性能。例如：以下查询执行 50 万次，分别测试启用和禁用 AHI 的场景：

SELECT user_id, username, bio FROM user WHERE username = 'willpeace1';

测试表有超过 3.9 亿行数据。当禁用 AHI 时：

$ python3 same_query.py 500000 1
starting query load
completed in 35.6 seconds
QPS = 14043.57

启用 AHI 后：

$ python3 same_query.py 500000 1
starting query load
completed in 29.94 seconds
QPS = 16701.1

结果显示查询速度提升了约 16%。虽然提升幅度不大，但对于已经非常高效的 B-树查找，这是一个额外的优化，让查询执行更快。

总结

在处理大型、多 TB 数据库以及每秒执行数十万次查询的工作负载时，即使是小幅性能改进也会对查询延迟和数据库服务器的基础设施需求产生巨大影响。**自适应哈希索引（AHI）** 为已经快速的 B-树索引查找提供了额外的性能优化，帮助某些类型的工作负载进一步提升性能。然而，AHI 是否对你的工作负载有帮助，取决于数据访问模式以及 InnoDB 缓冲池的大小。

MySQL 自适应哈希索引（Adaptive Hash Index）插图5