基礎インデックスの種類
ハッシュインデックス
定義
ハッシュインデックスとは、キーの値をハッシュ関数で変換し、対応するバケットに格納・参照することでO(1)相当で等価検索を行うインデックス方式である。
キーをハッシュ値に変換してバケットに配る
ハッシュインデックスの仕組みはシンプルです。キーをハッシュ関数に通して固定サイズの数値に変換し、そのバケットに格納する。 探すときも同じ関数でバケットを特定して、そこだけを見れば済みます。 件数が増えても平均O(1)で目的にたどり着けるのが強みです。
計算の流れ
「1ステップ」で入力からバケット到達までを順に追う。「自動再生」で連続再生。
1. 入力を受け取る
2. ハッシュ関数を通す
3. 5 で割った余りを取る
4. バケット3 を線形探索
バケット 0衝突: 2件を線形探索
yamada → (2,1)kobayashi → (2,2)
バケット 1
kato → (3,2)
バケット 2衝突: 3件を線形探索
tanaka → (1,1)ito → (1,3)watanabe → (2,3)
バケット 3衝突: 3件を線形探索
suzuki → (1,2)nakamura → (2,0)takahashi → (3,0)
バケット 4衝突: 2件を線形探索
sato → (1,0)saito → (3,1)
バケット内の各エントリは
キー → 行ID の組。 「1ステップ」で入力からバケット到達までの流れを順に追う。ハッシュインデックスの弱点
- 範囲検索ができない: ハッシュ値は元の値の大小関係を保存しないため、
WHERE id BETWEEN 10 AND 20のような検索は不可能。 - ソートに使えない:
ORDER BYを高速化する用途にも使えない。 - 複合条件が組みにくい: 一部のカラムだけでの検索や先頭一致は不可。
使うべき場面
セッションストアのキャッシュキー引き、ユニークIDでの等価検索、インメモリDB。 逆に一般的な業務テーブルの主インデックスとしてはB-treeが選ばれることがほとんどです。
よくある疑問
Q.ハッシュインデックスがB-treeより速いのに使われる場面が少ないのはなぜ？
A.範囲検索・並び替え・複合的な条件に対応できないためです。用途が「主キーやユニーク値の等価検索」に限られます。
Q.ハッシュ衝突が起きるとどうなりますか？
A.同じバケットに複数のキーが入り、線形探索やチェーンで解決します。衝突が多いと性能が落ちるため、ハッシュ関数と負荷率の設計が重要です。
関連トピック
もっと学びたい方へ（おすすめ書籍）
本セクションはAmazonアソシエイトのリンクを含みます。購入いただくと運営者に紹介料が入る場合があります。
オンライン個別指導
もっと深くDBを学びたい方へ。
たいてっくが、SQL・データベース設計・パフォーマンスチューニング・ IPAデータベーススペシャリスト対策まで、1対1で学習をサポートします。まずは無料相談から。