ハッシュインデックス

等号しか書かないなら、木を辿る必要すらない

セッショントークンから利用者を引く処理を考えます。条件は必ず完全一致で、範囲も並べ替えも一生使いません。

こういうときに木を辿るのは、少し遠回りです。境界と比べながら段を下りるのは、順序を保つための作業だからです。順序が要らないなら、値から置き場所を直接計算してしまえばよい。

ハッシュ索引はそれをやります。キーを関数に通して数値にし、その数値を並んだ入れ物の番号として使います。中にあるのは行のありかです。段数という概念がないので、件数がいくら増えても手数は変わりません。

本の索引でいえば、五十音順に並べるのをやめて、語ごとに置き場所を計算で決めているようなものです。順に並んでいないので眺めても意味を成しませんが、探したい語が分かっているなら一発で開けます。

並び順を捨てた代償

代わりに失うものがあります。ハッシュ関数は、似た値をわざと遠くに飛ばします。1 文字違うだけの 2 つのキーが、まったく別の場所に入ります。近い値が近くに置かれないということは、順序がどこにも残っていないということです。

使えるのは完全一致と、その列挙だけです。これがハッシュ索引の主役になれない理由です。

もう 1 つ、違うキーが同じ入れ物に入ってしまうことがあります。中では一覧にして順に見るので、偏りが大きいと手数が増えていきます。入れ物の数をデータ量に合わせて増やし、偏りにくい関数を選ぶことで抑えます。

ただし、入れ物を増やす作業自体が見えにくい負担です。番号の付け方が変わるので、入っている全部を計算し直して置き直します。件数の伸びが読めない用途では、この作り直しが「ときどき固まったように見える」原因になります。手数が常に一定という説明は、増えない前提での話です。

貼ったつもりが、B+tree になっていた

現場では、思ったところに存在しないことがあります。

MySQL の InnoDB は、ハッシュ索引を明示的に作らせてくれません。ハッシュを指定して書いても、黙って B+tree が作られます。代わりに、よく触られる部分を DB 自身が判断して内部でハッシュ化する仕組みが動いていますが、これは利用者が制御するものではありません。メモリ上に置くテーブルでは既定でハッシュが使われます。PostgreSQL では明示的に作れるものの、長らく実用に耐えない時期があり、いまでも既定の選択肢にはなっていません。

一方、Redis や Memcached のようなキーと値だけの倉庫は、構造そのものが巨大なハッシュ表です。キーを渡して値を受け取る操作しか用意していないので、順序を捨てた設計が最初から噛み合っています。

そう考えると、ハッシュ索引は「どの索引を使うか」の選択肢というより、順序が本当に要らない場所に現れる形と見たほうが近いです。迷ったら B+tree で困りません。順序を保つぶんの手間は払っていますが、その手間があとから効いてくる場面のほうが、実際にはずっと多いからです。