はじめに
RDBのインデックスは「B-treeで探索が速くなる」という説明をよく見ますが、実際にどう速くなるのか、なぜそういう構造なのかをイメージするのが難しいと感じていました。
この記事では、インデックスの前提知識として知っておくと理解が深まる「フルテーブルスキャンの動き」「テーブルのディスク上の構造」「B-treeの探索の仕組み」を順に整理します。
動く図解で確認したい方は、こちらのサイトも合わせてどうぞ
RDBインデックス図解
フルテーブルスキャンとは何をしているのか
インデックスを使わないクエリはフルテーブルスキャン（全件走査）になります。
SELECT * FROM users WHERE email = 'foo@example.com';
-- インデックスなし → 先頭行から末尾まで全行を比較
やっていることはシンプルで、テーブルの先頭から1行ずつ email カラムを比較して、一致したら返す。一致しなければ次の行へ。これを末尾まで繰り返します。
行数を n としたとき、最悪ケースは n 回の比較なので計算量は O(n)。100万行あれば最大100万回比較することになります。
件数が少ない間は気になりませんが、テーブルが大きくなるにつれてじわじわと遅くなっていくのがフルスキャンの特性です。
テーブルはディスクにどう置かれているか
インデックスの仕組みを理解するために、テーブルがどう保存されているかを押さえておくと後が楽です。
RDBはディスクとのやり取りをページ（PostgreSQLでは通常8KB）という固定サイズの単位で行います。テーブルのデータは複数のページに分散して格納されており、1ページに複数行が入っています。
テーブルファイル
├── Page 0 [row1, row2, row3, ...]
├── Page 1 [row4, row5, row6, ...]
├── Page 2 [row7, row8, row9, ...]
└── ...
各行には行ID（PostgreSQLでは CTID、MySQLでは ROWID）が付いており、「何ページ目の何番目」という位置情報になっています。
インデックスはこの行IDを持っています。インデックスで目的の値を見つけたあと、その行IDを使ってテーブル本体の該当ページだけを読みに行く、というのが基本的な流れです。
B-treeインデックスの探索
B-treeインデックスは、値をソートした平衡木で保持しています。
[50]
/ \
[25] [75]
/ \ / \
[10] [30] [60] [90]
id = 60 を探す場合、ルートノードから始めて「目的の値はこのノードより大きいか小さいか」で左右に進む分岐を繰り返し、葉ノードに到達します。葉ノードには値と行IDが記録されており、そこからテーブル本体の対象ページに直接アクセスします。
1ステップごとに探索対象が半分になるので、計算量は O(log n)。100万行でも約20ステップ程度で到達できます。
葉ノード同士は連結リストでつながっているため、範囲検索（BETWEEN、> など）も効率よくできます。葉ノードに到達したあとは隣のノードを順にたどるだけです。
B-treeが使えない・使われない場面
速いとはいえ、B-treeインデックスが効かないケースもあります。
インデックス列に関数・演算をかけている
-- ✗ インデックスが効かない
WHERE LOWER(email) = 'foo@example.com'
WHERE created_at + INTERVAL '1 day' > NOW()
-- ◯ インデックスが効く
WHERE email = 'foo@example.com'
WHERE created_at > NOW() - INTERVAL '1 day'
インデックスは元の値でソートされているので、関数をかけた結果とは対応しません。
カーディナリティが低いカラム
status カラムが 'active' か 'inactive' の2値しか取らない場合、インデックスを使っても全体の半分の行を読むことになります。オプティマイザがフルスキャンの方が速いと判断してインデックスを使わないことがあります。
LIKE の前方一致以外
-- ◯ 前方一致はインデックスが効く
WHERE name LIKE '田中%'
-- ✗ 中間・後方一致は効かない
WHERE name LIKE '%田中%'
WHERE name LIKE '%田中'
B-treeはソート順を使って探索するため、先頭が不定な検索には対応できません。
まとめ
- フルテーブルスキャンは O(n) で、行数に比例して遅くなる
- テーブルはページ単位で管理されており、インデックスは行IDを通じてページに直接アクセスする
- B-treeは O(log n) で探索でき、範囲検索にも対応している
- 関数適用・低カーディナリティ・LIKE中間一致などはインデックスが使われない場合がある
今回の記事で紹介した内容以外にも複合インデックスやカバリングインデックス、実行計画の読み方など、詳しく知りたい方は以下のサイトにまとめておりますのでご参照ください。
バグ・ご意見は X @taitech_dev まで。