なぜインデックスが必要か — 目次の例え

100万行のテーブルから特定の1行を取るとき、インデックスなしなら全件走査(Sequential Scan)で1秒以上かかります。 インデックスがあれば数ミリ秒で返ります。 この差は「本の目次」と同じで、目次なしで100ページの本から「第7章」を探すのと、目次から直接ページ番号を引くのと同じ。

B-tree / B+tree — デフォルトにして最強

関係データベースで圧倒的に最も使われるのがB+treeです。 B-tree(Rudolf Bayer & Edward McCreight, 1972)の改良版で、 葉ノードに実データ(または行へのポインタ)が並び、葉が双方向リンクで繋がっているのが特徴。

flowchart TD
    Root["Root<br/>[50]"] --> L1["内部ノード<br/>[20, 35]"]
    Root --> L2["内部ノード<br/>[70, 85]"]
    L1 --> Leaf1["葉<br/>[5, 12, 18]"]
    L1 --> Leaf2["葉<br/>[22, 28, 33]"]
    L1 --> Leaf3["葉<br/>[38, 42, 48]"]
    L2 --> Leaf4["葉<br/>[55, 62, 68]"]
    L2 --> Leaf5["葉<br/>[72, 78, 82]"]
    L2 --> Leaf6["葉<br/>[88, 92, 98]"]
    Leaf1 <-.順次走査.-> Leaf2 <-.-> Leaf3 <-.-> Leaf4 <-.-> Leaf5 <-.-> Leaf6
    style Root fill:#3b82f6,color:#fff
B+tree: 高さはO(log n)。葉ノードの双方向リンクで範囲スキャンも高速

B+treeが強いのは3つの用途すべてを1つのデータ構造でカバーできるからです。

  1. 等値検索: WHERE id = 42 → 根から葉までO(log n)で辿る
  2. 範囲検索: WHERE id BETWEEN 10 AND 100 → 左端に辿り着いたら葉のリンクで右へ順次走査
  3. ソート済み走査: ORDER BY id → 葉をそのまま辿るだけ。ソート不要

B+tree以外のインデックス — PostgreSQLの場合

PostgreSQLは特に多彩なインデックス型を持ちます。用途に応じて使い分けると劇的に効きます。

種類 向いている用途 向いていない用途 代表的な例
B-tree (B+tree) 等値・範囲・ソート 全文検索・配列検索 ほぼあらゆる用途
Hash 等値のみ、超高速 範囲検索・ソート WHERE user_id = 42 (単純等値)
GiST 幾何型・全文検索・近傍検索(Generalized Search Tree) 単純等値ならB-treeに劣る PostGIS、&&演算子、pg_trgm
SP-GiST 空間分割ツリー(kd-tree, trie, quadtree) 汎用検索 IPアドレス、電話番号、多次元点
GIN 要素を多く含む列(配列, jsonb, tsvector) 頻繁な更新(遅い) tsvector全文検索、jsonb, 配列の@>
BRIN 物理順序と相関のある列、超巨大テーブル 小規模 or ランダム順テーブル 時系列データのtimestamp、ログテーブル
-- GIN: 全文検索インデックス(PostgreSQL tsvector)
CREATE INDEX idx_articles_fts ON articles
USING GIN (to_tsvector('japanese', title || ' ' || body));

SELECT * FROM articles
WHERE to_tsvector('japanese', title || ' ' || body) @@ to_tsquery('SQL');

-- BRIN: 時系列巨大テーブルで神(ログが書かれた順=timestampの順なので)
CREATE INDEX idx_logs_ts ON logs USING BRIN (created_at);
-- 物理ブロックごとにmin/maxを持つだけのごく小さなインデックス
-- 10億行でも数MBで済み、時系列範囲検索が劇的に速くなる

-- 部分インデックス(Partial Index): 条件付きで小さく保つ
CREATE INDEX idx_active_users ON users (email)
WHERE status = 'active';
-- statusがactiveなユーザーのみインデックス化 → サイズが激減

-- 関数インデックス: 式に対してインデックス
CREATE INDEX idx_users_lower_email ON users (lower(email));
SELECT * FROM users WHERE lower(email) = 'alice@example.com';

インデックスが効かないクエリ Top 7

インデックスを作っても、クエリの書き方次第で「効かない」ことがあります。 中級SQL技術者が押さえておくべきTop 7を整理します。

# パターン 原因 対策
LIKE '%foo' 前方一致でない = B-treeで辿れない pg_trgm + GIN で対応 / 逆向き列を持つ
WHERE lower(email) = ... 列に関数を適用すると使えない 関数インデックス CREATE INDEX ... ON ... (lower(email))
WHERE a = 1 OR b = 2 条件のOR(UNIONで回避可能) 各列に独立インデックス + UNIONで書き直し or BitmapOr
暗黙型変換 WHERE int_col = '42' 型不一致で列に変換がかかる 型を揃える / CAST側を変える
WHERE col IS NULL NULLはデフォルトで格納されないインデックスが多い 部分インデックス WHERE col IS NULL
WHERE col != 5 NOT条件は選択率が高くなりがち → Seq Scanが選ばれる データ分布次第。見積もりが正しいか EXPLAIN で確認
複合インデックスの左端違反 idx(a, b)WHERE b = 1だけは使えない 左端のaを条件に入れる / インデックスを追加
-- ❌ 関数適用でインデックスが効かない
CREATE INDEX idx_email ON users (email);
SELECT * FROM users WHERE LOWER(email) = 'alice@example.com';  -- Seq Scan

-- ✅ 関数インデックスに置き換える
CREATE INDEX idx_email_lower ON users (LOWER(email));
SELECT * FROM users WHERE LOWER(email) = 'alice@example.com';  -- Index Scan

-- ❌ 複合インデックス(a, b)で b だけを条件にしてもダメ
CREATE INDEX idx_ab ON t (a, b);
SELECT * FROM t WHERE b = 1;  -- Seq Scan (a が条件に無いから)

-- ✅ 左端の列を含める or (b, a) の順で作り直す
SELECT * FROM t WHERE a = 1 AND b = 2;  -- Index Scan

EXPLAIN — 実行計画を読む

「このクエリ、なぜこんなに遅いんだろう?」の答えはEXPLAINが教えてくれます。 SQL標準にはないものの、PostgreSQL/MySQL/Oracleなど主要DBすべてが類似の構文を提供しています。

DB 構文 特徴
PostgreSQL EXPLAIN / EXPLAIN ANALYZE / EXPLAIN (BUFFERS, ANALYZE) ANALYZEで実測、BUFFERSでキャッシュHit率
MySQL EXPLAIN / EXPLAIN ANALYZE (8.0.18+) 伝統的にツリー表示なし。8.0+でFORMAT=TREEが登場
Oracle EXPLAIN PLAN FOR ... ; SELECT * FROM TABLE(DBMS_XPLAN.DISPLAY) 別途DBMS_XPLANで表示
SQL Server SET SHOWPLAN_ALL ON / 実行計画の表示(Ctrl+M) SSMSでグラフィカル表示が強力
-- PostgreSQLでの典型的な読み方
EXPLAIN ANALYZE
SELECT u.name, COUNT(o.id)
FROM users u
LEFT JOIN orders o ON u.id = o.user_id
WHERE u.created_at >= '2026-01-01'
GROUP BY u.name;

-- 出力例(抜粋):
-- HashAggregate  (cost=1234.56..1456.78 rows=100 width=40)
--                (actual time=10.2..12.5 rows=98 loops=1)
--   Group Key: u.name
--   ->  Hash Left Join  (cost=...)
--                       (actual time=...)
--         Hash Cond: (o.user_id = u.id)
--         ->  Seq Scan on orders o  (...)
--         ->  Hash  (...)
--               ->  Index Scan using idx_users_created ON users u
--                     Index Cond: (created_at >= '2026-01-01')

よく見る実行計画ノード

ノード 意味 赤信号サイン
Seq Scan テーブル全件走査 大テーブルに対してインデックスが効くはずなのにSeq Scanなら要注意
Index Scan インデックスを使った検索 一般的に良い。ただし取得行数が多すぎるとIndex-only scanの方が速い
Bitmap Heap Scan インデックスで候補をビット列にして一括取得 Index ScanとSeq Scanの中間。中量ヒット時に選ばれる
Nested Loop 外側×内側の二重ループJOIN 両方大きいなら危険。内側がインデックス検索なら速い
Hash Join ハッシュ表を作ってプローブ 等結合で大テーブル同士なら理想
Merge Join ソート済み入力をマージ 両方ソート済みなら最速
Sort ソート 大量行のSortはメモリ不足→一時ファイルが危険
Hash Aggregate ハッシュ表で集約 一般的に良い

第7章のまとめ

  • インデックスはB+treeがデフォルトにして最強。等値・範囲・ソートの3用途すべてをO(log n)でカバー
  • PostgreSQLにはB-tree / Hash / GiST / SP-GiST / GIN / BRINの6種類。用途(全文検索→GIN、超巨大時系列→BRIN、幾何→GiST)で使い分ける
  • インデックスが効かない主因: LIKE %foo、関数適用、OR条件、暗黙型変換、NULL判定、複合インデックスの左端違反
  • EXPLAIN / EXPLAIN ANALYZEで実行計画を読めるのが中級SQL技術者の条件。rows(見積) vs actual rows(実測)の乖離を見れば統計情報の鮮度がわかる
  • 実行計画ノード: Seq Scan / Index Scan / Bitmap Heap Scan / Nested Loop / Hash Join / Merge Join / Sort / Aggregate。それぞれの得意不得意を体で覚えること

次章では、複数のクライアントが同時にデータを読み書きしても一貫性が保たれる理由 — トランザクションとACID、4つの分離レベル、MVCCの世界に踏み込みます。 「なぜRDBMSは信頼できるのか」の答えがここにあります。

理解度チェック

問題 0 / 50%
Q1

B+treeインデックスで「できること」として正しくないのはどれですか?

キーボード: 1〜4 で選択、Enter で回答