【テクニカル・上級編】 B-treeインデックス – PostgreSQL

B-treeインデックスの深淵：なぜ我々は「とりあえずインデックス」で躓くのか

PostgreSQLを触り始めてからどれくらいの年月が経っただろうか。`CREATE INDEX`というコマンドは、まるで魔法の呪文のように、鈍重なクエリを瞬時に叩き起こしてくれる。しかし、我々エンジニアがそのインデックスの「中身」を理解せず、ただ無闇に定義するだけでは、いずれシステムの成長とともにその魔法は解け、負債となって返ってくる。

今回は、PostgreSQLのデフォルトであり、最も信頼の厚い「B-treeインデックス」について、あえて教科書的な説明は飛ばして、その内部構造とパフォーマンストラブルの勘所について語りたいと思う。

物理構造と「ページ」という単位

B-treeインデックスを理解する上で避けて通れないのが、ページ（ブロック）という概念だ。PostgreSQLのインデックスは、8KBのページ単位で管理されている。

インデックスは、ルート（Root）から始まり、ブランチ（Branch）、そしてリーフ（Leaf）へと続く階層構造を持っている。ここで重要なのは、「リーフページ同士が双方向連結リストで繋がっている」という点だ。

なぜこれが重要か？例えば、`WHERE id BETWEEN 100 AND 200`という範囲検索を想像してほしい。ルートから辿った結果、100の場所が特定できれば、あとはリーフページのリンクを順に辿るだけでいい。わざわざ毎回ルートから降り直す必要はないわけだ。この「横方向の移動」こそが、範囲検索におけるB-treeの真骨頂である。

なぜ「インデックスの肥大化」は起きるのか

多くのエンジニアが頭を抱えるのが、インデックスの肥大化（Bloat）だ。特に更新頻度が高いテーブルでは、インデックスはあっという間に荒れ果てる。

PostgreSQLのB-treeは「デッドタプル」を直接インデックスから即座に削除するわけではない。更新が発生した際、古いインデックスエントリは残ったまま、新しいエントリが追加される。これを整理してくれるのが`VACUUM`だが、負荷の兼ね合いで頻繁に走らせられない現場も多いだろう。

トラブルの兆候: インデックスのサイズが急激に肥大化し、スキャン速度が落ちている。
診断の鍵: `pgstattuple`拡張を使って、`leaf_fragmentation`（リーフの断片化率）を計測してみるといい。もしこれが極端に高ければ、インデックスの再構築（`REINDEX CONCURRENTLY`）を検討すべきタイミングだ。

「ソート」のコストを忘れていないか

よくある誤解が、「インデックスを貼れば、ORDER BYも速くなる」というものだ。これは半分正解で、半分は危険な罠だ。

B-treeは、論理的にデータがソートされた状態で格納されている。そのため、インデックスの順序とクエリのソート順が一致していれば、データベースはわざわざ追加のソート処理（`Sort`ノード）を行う必要がない。

しかし、もしあなたが`ORDER BY a DESC`と書いているのに、インデックスがデフォルトの`ASC`で作成されていたらどうなるか？ PostgreSQLはインデックスを逆方向にスキャンする（Backward Scan）ことになる。これは順方向スキャンに比べて、わずかにコストが高い。

もしそのクエリがシステム全体のボトルネックになっているなら、インデックスの定義を`CREATE INDEX … ON table (a DESC)`と変えるだけで、実行計画から`Sort`ノードが消え去り、劇的な改善が見られることがある。

パフォーマンスの秘訣：インデックスの「適材適所」

最後に、一つだけ現場の知見を共有したい。それは「インデックスは、データのカーディナリティ（値の多様性）だけでなく、アクセスパターンを考えて選べ」ということだ。

例えば、`BOOLEAN`フラグのような値の種類が少ないカラムにインデックスを貼ることは、多くの場合、アンチパターンだ。スキャンする範囲が広すぎて、結局シーケンシャルスキャンの方が速いとオプティマイザが判断してしまう。

インデックスを設計する際の「私のチェックリスト」:

カバーリングインデックス: `INCLUDE`句を使って、頻繁に参照するカラムを含めていないか？（`Index Only Scan`を狙え）
複合インデックスの順序: 最も選択性の高い（絞り込みが効く）カラムを左側に置いているか？
必要以上のインデックス: 更新処理のたびに書き込み負荷が増大する。使われていないインデックスは、`pg_stat_user_indexes`を確認して、潔く削除する勇気を持とう。

最後に：ブラックボックスにしないために

B-treeは、何十年も前に生まれた古くからある構造だが、PostgreSQLという堅牢なエンジンの中で完璧に磨き上げられている。しかし、それはあくまで道具に過ぎない。

「とりあえず貼る」のではなく、「なぜこのクエリがこのインデックスを使うのか」「今のデータ量でこのインデックスは本当に効率的か」を、`EXPLAIN (ANALYZE, BUFFERS)`の結果を眺めながら自問自答し続けてほしい。その繰り返しの先にこそ、真のデータベースエンジニアとしての直感が宿るのだと、私は信じている。

さて、今日はどのインデックスをチューニングしようか？