なぜインデックスが必要か — 目次の例え
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:#fffB+treeが強いのは3つの用途すべてを1つのデータ構造でカバーできるからです。
- 等値検索:
WHERE id = 42→ 根から葉までO(log n)で辿る - 範囲検索:
WHERE id BETWEEN 10 AND 100→ 左端に辿り着いたら葉のリンクで右へ順次走査 - ソート済み走査:
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 で回答