ハッシュ

概要

チューニング技術としてB-treeの次に重要なのは，ハッシュ（hash）です。ハッシュとは「ごちゃまぜ」とか「細切れ」という意味で，ハッシュドビーフとかハッシュポテトなどの料理名にも使われています。

ハッシュのポイントは分散です。キー値に対して適当な関数を適用して，データを格納する先のアドレスを割り当てるのですが，このときポイントなのは，異なる値のキーに対しては，異なるアドレス（それもなるべく離れた）を割り振れるかどうかです。これができるほど，ハッシュ関数として優れているということになります（図6）。

なおハッシュは，Postgre SQLやMy SQLのようにインデックスとして実装しているDBのほか，OracleやDB2，My SQLのようにパーティションとして実装しているDBもあります（注3）。ハッシュパーティションの場合，テーブル作成時にハッシュキーを指定して，実データそのものを分散させてしまいます。これは，より徹底したハッシュの効果が望める一方，テーブル作成後にハッシュキーを変更するのが難しいという難点があります。

注3）

Oracleは，逆キーインデックスという形で，一種のハッシュインデックスも持っています。

特性

ハッシュの特性を，先ほどのB-treeのようにチャートで示すと図7のようになります。

均一性

うまい具合にハッシュによるデータ分散が成功している場合，目的の1つのデータを見つけ出すために必要なコストは，1回のハッシュ関数の計算と1回のファイルアクセスだけです。したがって，ほぼ定数時間O (1)で見つけ出すことができます。これはキー値によらず該当します。

しかし現実には，なかなか完全に均等にデータを分散できるハッシュ関数はなく，キー値が異なるのに，格納先のアドレスが同じになる衝突（collision ）が発生します（図8）。衝突するデータに対しては，パフォーマンスが悪化します。

持続性

ハッシュは持続性にもすぐれており，衝突がないと仮定すれば，データ量がいくら増えようと，処理速度はつねに定数時間O (1)が保証されます（図9）。

しかし，先述のように，現実にはデータ量が増大するにつれて衝突の起こる確率も増えるため，徐々にパフォーマンスは悪くなるでしょう（図9のグラフの点線が示すように）。

処理汎用性

ハッシュは，検索だけでなく，挿入／削除／更新といった処理に対しても，やはり定数時間で処理するため，非常に高い性能を発揮します。ここまで見るとハッシュというのはたいへん性能が良いアルゴリズムだと思うでしょう。実際，均一性や持続性という観点では，ハッシュはB-treeより優れる場合もあります。しかし，ここから先が悩みの種です。

非等値性

ハッシュは，たしかに検索などの処理を非常に小さい定数時間で処理するのですが，実はこれが言えるのは，あくまで1つだけのキー値を対象とした操作を考えた場合です。構造から明らかなように，ハッシュは，ランダムアクセスに特化したアルゴリズムであり，シーケンシャルアクセスにはまったく向いていません。したがって，不等号や範囲検索に対しては，何の役にも立ちません（もちろん否定条件に対しても意味がありません）（注4）。

注4）

たとえば，My SQLのマニュアルには，次のように記述されています。「[ハッシュインデックスは] <のように値の範囲を検索する比較演算子には使用されません。オプティマイザはORDER BYオペレーション速度を上げるためにハッシュインデックスを使用することはできません。」（「6.4.5. My SQLにおけるインデックスの使用」『My SQL 5.1 リファレンスマニュアル』）。

親ソート性

同様の理由から，ハッシュはソート処理の助けにもなりません。B-treeは，それ自体がソートされた配列だったので，これにアクセスすることで，実データのソートを回避することが可能でした。しかし，ハッシュにそういう効果はありません。