【2026年10月版】

索引と探す技術（第2回）― キーによる検索、不在の判定、同一性の確認

公開日: 2026/10/02
読了時間: 約 22分

第1回では、ソートとインデックスという、問い合わせの前に済ませておく仕事を扱った。第2回は、キーが一致するかを調べる構造を扱う。

1. ハッシュ表 ― 順序と引き換えの等価検索

ハッシュ表は、キーから計算した整数で表の中の置き場所を決めておき、検索時も同じ計算で置き場所へ直接向かうことで等価検索を高速化する。教科書ではこの計算を、キーを整数空間へ写像するハッシュ関数と呼ぶ。ハッシュ関数はキーを表の中へ均等に散らすように作られており、値の近いキーどうしも互いに関係のない位置に置かれる。位置からキーの大小関係を読み取れないため、ハッシュ索引は範囲検索には使えない。等価検索に限ってハッシュ索引を使い、範囲検索や ORDER BY には通常、順序を保つ B木を使う。「以上」「未満」「次の値」を問う条件にハッシュ索引を張っても、結局は全件を走査することになる。

異なるキーが同じ置き場所に割り当てられることを衝突と呼ぶ。その処理には、同じ置き場所に来たキーを一本のリストへ繋いでおく分離連鎖法と、隣接スロットを順に探す線形探査法がある。間隔を広げて探す二次探査法、二つ目のハッシュ関数で移動幅を決めるダブルハッシュ法、探索距離の偏りを均すロビンフッド・ハッシュ法も使われる。カッコウハッシュ法は、キーに複数の候補位置を持たせ、衝突時に既存要素を別位置へ押し出す。検索時に調べる場所を限定でき、最悪でも定数時間で検索を終えることを目標にした構造である。

近年の実用ハッシュ表では、キーと値とは別に、ハッシュ値の一部を書いた小さな札を制御メタデータとして並べておく Swiss Table 系が広がった。検索時は複数スロットの札を SIMD 的にまとめて照合し、札が一致したスロットのキーだけを確かめる。Abseil の設計では、ハッシュ値をテーブル位置用とメタデータ照合用に分割する。Go は1.24で map を Swiss Table 系の構造へ移行し、オープンアドレス法、グループ単位の制御情報、段階的なテーブル成長を採用した。同じハッシュ表という名前でも、現代 CPU のキャッシュ階層と並列比較を前提にした実装かどうかで、性能は大きく変わってくる。

2. 予測モデルとしての索引

ソート済みの索引では、見出しから、それが索引のどのあたりにあるかの見当をつけられる。見出しに偏りがあっても、その見出しより前の見出しが全体の何割あるかが分かれば何番目にあるかを計算でき、この割合を見出しごとに表したものを累積分布と呼ぶ。Learned Index は、データベースの索引で同じことをする。B木のように木をたどって位置を探す代わりに、ソート済みのキーの累積分布をモデルで学習しておき、キーを渡すとそれが何番目付近にあるかを予測する。累積分布はキーが大きくなるほど増えるので、予測した位置もキーの大小の順に並び、範囲検索の両端の位置も同じモデルで求められる。

予測は外れるため、予測位置の周囲を別に探索して誤差を吸収する。SOSD を使った評価では、読み取り専用でメモリ上の密な配列という条件で、学習索引がサイズと性能の組み合わせで従来の索引を上回った。ただしこの優位は、あくまで読み取り専用の条件で測ったものである。更新で分布が変われば再学習が要り、最悪性能の保証も難しい。優位が出るかどうかはデータの分布に左右され、その実測は第8回で扱う。learned sorting も提案されており、特定の分布やデータ型では既存の基数ソートを上回る結果が報告されている。ただしその結果は入力の分布と学習のコストに左右され、外れ値の影響も受ける。

外れた予測の害を抑える設計もある。予測位置から範囲を2倍ずつ広げて調べ、真の位置を囲めたら二分探索に入る。予測位置と真の位置の差を η とすると、比較回数は高々 2 log η になる。η は配列の長さ以下なので、予測がどれほど外れても、比較回数は二分探索の2倍以内に収まる。Algorithms with Predictions は、予測が良ければ最適に近く、外れても予測なしの最悪性能に戻る設計として、この例を挙げている。

3. ひとつの DB が六種類の索引を持つ理由

PostgreSQL 18 が標準で備えるアクセスメソッドは、B木・Hash・GiST・SP-GiST・GIN・BRIN の六種類だ。ここに拡張として Bloom も加えられる。この構成は、索引ごとに効く条件が分かれていることの表れになっている。

六種類はそれぞれ扱う条件が違う。B木は比較可能な値の範囲と並び順を扱い、Hash は等価条件だけを扱う。GIN は配列、全文、JSON のように、ひとつの行へ複数の検索キーが含まれる場合に効き、本の巻末索引が語ごとに載っているページを並べるのと同じ形で、キーごとに該当する行の一覧を持つ。GiST は、木をたどって候補を絞る骨組みを共通にしておき、「重なる」「含む」といった判定をデータ型ごとに差し込めるようにした仕組みで、検索構造そのものを拡張するフレームワークと呼ばれるのはこのためである。SP-GiST は空間を非平衡に分割する構造を受け持ち、データが密な場所は細かく、疎な場所は粗く区切るので、木の枝の深さが場所ごとに違ってくる。BRIN はページ範囲ごとの最小・最大などの要約を持ち、条件の値が要約の範囲の外にあるページ範囲をまとめて読み飛ばす。Bloom は複数列の存在可能性を確率的に判定し、次節で扱うブルームフィルタを行ごとに持つことで、指定した列の値の組み合わせに合いそうな行だけを候補に残す。

DuckDB では Adaptive Radix Treeが PRIMARY KEY や UNIQUE の制約のために自動生成される。ART が速くするのは単一キーの検索（point lookup）と、条件に合う行がテーブル全体の0.1%未満にとどまる検索（選択率0.1%未満の検索）で、結合、集約、ソートの性能は ART の有無と無関係に決まる。

索引を増やすと、読み取りが速くなる一方で、書き込み、削除、VACUUM、コンパクション、バックアップの負担とメモリ使用量も同時に増える。すべての列へ索引を張る運用では、読み取りの改善分を書き込み側の劣化が相殺しやすい。複合索引では列順も効いてくる。(tenant_id, created_at) と (created_at, tenant_id) では利用できる検索条件と範囲走査が変わるため、列順はデータモデルの見た目ではなく、クエリの絞り込み順序に合わせて決める。

4. 「ここにはない」と安価に答える索引

従来の索引は、レコードの位置を直接指すものが中心だった。大規模分析では、正確な位置を一件ずつ持つより、ページやファイルを丸ごと除外するほうが効く。BRIN、ゾーンマップ、min-max インデックス、ブルームフィルタは、いずれもこの除外のための構造である。Parquet や Iceberg のファイル統計、パーティションプルーニングも同じ働きをする。

ClickHouse のスキップインデックスは、一致する値の不在を判定できたデータチャンクを読み飛ばす。主索引がグラニュール単位で行っている枝刈りを、ソートキー以外の列へも効かせる。スキップインデックスには複数の型があり、ブルームフィルタもその一つとして選べる。

ブルームフィルタは複数のハッシュ関数とビット列を使い、集合への所属可能性を小さな容量で表現する。キーを登録するときは、そのキーを複数のハッシュ関数にかけ、得られた位置のビットをすべて立てておく。照会するときは同じ位置のビットを調べ、一つでも立っていない位置があれば、そのキーは一度も登録されていないと確定できる。すべて立っていた場合は、ほかのキーが立てたビットがたまたま重なっただけということもあるので「存在する可能性がある」と答えることになり、未登録のキーを存在すると答えるこの誤りを偽陽性と呼ぶ。1970年の原論文は、誤りを許す所属判定（membership）での、時間と空間のトレードオフを扱った。判定は非対称で、「存在しない」という判定は常に正しく、「存在する」という判定には偽陽性が含まれうる。ブルームフィルタが答えるのは、SSTable を読む必要があるか、キャッシュにキーがある可能性があるか、ネットワーク照会が必要か、重複候補を詳しく確認すべきか、といった問いに限られる。証明できるのは不在だけで、内容の同一性や変更された位置の証明は扱う範囲の外にある。

学習モデルで存在を判定する学習ブルームフィルタもある。Algorithms with Predictions は、Kraska らのこの提案を、モデルの後ろにバックアップのブルームフィルタを置き、登録済みのキーを「存在しない」と答えてしまう偽陰性を防いだ例として紹介している。モデルが外れても、「存在しない」と判定したものは確実に存在しない、という性質が保たれる。

その結果、一つのテーブルの読み取り経路には複数の構造が同時に並ぶ。ClickHouse のテーブルでは、ソートキー順の物理配置の上にグラニュール単位の疎な主索引が乗る。ソートキー以外の列にはスキップインデックスが働き、その型としてブルームフィルタを置ける。半世紀にわたって別々の文脈で提案された構造が、実装の中では隣り合っている。

正確に「ここにある」と答える構造も、安価に「ここにはない」と答える構造も、読む量を減らすという点で同じ働きをしている。

5. ハッシュによる同一性と変更範囲の圧縮

ハッシュは検索キーを作るほかに、内容が変化したかどうかの検知にも使われる。

最も単純なのは、ファイルやオブジェクト全体のハッシュ値を前回値と比較する方式である。ビルドキャッシュや配信ファイルの更新判定、バックアップ、オブジェクトストレージ、改ざん検知、重複排除に使われる。一バイトでも変われば全体のハッシュが変わるため、分かるのは変更の有無までで、変更箇所の特定には別の仕組みが要る。

Git は内容からオブジェクト ID を計算する内容アドレス型のファイルシステムとして設計されている。blob、tree、commit は内容に基づく ID で参照されるため、同じ内容は同じ ID で表現でき、tree オブジェクトをたどればディレクトリ単位の変更も判定できる。SHA-256 を使うリポジトリ形式も用意され、従来の SHA-1 形式からの移行仕様が整備されている。

大きなファイルの途中に数バイト挿入されると、固定位置のブロック分割ではそれ以降の全ブロックが変化したように見える。rsync は、受信側の固定ブロックにチェックサムを作り、送信側では窓を一バイトずつ動かしながらローリングチェックサムを更新する。一致候補を見つけた後により強いチェックサムで確認し、不一致の部分だけを送る。衝突しうる安価な要約で候補を探し、強いハッシュで正確に確認する二段構えである。

窓を動かしながらハッシュを差分更新する発想は、ゲームの探索にもある。ゾブリストハッシュは、駒とマスの組ごとに割り当てた乱数を XOR で合成して局面のハッシュを作り、一手指すたびに、動いた駒の分だけを XOR して更新する。一度読んだ局面の結果を再利用するための置換表で使われ、第5回で改めて扱う。

内容定義チャンキング（Content-Defined Chunking）（CDC）は、固定バイト数の代わりに、内容から算出した境界条件でチャンクを切る。典型的には窓を一バイトずつ動かしながら窓の中のバイト列のハッシュを計算し、その値があらかじめ決めた条件を満たした位置を境界にする。境界の位置がその周りの内容だけで決まるので、ファイル先頭へデータが挿入されても、その後に同じ内容が続けば再び同じ境界へ同期しやすい。FastCDC は、CDC の計算量を抑えながら重複排除率とスループットを両立する方式として2016年に提案された。2025年の FAST で発表された VectorCDC は、ハッシュを使わない CDC アルゴリズムの境界探索を SIMD 命令で行う方式で、既存のベクトル化実装に対して8.35倍から26.2倍のスループットを報告している。

マークル木では、葉にデータブロックのハッシュを置き、親には子ノードのハッシュを置く。

                root hash
              /           \
         branch A       branch B
          /    \         /    \
        h1     h2      h3     h4

二つのルートが同じなら木全体が同じと判定でき、異なる場合は差のある枝だけを下へたどることで変更範囲を特定できる。Amazon Dynamo は、レプリカどうしが中身を突き合わせて食い違いを直すアンチエントロピーの処理でマークル木を使い、全データの転送を避けながら、レプリカ間で食い違うキー範囲を特定した。分散レプリカの差分検出、大規模ディレクトリの同期、オブジェクトストレージ、バージョン管理、ブロックチェーン、改ざん検証、増分ビルドが主な用途に挙がる。

対象	手法	分かること
小さなオブジェクト	全体ハッシュ	変更の有無
大きなファイル	ブロックハッシュ	変更ブロック
挿入・削除が多いファイル	ローリングハッシュ／CDC	再利用可能な内容
ディレクトリやデータ集合	マークル木	変更された部分木
集合への存在確認	ブルームフィルタ	確実な不在
内容による保存・参照	内容アドレス	同一内容の共有
敵対的な改ざん検知	暗号学的ハッシュ	完全性検証

ハッシュ関数の種類を選ぶ前に決めておく項目が八つある。何を一単位として比較するか、どの頻度で再計算するか、変更位置まで必要か、衝突が性能の問題かセキュリティの問題か、入力を正規化するか、順序の違いを変更とみなすか、メタデータを含めるか、削除をどう表現するか、である。これらが決まって初めて、ハッシュ関数の選択が運用の安定につながる。JSON のキー順、時刻表現、浮動小数点の書式、Unicode 正規化が不安定なままだと、意味的には同じデータが異なるハッシュになり、不要なキャッシュミスや再ビルド、再同期が起きる。高速な非暗号学的ハッシュが適しているのは偶発的な変更の検知までで、意図的な衝突や改ざんに備える場面では、暗号学的ハッシュが要る。

第3回は、キーの代わりに語で探す場合を取り上げ、文字列走査と転置索引から、見つかった文書への順位付けまでを扱う。