PostgreSQL インデックスの内部構造を徹底解説：B-tree、GiST、GIN の仕組みと使い分け

はじめに

この記事では、PostgreSQLのインデックスの内部実装を深掘りします。

前回の記事（InnoDB B+Tree の内部構造を徹底解説）ではMySQLのB+Treeを解説しました。PostgreSQLはInnoDBと違い、複数のインデックスタイプを提供しています。PostgreSQL 17のソースコードを参照しながら、以下を解説します：

• HeapとIndexの分離構造（InnoDBのClustered Indexとの違い）
• B-treeの内部構造（Lehman-Yaoアルゴリズム）
• GiSTインデックス（空間データ等の汎用検索木）
• GINインデックス（全文検索・配列検索用の転置インデックス）

HeapとIndexの分離

InnoDBではテーブル自体がClustered Index（B+Tree）でした。PostgreSQLは根本的に異なります。

Heap：順序なしのデータ格納

PostgreSQLのテーブルはHeapと呼ばれる構造で、レコードは挿入された順に格納されます。B+Treeのようなキー順の並びはありません。

Heap（テーブル）:
  Page 0: [row5, row1, row8]    ← 挿入順。キー順ではない
  Page 1: [row3, row12, row2]
  Page 2: [row10, row7, row4]

各レコードの物理位置はctid（タプルID）で表されます：

ctid = (page_number, offset_within_page)
例:    (0, 1) = Page 0の1番目のスロット

Indexはctidを指す

PostgreSQLのインデックスのリーフには、ctidが格納されます。InnoDBのSecondary IndexがPK値を格納するのとは対照的です。

InnoDB Secondary Index:
  リーフ: [key=Alice, PK=1] → Clustered Indexを検索（B+Tree走査）

PostgreSQL Index:
  リーフ: [key=Alice, ctid=(0,1)] → Heapに直接アクセス（1回のI/O）

PostgreSQLのctidアクセスは高速ですが、UPDATEで行が新しいページに移動するとctidが変わり、全インデックスの更新が必要になります。これがPostgreSQLでVACUUMが重要な理由の1つです。

HOT（Heap Only Tuple）

この問題を緩和するのがHOTです。インデックスカラムが変更されないUPDATEでは、同じページ内に新バージョンを作り、旧バージョンからポインタで繋ぎます。インデックスの更新が不要になります。

UPDATE前: Page 0, slot 1: [Alice, age=25]
UPDATE後: Page 0, slot 1: [Alice, age=25] → slot 4: [Alice, age=26]  (HOT chain)
          ↑ インデックスのctid (0,1) はそのまま

B-tree

PostgreSQLのB-treeはInnoDBのB+Treeと似ていますが、重要な違いがあります。

Lehman-Yaoアルゴリズム

PostgreSQLのB-treeはLehman-Yao（L&Y）アルゴリズムを採用しています。各ページに右リンク（right-link）を持ち、ページ分割中でも検索を安全に続行できる設計です。

通常のB+Tree:
  親 [10 | 20]
     /    |    \
  [≤10] [11-20] [21-]

Lehman-Yao B-tree:
  親 [10 | 20]
     /    |    \
  [≤10]→[11-20]→[21-]→NULL
         ↑ 各ページが右隣へのリンクを持つ

なぜこれが重要かというと、ページ分割中のロック範囲を最小化できるからです：

InnoDBの分割:
  1. SX-latchでツリー全体をロック
  2. 分割実行
  3. ロック解放

PostgreSQLの分割（L&Y）:
  1. 分割するページだけをロック
  2. 新ページを作成し、右リンクで接続
  3. 親ページをロックしてポインタ追加
  → ツリー全体のロックが不要

検索中にページ分割に遭遇した場合、右リンクをたどれば正しいページに到達できます。

ページ構造

• PageHeaderData ページ管理情報
• BTPageOpaqueData B-tree固有情報
• ├─ btpo_prev (左ページ)
• ├─ btpo_next (右ページ = right-link)
• ├─ btpo_level (木の高さ)
• └─ btpo_flags (リーフ/内部/削除済み)
• Line Pointers (ItemId配列) 各タプルへのオフセット
• Free Space
• Index Tuples キー + ctid

InnoDBとの違い： – InnoDBはレコードをリンクリストで繋ぐが、PostgreSQLはLine Pointer（ItemId）配列でオフセット管理 – InnoDBにはPage Directory（二分探索用スロット）があるが、PostgreSQLのB-treeはBinary Search on Line Pointersで直接二分探索

Deduplication（PostgreSQL 13〜）

同じキー値が複数ある場合、キーを1つにまとめてctidのリストを持つ最適化です：

従来:     [Alice, ctid(0,1)] [Alice, ctid(1,3)] [Alice, ctid(2,5)]
Dedup後:  [Alice, {ctid(0,1), ctid(1,3), ctid(2,5)}]

インデックスサイズが大幅に削減されます。

GiST（Generalized Search Tree）

B-treeは等値検索と範囲検索に強いですが、「この点から半径1km以内」のような空間検索には向きません。そこで登場するのがGiSTです。

GiSTとは

GiSTは「汎用検索木」のフレームワークです。B-treeのようにキーの大小で分岐するのではなく、データ型ごとに定義された「一致」「包含」「重なり」などの演算子で分岐します。

-- 空間検索（PostGIS）
CREATE INDEX idx_geom ON places USING gist(geom);
SELECT * FROM places WHERE geom && ST_MakeEnvelope(139.7, 35.6, 139.8, 35.7);

-- 範囲型の検索
CREATE INDEX idx_period ON events USING gist(period);
SELECT * FROM events WHERE period @> '2026-04-01'::date;

-- 全文検索（tsvector）
CREATE INDEX idx_fts ON docs USING gist(tsv);
SELECT * FROM docs WHERE tsv @@ to_tsquery('database & index');

内部構造

GiSTはバランス木で、各内部ノードがバウンディングボックス（境界領域）を持ちます：

空間インデックスの例:

Root: [日本全体の矩形]
       /              \
  [関東の矩形]      [関西の矩形]
   /      \           /      \
[東京]  [神奈川]   [大阪]   [京都]
  ↓       ↓         ↓       ↓
ctid群   ctid群    ctid群   ctid群

検索時は、クエリの領域と各ノードのバウンディングボックスの重なりを判定し、重なるブランチだけを探索します。

B-treeとの使い分け

GIN（Generalized Inverted Index）

GINとは

GINは転置インデックスです。1つの行が複数の値を持つ場合（配列、全文検索、JSONB）に威力を発揮します。

-- 全文検索
CREATE INDEX idx_fts ON docs USING gin(to_tsvector('english', body));
SELECT * FROM docs WHERE to_tsvector('english', body) @@ to_tsquery('postgresql & index');

-- JSONB
CREATE INDEX idx_json ON products USING gin(attributes);
SELECT * FROM products WHERE attributes @> '{"color": "red"}';

-- 配列
CREATE INDEX idx_tags ON articles USING gin(tags);
SELECT * FROM articles WHERE tags @> ARRAY['database', 'postgresql'];

内部構造

GINは「キー → 行のリスト」という転置構造です：

GINの構造:

Entry Tree（B-tree）:
  [apple] → Posting List: [ctid(0,1), ctid(2,3), ctid(5,1)]
  [banana] → Posting List: [ctid(1,2), ctid(3,4)]
  [cherry] → Posting Tree: (大量のctidはB-treeで管理)

• Entry Tree：キー（単語など）をB-treeで管理
• Posting List：少数のctidはリストで保持
• Posting Tree：大量のctidは別のB-treeで管理

GiSTとGINの使い分け（全文検索の場合）

GINの更新が遅い問題はPending List（fastupdateオプション）で緩和されます。新しいエントリを一時的にリストに溜めておき、まとめてインデックスに反映します。

PostgreSQLのインデックスタイプ一覧

InnoDBがB+Tree一本なのに対し、PostgreSQLはデータの特性に応じたインデックスを選べる柔軟性があります。

まとめ

次回はOracle Indexを同じ切り口で解説します。

参考文献

• PostgreSQL Documentation: Indexes
• PostgreSQL Documentation: GiST Indexes
• PostgreSQL Documentation: GIN Indexes
• PostgreSQL Source Code: src/backend/access/nbtree/README
• Lehman & Yao: Efficient Locking for Concurrent Operations on B-Trees (1981)