Day6 前半のゴール
「“インデックス＝本の索引”を超えて、“中で何が起きているか”をざっくり掴む」
今日は PostgreSQL のインデックス、その中でも標準の B-tree インデックスと、そのざっくりした内部動作を扱います。
SQLite や MySQL でもインデックスは出てきましたが、「速くなるらしい」以上のイメージは持ちにくかったと思います。
今日の前半のゴールはこうです。
インデックスを「本の索引」レベルではなく、「ソート済みの木構造」としてイメージできる。
B-tree が「範囲検索」「=検索」に強い理由を、感覚レベルで説明できる。
テーブルフルスキャンとインデックス利用の違いを、ストーリーとして語れる。
ここではまだ数式や難しい木構造の理論には踏み込まず、「頭の中のアニメーション」を作ることに集中します。
そもそもインデックスとは何か
「“全部めくる”か、“索引から飛ぶ”かの違い」
まずは、超ざっくりしたところから。
テーブルにインデックスがない状態で、次のようなクエリを投げたとします。
SELECT * FROM users WHERE email = 'a@example.com';
PostgreSQLはどうするか。
インデックスがなければ、「usersテーブルを先頭から最後まで全部なめて、email が一致する行を探す」ことになります。
これが、いわゆる「フルスキャン」です。
本で言えば、「目的の単語を探すために、1ページ目から最後のページまで全部読む」状態です。
データが少ないうちはそれでもいいですが、100万行・1000万行となると、さすがにしんどい。
そこで登場するのがインデックスです。
インデックスは、「特定のカラムについて、探しやすいように別で作っておく“検索用の構造”」です。
本で言えば、「巻末の索引」です。
索引があれば、いきなり目的のページにジャンプできます。
PostgreSQLの標準インデックスは、この索引を「B-tree」という木構造で実現しています。
B-treeインデックスのざっくりしたイメージ
「ソート済みの“分岐する道”をたどっていく」
B-tree を一言で言うと、「ソートされたデータを、木構造で効率よく探せるようにしたもの」です。
ここでは、細かいアルゴリズムの話は置いておいて、「どういうイメージで動いているか」だけ掴みます。
例えば、users テーブルに email カラムがあり、そこにインデックスを張るとします。
CREATE INDEX idx_users_email ON users(email);
この瞬間、PostgreSQLの中には「email の値をキーにしたB-treeインデックス」が作られます。
イメージとしては、こんな感じです。
email の値がソートされた状態で並んでいる。
そのソートされた並びを、木構造（分岐する道）として管理している。
検索するときは、その木をたどって、目的の値の近くまで一気にジャンプする。
本の索引との違いは、「ただの一覧」ではなく、「分岐しながら絞り込んでいける構造」になっていることです。
B-treeが速い理由を“20の質問ゲーム”で考える
「1個ずつ聞くか、“半分に分ける質問”をするか」
B-treeの強さを、よくある「20の質問ゲーム」にたとえてみます。
1〜1000の中から、あなたが1つ数字を思い浮かべる。
相手は「はい／いいえ」で答えられる質問だけで、その数字を当てる。
このとき、「1ですか？」「2ですか？」「3ですか？」と順番に聞いていったら、最悪1000回かかります。
これが「フルスキャン」です。
賢い人はこう聞きます。
「その数字は500以上ですか？」
「その数字は750以上ですか？」
「その数字は625以上ですか？」
毎回「範囲を半分に切る」質問をしていけば、10回も質問すればほぼ確実に当てられます。
これが、B-treeの世界観です。
B-treeインデックスは、「ソートされたキーの空間」を、木構造で分割しています。
検索するときは、「左の枝か右の枝か」を選びながら、どんどん範囲を狭めていきます。
だから、データが100万行あっても、「1行ずつ見る」のではなく、「何十ステップかで目的の場所にたどり着ける」わけです。
B-treeインデックスが得意な検索
「= と範囲（<, >, BETWEEN）がとにかく強い」
B-treeインデックスは、「ソートされた順番」を前提にしているので、
次のような検索が特に得意です。
SELECT * FROM users WHERE email = 'a@example.com';
SELECT * FROM users WHERE age >= 20 AND age < 30;
SELECT * FROM orders WHERE created_at BETWEEN '2024-01-01' AND '2024-01-31';
email の「ちょうど一致」
age の「20〜29歳」
created_at の「ある期間」
こういう「=」や「範囲条件」は、B-treeの得意技です。
木構造をたどって、「その値（またはその範囲）の先頭の位置」まで一気に飛び、
そこから必要な範囲だけをなめればいいからです。
逆に、「LIKE ‘%abc'” のような“前方があいまいな検索”は苦手です。
（これは後半や別の日に扱いますが、「ソート順を活かせない」からです。）
ここでの重要ポイントは、「B-treeインデックスは“ソートされたキーに対する=と範囲検索”に強い」という一文を、口に出して言えるようになることです。
インデックスを使うときと使わないとき
「少ない行ならフルスキャンの方が速いこともある」
もう1つ、現実的な話をしておきます。
「インデックスがあればいつでも速い」わけではありません。
例えば、users テーブルに100行しか入っていないとします。
このとき、次のクエリを考えます。
SELECT * FROM users WHERE age >= 0;
全員が条件にマッチするようなクエリです。
PostgreSQLは、こういうとき「インデックスを使わずにフルスキャンした方が速い」と判断することがあります。
理由はシンプルで、「どうせほぼ全部読むなら、インデックスを経由するコストが無駄だから」です。
インデックスを使うには、「インデックスをたどる → 見つけた行の場所からテーブル本体を読む」という2段階が必要です。
全件読むなら、「最初からテーブルを順番に読んだ方が安い」ことが多い。
PostgreSQLには「クエリプランナ」という頭脳がいて、
「このクエリならインデックスを使うべきか、フルスキャンすべきか」を毎回判断しています。
ここでのポイントは、「インデックスは“使わせるもの”ではなく、“使うかどうかをDBが決めるもの”」という感覚です。
我々がやるのは、「使えるようにインデックスを用意しておく」ことまで。
実際に使うかどうかは、PostgreSQLが賢く選びます。
PostgreSQLとSQLite / MySQLのインデックス感覚の違い
「“とりあえず張る”から、“用途を意識して張る”へ」
SQLite や MySQL でも B-tree ベースのインデックスは使われていますが、
PostgreSQLは特に「インデックスの種類」「プランナの賢さ」が強いDBです。
その分、「とりあえずインデックスを増やせば速くなる」という発想は危険になります。
インデックスは「読み取りを速くする代わりに、書き込み（INSERT/UPDATE/DELETE）にコストがかかる」存在だからです。
Day6 前半ではまだそこまで踏み込みませんが、
「インデックスは魔法ではなく、“ソートされた木構造を1個余分に持つこと”」
「だから、速くなるクエリと、そうでもないクエリがある」
という感覚だけ持っておいてください。
Day6 前半のまとめ
インデックスがないとき、WHERE email = 'a@example.com' のような検索はテーブルを先頭から最後まで「全部なめる」フルスキャンになるのに対し、PostgreSQLで CREATE INDEX ... ON users(email); とB-treeインデックスを張ると、「ソートされたキーを木構造で管理し、“20の質問”のように範囲をどんどん半分に絞り込んで目的の値の位置にジャンプする」動きになるため、大量データでも = や BETWEEN などの範囲検索が一気に速くなる。
B-treeインデックスは「ソート順を前提にした木構造」なので、age >= 20 AND age < 30 や created_at BETWEEN ... のような条件に強く、一方で「どうせほぼ全件読むクエリ」では、インデックス経由よりフルスキャンの方が速いとPostgreSQLが判断することもあり、「インデックスは“用意しておき、使うかどうかはDBが決めるもの”」という視点で捉えるのが Day6 前半の着地点になる。