InnoDB存储引擎使用哈希算法来对字典进行查找,其冲突机制采用链表方式,哈希函数采用除法散列方式。对于缓冲池页的哈希表来说,在缓冲池中的Page页都有争chain指针,它指向相同哈希函数值的页。而对于除法散列,m的取值为略大于2倍的缓冲池页数量的质数。例如:当前参数 innodb_buffer_pool_size的大小为10M,则共有640个16KB的页。对于缓冲池页内存的哈希表来说,需要分配640×2=1280个槽,但是由于1280不是质数,需要取比1280略大的一个质数,应该是1399,所以在启动时会分配1399个槽的哈希表,用来哈希查询所在缓冲池中的页。

那么 InnoDB存储引擎的缓冲池对于其中的页是怎么进行查找的呢?上面只是给出了一般的算法,怎么将要查找的页转换成自然数呢?
其实也很简单, InnoDB存储引擎的表空间都有一个 space_id,用户所要查询的应该是某个表空间的某个连续16KB的页,即偏移量 offset。InnoDB存储引擎将 space_id左移20位,然后加上这个 space_id和 offset,即关键字K= space_id<<20+ space_id+ offset,然后通过除法散列到各个槽中去。

自适应哈希索引

自适应哈希索引采用之前讨论的哈希表的方式实现。不同的是,这仅是数据库自身创建并使用的,DBA本身并不能对其进行干预。自适应哈希索引经哈希函数映射到一个哈希表中,因此对于字典类型的查找非常快速,如 SELECT * FROM TABLE WHERE index_col=xxx。但是对于范围查找就无能为力了。通过命令 SHOW ENGINEINNODB STATUS可以看到当前自适应哈希索引的使用状况,如:

现在可以看到自适应哈希索引的使用信息了,包括自适应哈希索引的大术使用情况、每秒使用自适应哈希索引搜索的情况。需要注意的是,哈希索引只能用来搜索等值的查询,如:
SELECT * FROM table Where index_co1=xxx
而对于其他查找类型,如范围查找,是不能使用哈希索引的。因此,这里出现了non-hash searches的情况。通过 hash searches:non-hash searches可以大概了解使用哈希索引后的效率。
由于自适应哈希索引是由 InnoDB存储引擎自己控制的,因此这里的这些信息只供参考。不过可以通过参数 innodb_adaptive_hash_index来禁用或启动此特性,默认为开启。