適応的ハッシュインデックスとは

適応的ハッシュインデックス（Adaptive Hash Index）は、等価検索を速くするための仕組みです。通常のB-tree検索では、ルートから中間ノードを経てリーフまで複数ページをたどる必要があります。もし同じキーへの検索が何度も繰り返されるなら、毎回この経路をたどるのは無駄です。InnoDBは、B-treeの検索パターンを監視し、よくアクセスされるリーフページについて、キーからバッファプール上のレコードへ直接飛べる参照を自動で構築します。

user_id='user01'、name='Alice'を探すとき、ハッシュインデックスに載っていればルートと中間ノードを経ることなくリーフ上のレコードへ直接アクセスすることができます。

ハッシュインデックスの構築

ハッシュ値の生成

ハッシュ値はインデックスキーのプレフィックスから計算されます。プレフィックスはn_fields（列数）とn_bytes（バイト数）で定義されます。n_fieldsはプレフィックスに含める列の数で、先頭からn_fields列を使います。n_bytesは、その次の列の先頭何バイトを含めるかです。列の境界でちょうど終わるならn_bytesは0になります。

例えば(user_id, name)の複合セカンダリインデックスで、user_id='user01'、name='Alice'という行を考えます。n_fields=2、n_bytes=0なら、プレフィックスはuser_idとnameがすべて含まれる'user01' + 'Alice'です。一方n_fields=1、n_bytes=3なら、user_id列全体に加えて次のname列の先頭3バイトだけを使い、'user01' + 'Ali'がプレフィックスになります。

同じプレフィックスを持つレコードが複数あるときは、キー未満とキー以上の境界に接する1レコードだけをハッシュインデックスに登録します。

ハッシュインデックスに登録されるレコード

等価検索で一致するレコードが存在するケースを考えます。プレフィックスに対してレコードが一意に定まる場合（この例ではn_fields=2、n_bytes=0）、キー以上の最小値は探している行そのものなので、そのレコードへの参照が登録されます。

等価検索で一致するレコードが存在しないケースでは、探しているキー未満の最大値とキー以上の最小値のうち、探しているキーと同じプレフィックスを持つ方を登録します。以降の例はプレフィックスをuser_id列のみ（n_fields=1、n_bytes=0）とします。

検索しているuser01,Bobは存在しないレコードです。左のuser01,Aliceは同じuser_id、右のuser02,Bobは別のuser_idなので、プレフィックスが同じ左が登録されます。

検索しているuser02,Aliceは存在しないレコードですが、左のuser01,Aliceは別のuser_id、右のuser02,Bobは同じuser_idなので、右が登録されます。

インデックスは、今検証中のn_fieldsとn_bytesの組み合わせについて、仮にハッシュエントリがあった場合に有効だったかをメモリ上のカウンタで数えます。バッファプールの各ページも、同じ組み合わせでハッシュエントリが有効だった回数を独自に保持します。両方の数が閾値を超えると、そのページにハッシュエントリを作ります。今の組み合わせでは有効とみなせない検索になると、n_fieldsとn_bytesを選び直し、インデックス側のカウンタはリセットされます。

ハッシュエントリの削除

適応的ハッシュインデックスは肥大化し続けるわけではありません。参照先のB-treeリーフページがバッファプールから追い出されると、そのページを指すハッシュエントリは削除されます。ページ分割やページ破棄などでB-treeの構造が変わったときも、該当するエントリは削除されます。検証中のn_fieldsとn_bytesが変更され、新しい組み合わせでインデックス側とページ側の両方の数が再び閾値を超えたときも、そのとき検索していたページの古いエントリを削除してから新しいエントリを作ります。