比較・疑問解決 · 基礎から応用へ

ハッシュ索引とB木索引

PostgreSQLの等価検索・範囲検索・並び順を例に、ハッシュ索引とB木索引の得意な条件と更新費用を比較します。

この記事をロゲイアに質問する確認問題3問に進むこれまでの誤答を復習する

更新日

この記事の目次
  1. 索引が絞り込める条件を比べる
  2. 等価検索だけなら両方が候補になる
  3. 範囲とORDER BYでは順序が役立つ
  4. 読み取りだけでなく更新も数える
  5. 実行計画を使って選択を確かめる
  6. この記事をロゲイアに質問する理解を確かめる

索引が絞り込める条件を比べる

ハッシュ索引は、値から計算したハッシュコードを使って候補を探します。B木系の索引は、順序を持つキーの範囲から候補を絞ります。どちらも表のすべての行を毎回調べずに済む可能性がありますが、対応する検索条件は同じではありません。ここではPostgreSQL 18の通常の索引を具体例にし、メモリ上の一般的なハッシュ表の期待O(1)を、そのままDBの問い合わせ時間へ置き換えないことにします。索引ページの読み込み、表本体へのアクセス、可視性の検査、取得件数なども、実際の費用に含まれるためです。

PostgreSQL 18の要求ハッシュ索引B木索引
単純な等価比較対応条件の下で利用可能対応条件の下で利用可能
範囲比較基本の対応対象ではない対応条件の下で利用可能
順序付き取得キー順を提供しない対応する順序で利用可能

等価検索だけなら両方が候補になる

WHERE customer_id=42のような単純な等価条件では、対応する型と演算子クラスの下で、B木とハッシュの両方が候補になります。ハッシュコードが一致しても元の値が必ず一致するとは限らず、衝突を考慮した正しい判定が必要です。また、customer_id=42の行が表の大半を占めるなら、索引を使う方がかえって不利になる場合があります。「等価条件だから必ずハッシュを選ぶ」という判断はできません。データの分布、表と索引の大きさ、取得する列と行数を含め、実行計画と実際の負荷から確認してください。

範囲とORDER BYでは順序が役立つ

WHERE created_at≧ある日時、ORDER BY created_atという要求では、時刻の順序を持つB木索引が、対応する条件の検索や並び順の取得に利用できる場合があります。PostgreSQLのハッシュ索引は単純な等価比較が対象で、同じ索引からその範囲や順序を得るものではありません。複合B木索引ではキーを並べる順番も重要です。例えば(tenant_id, created_at)は、ある利用組織の中を時刻順に探す要求と関係します。索引が存在することと、指定した条件・順序に合うことは別なので、列名だけを見て索引が使われるはずだと決めないでください。

読み取りだけでなく更新も数える

索引を増やせば、追加や更新に伴う索引の変更、ページの管理、WAL、領域の費用も増え得ます。同じ列に複数種類の索引を置くなら、それぞれが実際の要求をどれだけ改善するかを確認します。B木が等価と範囲の両方に使えるから、どのワークロードでも一つで十分という意味でもありません。反対に、ハッシュが等価専用だから常に小さく高速とも限りません。比較には、読み書きの比率、キーの重複や幅、作業集合、キャッシュ状態を含めます。索引の理論上の性質と、製品が実装する制約や運用費用を分けると、変更の理由を説明しやすくなります。

実行計画を使って選択を確かめる

EXPLAINで候補の計画を確認し、実行する必要がある場合はEXPLAIN ANALYZEが実際に文を動かすことを理解して使います。推定行数と実際の行数、ループ数、バッファの指標を見て、索引名が出たかだけで成功を判断しません。比較用のデータは本番と異なる分布になりやすいので、件数だけでなく偏りも確認します。更新を伴う試験や索引の削除を、本番で思いつきのまま行うのは避け、使う環境と影響範囲を決めます。最終的には、等価、範囲、順序、更新のどれを改善したいかを明確にし、その要件に合う最小限の索引を検証します。

読了と問題の結果を、言語ごとにこのブラウザへ保存します。

コースの順番に沿って学ぶ

サーバーの中で起きていること · STEP 12

学習コースから次を選ぶ