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

B-treeの「当たり前」を疑え：PostgreSQLのインデックス設計で、もう一段深く潜る話

PostgreSQLを触り始めて数年、あるいは数十年。私たちは「とりあえずインデックスを貼る」という行為を、まるで呼吸をするように行っています。

`CREATE INDEX ON table (column);`

このコマンドを実行したとき、裏側で何が起きているか、そしてなぜそれが「万能」に見えて、時に私たちの足をすくうのか。今回は、PostgreSQLにおけるB-treeインデックスの深淵を覗いてみましょう。教科書的な「検索が速くなる」という説明は飛ばします。現場のエンジニアが知っておくべき、物理構造とトレードオフの話です。

—

1. B-treeの深層：なぜ「バランス」が重要なのか

PostgreSQLのB-treeは、正確には「Lehman & Yao」のアルゴリズムをベースにした、非常に洗練された実装です。

ここで意識すべきは、「木構造の高さ（Height）」です。
ページサイズ（デフォルト8KB）に対して、インデックスのキーサイズが大きすぎれば、一つのノードに格納できるエントリ数は減り、木は太く、高くなります。

何が起きるか： 木が深くなればなるほど、I/Oの回数は増えます。
現場の教訓： 文字列型のカラムに不用意に長いインデックスを貼るのがなぜ危険か、もうお分かりですね。`VARCHAR(255)`に対してB-treeを貼る際、その値が常に長い場合、インデックスの肥大化は避けられません。もし検索が「前方一致」だけで済むなら、`pg_trgm`の検討や、ハッシュ化、あるいは演算子クラスの工夫が視野に入ってきます。

2. 「Index Only Scan」の甘い罠

皆さんは、`Index Only Scan`が出た瞬間に「よし、最適化完了」とガッツポーズをしていませんか？実は、ここにも落とし穴があります。

PostgreSQLのB-treeは、インデックス内に「可視性マップ（Visibility Map）」の情報を持ちません。そのため、インデックスに一致するエントリを見つけた後も、「その行が現在本当に可視（Visible）なのか」を確認するために、ヒープ（テーブル本体）のページへアクセスしに行く必要があります。

パフォーマンストラブルの種： 更新頻度が高いテーブルで`Index Only Scan`を過信すると、期待したほど速度が出ないことがあります。これは、ヒープへのアクセスが「可視性チェック」のために発生しているからです。
対策： `VACUUM`を適切に回すことはもちろん、`INCLUDE`句を使った「カバリングインデックス」を活用しつつ、`HOT（Heap Only Tuple）`アップデートが効くようなfillfactorの調整を行っているか。ここが、素人と玄人の分かれ道です。

3. ソートと範囲検索：B-treeが「最強」である理由

B-treeが他のインデックス（HashやBRINなど）と決定的に違うのは、その「順序性」です。

等価比較（`=`）だけでなく、範囲検索（`>`, `<`, `BETWEEN`）や`ORDER BY`にこれほど強く、かつ安定しているデータ構造は他にありません。しかし、ここでも「型」の扱いに注意が必要です。例えば、`WHERE created_at > ‘2023-01-01’` と `WHERE created_at::date > ‘2023-01-01’`。
前者はインデックスをフル活用しますが、後者は式インデックス（Expression Index）がない限り、インデックスを無視してフルスキャンを始めます。

「カラムに直接インデックスを貼る」という思考停止から脱却しましょう。クエリの書き方に合わせてインデックスの定義を変えるか、インデックスに合わせてクエリを最適化するか。この双方向の視点を持てるかどうかが、大規模データセットを扱う際の生存戦略になります。

4. まとめ：インデックスは「負債」になり得る

最後に、残酷な事実をお伝えします。インデックスは「読み取りを速くするための投資」ですが、同時に「書き込みを遅くする負債」でもあります。

更新のたびにB-treeのバランスを維持するためのコスト（ページ分割など）がかかる。
インデックス自体がストレージを圧迫する。
統計情報が古くなれば、プランナを惑わせる凶器になる。

DBAとして私がいつも心がけているのは、「そのインデックス、本当に必要か？」という問いです。使われていないインデックスは、ただのゴミではありません。システム全体のパフォーマンスを静かに削り取る、悪意ある存在です。

`pg_stat_user_indexes`を定期的にチェックし、`idx_scan`が極端に少ないインデックスを切り捨てる勇気を持ってください。

—

PostgreSQLというデータベースは、非常に正直です。我々が書いたインデックスの設計を、パフォーマンスという形でそのまま返してくれます。B-treeは古臭い技術だなんて思わないでください。現代のハードウェアにおいても、正しく設計されたB-treeは、依然として最強の武器であり続けています。

皆さんのデータベースに、今日もしなやかな木々（B-tree）が健やかに育ちますように。