【2026年10月版】

索引と探す技術（第1回）― 読む前に済ませておくこと

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

0. はじめに

全件を読めば答えは必ず見つかる。テーブルを先頭から末尾まで走査すれば、どんな条件でも該当する行は取り出せる。データが増えるほどこの走査は遅くなるため、読む量を減らす技術が積み上げられてきた。その技術は、検索しやすくする、検索する、探索するという三つの段階に分けて整理できる。

一つ目の検索しやすくする段階では、辞書が五十音順に並んでいるように、問い合わせが来る前にデータへ手を入れておく。ソートはデータに順序を与え、インデックスは順序や特徴を要約し、ハッシュは同一性や変更範囲をさらに小さな値へ圧縮する。二つ目の検索する段階では、索引を使って候補を削り、答えのありかを絞ってから必要な部分だけを読む。二分探索、文字列走査、転置索引、ベクトル検索がここに入る。

三つ目の探索する段階が扱うのは、答えの候補の全体を見渡せない問題である。カーナビの経路や将棋の次の一手では候補の数が組合せで増えるため、目の前の局面や経路を評価しては見込みのない枝を捨て、残った方向をさらに先まで調べる、という行き来を繰り返して答えに近づく。何を事前に計算し、いつ計算を済ませておくかは段階ごとに違うが、読む量を減らして答えへ近づくという目的は三つの段階に共通している。

経路探索では、問い合わせの前に道路網を前処理しておく方式もとられる。経路探索手法のサーベイの表では、西欧の道路網で約2.2秒かかるダイクストラ法に対し、前処理5分の Contraction Hierarchies は約110マイクロ秒で答える（実装と計測環境は手法ごとに異なる）。

この連載の第1回と第2回は一つ目の検索しやすくする段階を扱い、第1回では問い合わせの前に済ませておく仕事として、並べ替えとインデックスを取り上げる。

1. 並べ替えが支える処理

整列済みのデータでは、二分探索で位置を特定でき、同一キーが連続するので集約が一度の走査で済む。二つの集合のマージや範囲検索も順序に依存する。ランレングス圧縮や差分圧縮は隣接する値の類似性を前提とするため、並べ替えが圧縮率を直接左右する。重複値の検出、インデックスのバルク構築、分散ノード間の範囲分割も、整列していることを前提にしている。

トランプの札を見比べながら並べ替えるように、キーどうしの大小比較だけを手がかりにして並べる方法を比較ソートと呼ぶ。一回の比較で分かるのはどちらが大きいかだけなので、あり得る並び方の中から正しい一つへ絞り込むには相応の回数の比較が要り、比較ソートには一般に O(n log n) の下限がある。計数ソートや基数ソートはキーの値そのものを手がかりにするので、教科書でいう比較モデルの外で動き、キーの範囲が限られていれば線形時間で済む。年齢や状態値のような小さな整数なら、値ごとに箱を用意して各行を該当する箱へ入れ、箱を小さい順に読み出すだけで整列が終わるので計数ソートが効く。固定長のキーや GPU 上の並べ替えでは、郵便物を郵便番号の桁ごとに仕分け直していくように、桁ごとに処理する基数ソートが選ばれる。

古典的な手法も用途ごとに残っている。挿入ソートは小規模データやほぼ整列済みの入力に強く、ハイブリッドソートの末端で使われる。選択ソートは書き換え回数が少ないため、特殊な小規模データで効く場面がある。マージソートは安定で逐次読み出しに向くので外部ソートと並列処理の基礎になり、クイックソートは平均的に高速で局所性がよいので主記憶上の汎用ソートに使われる。ヒープソートは最悪計算量を保証しやすいため、メモリ制約のある環境やフォールバック先として使われる。

現代の標準ライブラリの多くは、複数のアルゴリズムを組み合わせて実装している。Python のリストソートで使われる Timsort は、入力の中ですでに整列している区間（run）を検出してマージする。CPython の listsort.txt には、部分的に整列した実データへの適応と安定性を設計目標に置いた経緯が書かれている。

実装の細部も性能を左右する。小さな区間では挿入ソートへ切り替える、偏った入力を検出してアルゴリズムを変えるといった分岐があり、比較回数とあわせて分岐予測ミスも減らす工夫が入る。キャッシュラインに合わせた分割、SIMD による複数キーの同時処理、NUMA とメモリ帯域への配慮も効く。不安定なソートで済む場面では、追加メモリを削る実装もある。理論計算量が同じ実装どうしでも、この差で実測値は大きく動く。

メモリを超える量のデータは、小分けにしてソートし、整列済みの run を多方向マージする。この外部マージソートは、DBMS、検索エンジン、ログ処理、データウェアハウスの基礎になっている。MapReduce でも、Map の出力をキーで分割・ソートして Reduce へ渡すシャッフルとソートが処理の中核にあり、ソートは分散集約のためにデータを配送する仕組みとしても働いている。

2. 保存時の物理順序による検索の最適化

ソートは一時的な処理に加えて、保存時の物理順序として検索の最適化にも使われる。

ClickHouse の MergeTree テーブルは行をソートキー順で格納する。索引は、既定で8192行ごとのグラニュールにひとつのマークを置く疎な構造をとる。検索時はマークを二分探索し、該当する可能性があるグラニュールだけを読む。位置をグラニュール単位で持つので、索引はメモリに収まる大きさに保たれる。

Apache Iceberg の仕様もテーブルにソート順を宣言でき、書き込みエンジンはその順序を使ってデータ配置を最適化できる。ただしこれは物理配置のヒントにとどまり、SQL のクエリ結果の順序を保証するのは明示的な ORDER BY だけだ。物理ソートと ORDER BY を同じものとして扱うと、開発環境でたまたま並んで見えた結果が本番で崩れる。

ソートキーを選ぶことは、将来どんな問い合わせが来るかを見込んで、先に備えておくことにあたる。物理配置は書き込み時に確定するため、その並びが枝刈りに効くのは、あくまで想定したソートキーで絞り込むクエリに限られる。

3. インデックスの役割と分類

本の巻末索引を引けば、本文を頭から読む代わりに、語が載っているページへ直接たどり着ける。データベースのインデックスも同じ働きをする仕組みで、定義としては、検索時に読み飛ばせるデータを判定し、読む量を減らすための補助構造である。

分類の軸は複数あり、本の索引にたとえると区別の意味がつかみやすい。論理的な区別の多くは、何を見出しにして引くかに関わる。行を一意に特定する主キーで引くものを主索引、それ以外の列で引くものを副索引と呼ぶ。見出しの値が行ごとに重複しない一意索引と同じ値が複数の行に現れる非一意索引、一つの列で引く単一列索引と姓と名のように複数の列を組み合わせて引く複合索引も、この見出しの選び方で分かれる。部分索引は未処理の注文のような条件に合う一部の行だけに見出しを付け、関数索引は小文字にそろえた名前のように、列に式を適用した結果を見出しにする。カバリングインデックスは必要な列を索引側にも持たせておき、索引だけで答えをそろえる。本でいえば、見出しの横に用語の要約まで書いてあるので本文を開く手間が省ける状態にあたる。本文の並びとの関係では、辞書のように本文そのものが見出しの順に並んでいるクラスタ化インデックスと、本文の並びとは別に巻末索引を作る非クラスタ化インデックスが同じ軸に並ぶ。

物理的な区別としては、全行に一つずつ見出しを持つ密な索引と、一定範囲ごとに代表の値だけを持つ疎な索引がある。辞書の各ページの上端に載っている、そのページの最初と最後の語は疎な索引の一種で、前章の ClickHouse の主索引もこの形をとる。置き場所によってメモリ常駐とディスク常駐、見出し一つが指す粒度によって行単位・ページ単位・ファイル単位にも分かれる。さらに、キーの順序を保って範囲を引ける順序付き索引と、順序を手放す代わりに一致するキーの位置へ直接飛ぶハッシュ索引、該当する行を漏れなく正確に返す厳密な索引と、多少の取りこぼしを許して速く候補を返す近似索引という軸も加わる。

どの構造を選ぶかは、データ型よりもクエリの形と選択性で決まる。

検索条件	適した構造
等価検索	ハッシュ表、ハッシュ索引
範囲、前後、ORDER BY	B木、B+木
書き込み中心	LSM-tree
不在の高速判定	ブルームフィルタ
接頭辞、バイト列	トライ木、基数木、ART
単語・文書検索	転置索引
時系列・物理順序との相関	BRIN、ゾーンマップ、min-max インデックス
地理・空間	R木、GiST、SP-GiST
高次元ベクトル	IVF、PQ、HNSW、DiskANN

4. 読み最適化と書き最適化

B木は、ディスクページのような大きなブロック単位で多数のキーを持ち、木の高さを抑える。1972年のバイヤーとマクライトの論文は、大規模な順序索引を少ない I/O で維持する構造としてこれを提示した。

実用 DB で使われる B+木系では、内部ノードに探索キーを置き、実データへの参照は葉に集める。葉どうしを連結するので範囲走査がしやすくなる一方、挿入時のページ分割と削除時の再配置が発生する。等価検索、範囲、最小・最大、前方一致、ソート済み走査のいずれにも使えるのが強みだ。

LSM-tree は反対に書き込みを優先する。最終位置への書き込みを後回しにし、更新をメモリ上に蓄積して整列済みファイルとして書き出し、後からマージする。1996年の原論文は、B木のランダムな更新 I/O を避けるために変更を遅延・バッチ化し、マージソートに似た方法で複数階層へ移動させる構造として説明している。

典型的な書き込み経路は先行書き込みログ（WAL）への追記から始まり、memtable へ書いた内容をソート済みの SSTable としてフラッシュする。読み取りは複数の SSTable にまたがって検索し、重複と削除済みデータはコンパクションで統合する。書き込みは連続した I/O になるが、その代わりに三種の増幅が生じる。一つのキーを読むために複数の SSTable を順に覗くことになるのが読み取り増幅で、コンパクションのたびに同じデータが書き直されるため、アプリケーションが書いた量より多くのデータをディスクへ書くことになるのが書き込み増幅である。統合前の古い版や削除済みの値がしばらく残るので、実データより多くの容量を使うことを空間増幅と呼ぶ。コンパクション時の I/O スパイク、トゥームストーンの蓄積、複数レベルを横断する検索も負担になる。

LSM-tree はソート済みの集合を継続的にマージするインデックスとみなせるので、ここでもソートが索引維持の中心にある。

5. 索引の維持と配置

データは更新や削除を受け、分布も変わっていくため、索引は作った後も維持し続ける必要がある。前章の B+木のページ分割や LSM-tree のコンパクションがその維持作業にあたる。読み取りを速くする代わりに、この維持の手間を引き受け続けることになる。

継続的な更新、削除の反映、スナップショットとの整合、スキーマ変更は、検索アルゴリズムの外側に課題として残る。分散配置と再構築、更新したデータが検索結果に現れるまでの遅れを表す鮮度（freshness）、可観測性、オンラインチューニングも同じ種類の課題だ。その意味で索引は、データ構造であると同時に、変わり続けるデータの上で維持されるシステムでもある。

索引の置き場所についても提案がある。Borycki の「Puffin-Backed Vector Indexes: Attaching Approximate Nearest Neighbor Indexes to Apache Iceberg Snapshots for Compute-Disaggregated Query Engines」（2026年6月）は、Apache Iceberg の Puffin sidecar ファイルへ Vamana 系の ANN 索引を格納し、snapshot summary で結び付ける設計を示した。索引の管理を Iceberg のスナップショット操作に帰着させる提案で、計算とストレージを分離したレイクハウスの中で、索引を独立したファイルとして扱う。ClickHouse Cloud は索引の解析を複数のレプリカに分散する索引のシャーディングを導入しており、索引を各ノードへ完全に複製する代わりに、ノード間で分担して扱う設計になっている。

第2回では、キーで引く構造としてハッシュ表と六種類の索引を取り上げ、安価に「ここにはない」と答える仕組みと、内容の同一性をハッシュで調べる方法へ進む。