結局、B-treeを「使いこなす」とはどういうことか
PostgreSQLを触り始めてからどれくらいの月日が流れただろうか。最初は`CREATE INDEX`を打てば速くなる、という単純な理解で十分だったかもしれない。しかし、大規模なデータセットと向き合い、レイテンシの1ミリ秒を削り出すフェーズに差し掛かると、B-treeインデックスの「裏側」を無視することは許されなくなる。
今日は、PostgreSQLにおけるB-treeの深淵を少し覗いてみたいと思う。教科書的な「等価比較や範囲検索が得意」という話は一旦脇に置き、もう少し泥臭い、実戦的な話をしよう。
内部構造：ページと「右」への飽くなき旅
PostgreSQLのB-treeは、正確には「Lehman & Yaoのアルゴリズム」をベースにした、同時実行制御に優れた構造を持っている。ここで意識すべきは、インデックスページが常に「右方向」へリンクされているという事実だ。
インデックスの走査中、もし目的のキーが現在のページになければ、右側の兄弟ページへ移動する（`right-link`を辿る）。これのおかげで、インデックスの再構成（`VACUUM`など）中であっても、ロックの競合を最小限に抑えつつ、読み込みを継続できる。
ここでトラブルシューティングのヒントを一つ。もし、特定のテーブルでインデックスの肥大化が止まらないなら、それは「ページ分割（Page Split）」が頻発している証拠だ。特に、シーケンシャルなIDではなく、ランダムなUUIDを主キーにしている場合、ページの真ん中付近で挿入が繰り返され、インデックスの埋め込み効率がガタ落ちする。`fillfactor`を調整して余裕を持たせるか、あるいはハッシュインデックスやBRINへの移行を検討するタイミングかもしれない。
複合インデックスの「並び順」は宗教論争ではない
複合インデックスを作成する際、カラムの順序で悩んだ経験は誰にでもあるはずだ。「カーディナリティが高い順に置くべきか？」という定説は半分正解だが、半分は罠だ。
最も重要なのは、「等価比較（`=`）で使うカラムを左側に寄せる」こと。
— 悪い例：範囲検索が先頭にある
CREATE INDEX idx_bad ON orders (status_date, user_id);
— 良い例：等価比較を左に寄せる
CREATE INDEX idx_good ON orders (user_id, status_date);
なぜか。B-treeは左から順にソートされたツリーを辿る。最初のカラムが不等号（`>`や`<`）だと、その先のカラムのソート順序はインデックス内で「バラバラ」になってしまう。結果、データベースエンジンは後続のカラムをインデックスで効率的に絞り込めない。 この順序を間違えるだけで、実行計画における`Index Scan`が`Bitmap Index Scan`に格下げされ、さらに最悪の場合は`Seq Scan`まで追い込まれる。この「左寄席」の原則を叩き込んでおくだけで、パフォーマンスの安定感は段違いになる。
「見えない」コスト：インデックスが重荷になる瞬間
インデックスは強力な武器だが、同時に「書き込みの代償」を要求する。
特に、頻繁に更新されるテーブルにインデックスを張りすぎると、`Heap`の更新に合わせてインデックスも全て書き換える必要がある。これはIOPSを激しく消費する。
私が現場でよく見るアンチパターンは、「とりあえず全ての検索条件にインデックスを貼る」ことだ。特に、「Covering Index（INCLUDE句）」の使い所を間違えてはいけない。`INCLUDE`で付け加えたカラムは、インデックスのリーフページにのみ保存されるため、検索は速くなる。しかし、そのカラムが更新されるたびにインデックスの再構築が走るという事実は変わらない。
最後に：計測こそがすべて
ここまで語っておいてなんだが、結局のところ、`EXPLAIN (ANALYZE, BUFFERS)`の出力結果に勝る真実はない。
- `Index Scan`のコストは高いか？
- `Shared Read`（ディスクからの読み込み）は発生しているか？
- `Heap Fetches`が多すぎないか？
これらの指標を追い続け、インデックスが「機能しているか」ではなく「効率的に機能しているか」を問うこと。それが、エンジニアとして次のステップへ進むための唯一の道だと私は信じている。
B-treeはシンプルだが、奥が深い。皆さんもぜひ、自分の手元のクエリプランを一度じっくり眺めてみてほしい。そこには、まだ最適化の余地が眠っているはずだ。
コメント