インデックス深掘り ── B-Tree・GIN・GiST・BRIN

2026/04/26

インデックス深掘り ── B-Tree・GIN・GiST・BRIN

このレイヤーの役割：「全件スキャン」を避け、必要なデータだけを効率的に見つける。インデックスの種類の選択はパフォーマンスを桁違いに変える。

インデックス種別 — B-Tree・GIN・GiST・BRIN

この章で何ができるようになるか：B-Tree 以外のインデックスタイプの内部構造と使い分けを理解し、「このクエリにはどのインデックスが最適か」を判断できるようになる。

B-Tree インデックス（デフォルト）

最も広く使われるインデックス。=, <, >, <=, >=, BETWEEN, IN, IS NULL に対応。

CREATE INDEX idx_users_age ON users(age);
-- デフォルトで B-Tree が作られる

内部構造（復習）

ルートページ:     [  50  |  100  ]
                 /     |       \
内部ページ:   [10|30] [60|80] [110|130]
              /  |  \   ...
葉ページ:  [1→3→5→8→10] → [12→15→18→25→30] → ...
           各エントリが TID（テーブルの物理位置）を持つ
           葉ページ同士がリンクリストで接続（範囲スキャン用）

複合インデックス

CREATE INDEX idx_users_country_age ON users(country, age);

ソート順: (country, age) の辞書順
  ('JP', 20), ('JP', 25), ('JP', 30), ('US', 18), ('US', 22), ...

使える:
  WHERE country = 'JP'                  ✅ 左端のカラム
  WHERE country = 'JP' AND age > 25     ✅ 両カラム
  WHERE country = 'JP' AND age = 25     ✅ 完全一致

使えない:
  WHERE age > 25                        ❌ 左端を飛ばしている
  WHERE age > 25 AND country = 'JP'     ✅ （プランナーが順序を入れ替える）

左端一致原則：複合インデックスは「左端のカラムから順に」使われる。

カバリングインデックス（INCLUDE）

-- PostgreSQL 11+
CREATE INDEX idx_users_email_include ON users(email) INCLUDE (name, age);
-- email で検索し、name と age も返す → Index Only Scan が可能
-- INCLUDE カラムはソートには使われない（検索条件には使えない）

GIN（Generalized Inverted Index）

全文検索と配列/JSONB の検索に使う転置インデックス。

-- 全文検索用
CREATE INDEX idx_articles_fts ON articles USING GIN(to_tsvector('japanese', body));

SELECT * FROM articles
WHERE to_tsvector('japanese', body) @@ to_tsquery('japanese', 'PostgreSQL & インデックス');

-- JSONB 検索用
CREATE INDEX idx_events_data ON events USING GIN(data);

SELECT * FROM events WHERE data @> '{"type": "purchase"}';

-- 配列検索用
CREATE INDEX idx_posts_tags ON posts USING GIN(tags);

SELECT * FROM posts WHERE tags @> ARRAY['PostgreSQL', 'performance'];

GIN の内部構造

通常の B-Tree（正引き）:
  row_id → 値

GIN（転置インデックス・逆引き）:
  値 → [row_id1, row_id2, row_id3, ...]

例（全文検索）:
  "PostgreSQL" → [doc_1, doc_5, doc_12, doc_45]
  "インデックス" → [doc_1, doc_3, doc_12]
  "パフォーマンス" → [doc_5, doc_7, doc_45]

検索 "PostgreSQL & インデックス":
  [doc_1, doc_5, doc_12, doc_45] ∩ [doc_1, doc_3, doc_12]
  = [doc_1, doc_12]

Pending List：GIN の更新は重い（転置リストの再構築）。PostgreSQL は更新を一時的に Pending List に貯め、バックグラウンドでマージする（fastupdate オプション）。

GiST（Generalized Search Tree）

地理空間データと範囲型の検索に使う。空間インデックスの汎用フレームワーク。

-- PostGIS での地理空間インデックス
CREATE INDEX idx_locations_geom ON locations USING GiST(geom);

SELECT * FROM locations
WHERE ST_DWithin(geom, ST_MakePoint(139.7671, 35.6812)::geography, 1000);
-- → 東京駅から1km以内の地点を検索

-- 範囲型（IP範囲、日付範囲）
CREATE TABLE reservations (
    id SERIAL PRIMARY KEY,
    room_id INT,
    period TSRANGE  -- タイムスタンプ範囲
);

CREATE INDEX idx_reservations_period ON reservations USING GiST(period);

SELECT * FROM reservations
WHERE period && tsrange('2026-04-01', '2026-04-07');
-- → 4/1〜4/7 と重なる予約を検索（&& は「重なる」演算子）

GiST vs B-Tree

B-Tree: 1次元のソート可能なデータに最適
  → 数値、文字列、日付の等価・範囲検索

GiST: 多次元・包含・重なりなど複雑な関係に対応
  → 地理空間（2D）、範囲型の重なり、最近傍検索
  → ただし B-Tree より一般に遅い

BRIN（Block Range Index）

物理的に順序付けられた大きなテーブル向けの非常にコンパクトなインデックス。

-- 時系列データ（created_at が物理的な挿入順と一致する場合）
CREATE INDEX idx_logs_created ON logs USING BRIN(created_at);
-- 10億行のテーブルでも数MBのインデックスで済む

BRIN の仕組み

テーブルを「ブロック範囲」(デフォルト128ページ)ごとに要約する

ページ 1-128:    min=2026-01-01, max=2026-01-05
ページ 129-256:  min=2026-01-05, max=2026-01-10
ページ 257-384:  min=2026-01-10, max=2026-01-15
...

WHERE created_at = '2026-01-07':
  ページ 1-128: min=01-01, max=01-05 → 含まれない → スキップ
  ページ 129-256: min=01-05, max=01-10 → 含まれる可能性 → スキャン
  ページ 257-384: min=01-10, max=01-15 → 含まれない → スキップ

BRIN の条件：データが物理的な順序と論理的な順序が一致している必要がある（correlation が 1.0 に近い）。ランダムに INSERT されたテーブルでは BRIN は効果がない。

-- correlation の確認
SELECT attname, correlation
FROM pg_stats
WHERE tablename = 'logs' AND attname = 'created_at';
-- correlation ≈ 1.0 なら BRIN が効果的

部分インデックス（Partial Index）

テーブルの一部の行だけにインデックスを作る。

-- アクティブなユーザーだけにインデックス（全体の10%とする）
CREATE INDEX idx_active_users ON users(email) WHERE status = 'active';
-- → インデックスサイズが 1/10 に
-- → INSERT/UPDATE のオーバーヘッドも軽減

式インデックス（Expression Index）

-- 大文字小文字を無視した検索
CREATE INDEX idx_users_lower_email ON users(LOWER(email));

SELECT * FROM users WHERE LOWER(email) = '[email protected]';
-- → Index Scan を使える

-- 日付から年を抽出して検索
CREATE INDEX idx_orders_year ON orders(EXTRACT(YEAR FROM created_at));

SELECT * FROM orders WHERE EXTRACT(YEAR FROM created_at) = 2026;

インデックス選択のフローチャート

Q: 等価検索（=）or 範囲検索（<, >）?
  → B-Tree（デフォルト・最も汎用的）

Q: 全文検索（テキスト内の単語検索）?
  → GIN + tsvector

Q: JSONB の包含検索（@>）?
  → GIN

Q: 配列の包含検索（@>）?
  → GIN

Q: 地理空間（2D 近傍・範囲）?
  → GiST + PostGIS

Q: 範囲型の重なり（&&）?
  → GiST

Q: 時系列データの範囲検索（物理順序 = 論理順序）?
  → BRIN（省メモリ）

Q: 特定条件の行だけ検索が多い?
  → 部分インデックス

まとめ

インデックス	対応する操作	サイズ	使用例
B-Tree	=, <, >, BETWEEN, ORDER BY	中	主キー、外部キー、一般的な検索
GIN	@@, @>, ?, ?&	大	全文検索、JSONB、配列
GiST	&&, @>, <@, <->	中	PostGIS、範囲型、最近傍
BRIN	=, <, >	極小	時系列データ（物理順序＝論理順序）
Hash	= のみ	小	等価検索のみ（PostgreSQL 10+で WAL 対応）