Adaptive Hash Index

引言

建立一个＂不大不小刚刚好＂的哈希表

问题的提出

• 随着MySQL单表数据量增大，（尽管B+树算法极好地控制了树的层数）索引B+树的层数会逐渐增多；
• 随着索引树层数增多，检索某一个数据页需要沿着B+树从上往下逐层定位，时间成本就会上升；

为解决检索成本问题，MySQL就想到使用某一种缓存结构：根据某个检索条件，直接查询到对应的数据页，跳过逐层定位的步骤。这种缓存结构就是AHI。

索引筛选

上图可以看出来 我们筛选的是那些索引树被使用的足够多，且该树上的索引行也要使用足够多，且该索引行命中的数据要在对应的数据库页中占比足够大

建立hash index

经过上面的步骤 我们可以开始建立AHI了，我们举一个例子来说明如何建立AHI,假设以上三个关卡的通关情况如下

• 表table具有4列： A1,A2,A3,B1. 具有两个索引idx(A1,A2,A3)以及 idx2(B1)
• 第一个选出的索引是idx1
• 第二个选出来的hash info 是 (2.0,true) 很多查询命中了idx1的最左两侧
• 第三个选出了某一个数据页P3,其中包含数据(1,1,1,1) 何 (1,2,2,2) 等

那么建立AHI的过程是 在内存中，为数据库页P3中每一行数据建立索引

• 对于数据(1,1,1,1) 根据hash info ,选中前两列建立AHI的一项，(1,1) 的哈希值 -> P3
• 对于数据(1,2,2,2) 根据hash info ,选取前两列建立AHI的一项，(1,2) 的哈希值-> P3
• 以此类推

我们终于可以AHI加速查询了，假设查询条件是A1=1 and A2=2，其满足条件：

• 命中了索引Idx1
• 索引Idx1上的hash info是(2, 0, true), 查询条件(A1=1 and A2=2)根据hash info转成(1,2)的哈希值
• 根据此哈希值在AHI中查询, 可查询到数据页为P3

从以上过程可以看出，如果命中了AHI，就可以跳过图2中查询索引树的4个步骤，一次到位找到数据页，提升性能。