ハッシュインデックス

このレッスンで分かること

ハッシュインデックスが等価検索で O(1) を実現する仕組み

範囲検索や ORDER BY が使えない理由

実際の DB でハッシュインデックスがどこで使われているか

ハッシュインデックスとは

等価検索専用の高速インデックスとその制約。本レッスンでは、ハッシュインデックスの基本から実際の使いどころまでを整理し、現場で迷わず使える形に落とし込みます。

ハッシュインデックスの原理

ハッシュインデックス (Hash Index) は、キーをハッシュ関数で固定長の値に変換し、そのハッシュ値で バケット配列 を引く構造です。

プレーンテキスト

hash("alice@ex.com") = 0x3F   → バケット 63 → 行ポインタ
hash("bob@ex.com")   = 0xA1   → バケット 161 → 行ポインタ

検索は 「ハッシュ計算 → 配列アクセス → 行ポインタを辿る」 だけで、計算量は O(1) です。B+tree の O(log n) よりさらに速い。

diagram (will load when visible)

範囲検索ができない

ハッシュインデックスの致命的な制約は、ソート順を保たない ことです。

hash("alice") = 0x3F で、hash("alicf") = 0xD2 のように、わずかに違うキーがまったく違うバケットに飛びます。ソートされていないため、WHERE age BETWEEN 30 AND 50 のような範囲検索や ORDER BY age には使えません。

唯一可能なのは 完全一致 (=、IN) のみです。

クエリ	B+tree	Hash
WHERE id = 100	効く	効く
WHERE id IN (1,2,3)	効く	効く
WHERE id > 100	効く	効かない
WHERE id BETWEEN 100 AND 200	効く	効かない
ORDER BY id	効く	効かない
WHERE name LIKE 'a%'	効く	効かない

これがハッシュインデックスがメインインデックスにならない理由です。

ハッシュ衝突

異なるキーが同じバケットに入ることを ハッシュ衝突 と呼びます。バケット内ではリンクリストや別ハッシュで管理しますが、衝突が多いと O(1) ではなく O(n) に近づきます。

衝突を減らすには、

バケット数 をデータ量に比例させる
良いハッシュ関数 （分布が均一）を使う
必要なら 動的拡張 （バケット数を倍々に増やす）を行う

実装の現場

MySQL InnoDB

InnoDB は明示的なハッシュインデックスを サポートしていません。ユーザーが CREATE INDEX ... USING HASH を書いても、内部的には B+tree になります。代わりに 適応的ハッシュインデックス (Adaptive Hash Index) という機能があり、頻繁にアクセスされる B+tree のページに自動でハッシュインデックスを内部生成します。

MEMORY エンジン (MySQL)

ENGINE=MEMORY のテーブルは、デフォルトでハッシュインデックスを使います。USING BTREE で切り替えも可能です。

SQL クエリ

CREATE TABLE sessions (
  token VARCHAR(64) PRIMARY KEY,
  user_id INT,
  expires_at INT
) ENGINE=MEMORY;

PostgreSQL

PostgreSQL は CREATE INDEX ... USING hash でハッシュインデックスを作れます。9.x まではトランザクション安全でなく WAL も無く非推奨でしたが、10 以降で改善され実用可能になりました。それでも B-tree が無難な選択肢です。

Redis / Memcached

KVS の代表である Redis や Memcached は、データ構造そのものが巨大なハッシュテーブルです。GET key は実質的にハッシュインデックスを引く操作で、O(1) で取り出します。

いつ使うか

ハッシュインデックスが有効な場面は限定的です。

完全一致だけが必要 で、範囲・ソートが不要
セッショントークンやキャッシュキー
データが小さくメモリに乗る
パフォーマンスを徹底的に追求する場面

それ以外は B+tree で十分です。実際、ほとんどの DBA は「困ったら B+tree」と言います。

ハッシュは「速いが用途が狭い」専門家の道具。B+tree は「万能ナイフ」。

ハッシュインデックスの仲間

ビットマップインデックス — 値ごとにビット配列を持つ。カーディナリティが低い列に強い。Oracle でサポート（PostgreSQL は実行時のビットマップスキャンのみ対応で、恒久的なビットマップインデックス型は持たない）
GIN (Generalized Inverted Index) — PostgreSQL で全文検索や JSON 検索に使う
GiST (Generalized Search Tree) — 地理空間データ向け

これらはハッシュとは別系統ですが、「B-tree じゃない索引」の代表例です。

やってみよう

MySQL MEMORY テーブルを作り、ハッシュインデックス vs B-tree で 10 万件の完全一致検索のベンチマークを取る
同じテーブルで範囲検索 WHERE id BETWEEN 1 AND 100 がハッシュインデックスでどう動くか試す
PostgreSQL で CREATE INDEX ... USING hash を作り、EXPLAIN でハッシュインデックスが使われるか確認

よくある質問

Q. インデックスを貼ると遅くなる処理はありますか？

A. INSERT / UPDATE / DELETE は遅くなります。インデックス自体も更新が必要なため、書き込みが多いテーブルに大量のインデックスを貼ると書き込み性能が落ちます。読み取りと書き込みのバランスで判断し、不要なインデックスは削除しましょう。

Q. 複合インデックスは順番が大事ですか？

A. 順番が極めて重要です。(user_id, created_at) のインデックスは WHERE user_id = ? AND created_at > ? で効きますが、WHERE created_at > ? だけだと効きません。よく使う絞り込みカラムを先頭に置くのが定石です。

Q. インデックスが効いているか確認するには？

A. EXPLAIN（MySQL/PostgreSQL）または EXPLAIN ANALYZE で実行計画を見ます。type が ref / range / const なら使われていて、ALL は全件スキャン（インデックス未使用）です。意図と違うインデックスが使われている場合は USE INDEX で強制することもできます。

次のレッスン

次は カバリングインデックス で、等価検索専用の高速インデックスとその制約を学びます。

事前確認 — 進む前に次の 3 つができることを確認しましょう。

ハッシュインデックスの要点を自分の言葉で説明できる
このレッスンの最小コード (または操作手順) を見ずに書ける
練習問題やクイズで間違えた箇所を読み直して理解した

理解度チェック (30 秒)

Q. ハッシュインデックスとは何か、1 文で説明してください。

この章のポイント

A. 本文の「このレッスンで分かること」または冒頭の説明文を見直し、自分の言葉で要約できれば OK。詰まったら本レッスンの最初の H2 セクションを読み返してみましょう。

関連レッスン