検索パフォーマンスとインデックス〜「遅いクエリ」を救うB-Treeと左端マッチの原則〜

はじめに

記事の目的：データ量が増加した際のボトルネックを解消するため、RDBの標準機能である「B-Treeインデックス」の仕組みと、複合インデックスにおける「左端マッチの原則」を論理的に理解する。
本記事はAIを用いて調査、執筆しています。

本記事の内容

• なぜデータが増えると検索が遅くなるのか？（フルテーブルスキャン）
• RDBの標準兵器「B-Treeインデックス」の強みと弱み
• 複合インデックス最大の罠：「左端マッチの原則」
• 範囲検索（Range）が引き起こすインデックスの機能停止
• 実務での対策とまとめ

1. なぜデータが増えると検索が遅くなるのか？

開発初期、テストデータが数千件しかない頃は、どんなSQLを書いてもデータベースは一瞬で結果を返してくれます。しかし、サービスが成長し、データが数百万件、数千万件という規模に膨れ上がると、ある日突然「画面がタイムアウトして開かない」「検索ボタンを押してもずっとローディング画面のままになる」という悲鳴が上がります。

このパフォーマンス低下の最大の原因は、データベースが 「フルテーブルスキャン（全件検索）」 を行っているためです。

フルテーブルスキャンとは？

フルテーブルスキャンとは、目的のデータを見つけるために、テーブルの1行目から最後の行までを「すべて」読み込んで確認する処理のことです。

分厚い専門書の中から、特定のキーワード（例：「正規化」）が書かれているページを探す場面を想像してください。巻末にある「索引（インデックス）」を使わずに探そうとすると、1ページ目から最後のページまで、すべての文章を一行ずつ目で追って探さなければなりません。
本のページ数（データ量）が10倍になれば、探す手間と時間も10倍になります。これがフルテーブルスキャンの恐ろしさです。

データ量が少ないうちはコンピュータの処理速度の暴力でカバーできてしまいますが、データ量が膨大になると、処理時間に比例して検索が致命的に遅くなっていきます。

2. RDBの標準兵器「B-Treeインデックス」

リレーショナルデータベースにおけるインデックスにはいくつか種類（ハッシュやビットマップなど）がありますが、私たちが普段 CREATE INDEX で作成するものは、ほぼ100% 「B-Tree（ビーツリー）インデックス」 と呼ばれるものです。

「B」は Balanced（平衡）の略で、データを「木構造（ツリー状）」に整理して保持するアルゴリズムです。

なぜB-Treeは速いのか？（辞書のメタファー）

B-Treeの検索方法は、私たちが分厚い「国語辞典」を引くときの動きに似ています。
例えば「データベース」という単語を探すとき、1ページ目からめくる人はいませんよね。まず真ん中あたりを開き、「タ行」のページが出たら「ダ行はもっと後ろだな」と判断してさらに後ろの真ん中を開く……というように、「探しているデータが今の位置より前か後ろか」を判断して、検索範囲を半分、また半分と絞り込んでいきます。

この構造のおかげで、データ量が100万件になっても20回のステップ、1億件になってもたった27回のステップで目的のデータに到達できるという、驚異的なパフォーマンスを発揮します。

B-Treeの「得意なこと」と「苦手なこと」

しかし、B-Treeは万能の魔法ではありません。「並び順（ソート）」を利用して検索する構造上、得意な検索と苦手な検索がはっきりと分かれます。ここを間違えると、せっかくインデックスを作ってもデータベースは「フルテーブルスキャン」に切り替えてしまいます。

• ⭕️ 得意（インデックスが効く）：
  • 完全一致検索（=）： WHERE age = 20
  • 範囲検索（>, <, BETWEEN）： WHERE age >= 20
  • 前方一致検索（LIKE）： WHERE name LIKE '山田%'（「や」から始まるページを開けばすぐ見つかるため）
• ❌ 苦手（インデックスが効かない＝フルスキャンになる）：
  • 否定形（!=, <>）： WHERE age != 20（「20歳以外の人」はツリーのあちこちに散らばっているため、全部見るしかない）
  • 後方一致・中間一致（LIKE）： WHERE name LIKE '%太郎'（「太郎で終わる名前」は、辞書では引けませんよね）

この「得意・苦手」の感覚を掴むことが、スロークエリ改善の第一歩です。

3. 複合インデックス最大の罠：「左端マッチの原則」

実務において、インデックスは単一の列だけでなく、複数の列を組み合わせて作成することがよくあります。これを 複合インデックス（Composite Index） と呼びます。

例えば、ユーザーの「姓（last_name）」と「名（first_name）」の組み合わせでインデックスを作ったとします。

-- 姓と名の複合インデックスを作成
CREATE INDEX idx_name ON users (last_name, first_name);

この複合インデックスを使いこなす上で、絶対に守らなければならない鉄則があります。それが 「左端マッチの原則（Left-Prefix Rule）」 です。
複合インデックスは、定義した列の「左側」から順番に使わないと、まったく機能しないという残酷な性質を持っています。

電話帳（ハローページ）で考える左端マッチ

なぜ左から順番に使わないといけないのか？紙の電話帳（ハローページ）を思い浮かべてください。

電話帳は、「①姓のあいうえお順」に並んでおり、姓が同じ人の中で「②名のあいうえお順」に並んでいます（まさに複合インデックスの構造です）。
この電話帳を使って、以下の3パターンの人を探してみましょう。

• パターンA：姓が「佐藤」、名が「太郎」を探す（last_name = '佐藤' AND first_name = '太郎'）
  • 結果：一瞬で見つかる。（インデックスが100%機能する）
  • 理由：「さ」の行から「佐藤」を見つけ、その中の「た」の行を見れば確実にたどり着けます。
• パターンB：姓が「佐藤」の人を探す（last_name = '佐藤'）
  • 結果：一瞬で見つかる。（インデックスが部分的に機能する）
  • 理由：名前がわからなくても、「さ」の行を開いて「佐藤」のブロックを見つけることは簡単だからです。
• パターンC：名が「太郎」の人を探す（first_name = '太郎'）
  • 結果：絶望的（フルテーブルスキャンになる）。
  • 理由：姓が分からないと、電話帳は引けません。 全国の「鈴木太郎」や「田中太郎」を探すために、結局1ページ目から最後のページまで全員の名前を確認する羽目になります。

このように、インデックスを (A, B) の順番で作成した場合、WHERE B = '値' という「左端をすっ飛ばしたクエリ」にはインデックスが一切使われません。

開発現場で「インデックスを貼ったのにクエリが遅い！」と騒ぎになった場合、その原因の多くは 「WHERE句の条件と、インデックスの左端の列が一致していない」 という、この罠にハマっているケースです。

4. 範囲検索（Range）が引き起こすインデックスの機能停止

左端マッチの原則には、もう一つ、多くの開発者が気づかずに踏み抜いてしまう恐ろしい仕様が存在します。
それは、 「左から順番に使えていても、途中で『範囲検索（Range）』が現れると、それより右側の列に対するインデックスは無効になる」 というルールです。

範囲検索とは、>, <, >=, <=, BETWEEN, LIKE '山田%' などのように、ピンポイントな1点ではなく「幅」を持たせた検索のことです。

なぜ右側が無効になるのか？

以下の複合インデックスとクエリを例に考えてみましょう。

• 複合インデックス： (age, created_at) （年齢、登録日の順）
• クエリ： WHERE age > 20 AND created_at = '2026-01-01'
  （20歳より上で、かつ2026年1月1日に登録した人を探す）

データベースの内部（B-Tree）では、データはまず「①年齢順」に並べられ、年齢が同じ人の中で「②登録日順」に並んでいます。

age > 20 という条件によって、データベースは「21歳以上のブロック」を瞬時に見つけ出すことができます（ここまではインデックスが効いています）。
しかし問題はその後です。

21歳の人たちの中では登録日順に並んでおり、22歳の人たちの中でも登録日順に並んでいます。しかし、「21歳以上のすべての人」という大きな括りで見ると、登録日は完全にバラバラ（ソートされていない状態）になってしまっているのです。

結果として、データベースは「2026-01-01」という日付をツリー検索（辞書引き）で見つけることができず、絞り込んだ21歳以上のデータを上から下まで1件ずつチェックして探すことになります。つまり、インデックスの第二キーである created_at は完全に機能停止しています。

5. 実務での対策とまとめ

では、先ほどのクエリ（年齢が範囲指定、登録日が完全一致）を爆速にするにはどうすればよかったのでしょうか。
答えは非常にシンプルで、 「インデックスの順番を逆にする」 ことです。

• ⭕️ 正しいインデックス： (created_at, age)

created_at = '2026-01-01' で完全に一致するブロックをピンポイントで開き、そのブロックの中はすでに「年齢順」に綺麗に並んでいるため、age > 20 のデータもインデックスを使って瞬時に取り出すことができます。

複合インデックス設計のベストプラクティス

この仕組みから導き出される、モダンなWeb開発における究極のベストプラクティスは以下の通りです。

「完全一致（=）で絞り込む列を左側（第一キー）に置き、範囲検索（>, < など）を行う列を右側に配置する」

PrismaなどのORMを使用してテーブル（モデル）を定義する際も、このルールは絶対に守らなければなりません。

model Order {
  id        Int      @id @default(autoincrement())
  userId    Int
  status    String
  createdAt DateTime

  // ❌ 範囲検索(createdAt)が左にあると、右のstatusのインデックスが死ぬ
  // @@index([createdAt, status])

  // ⭕️ 完全一致(status)を左に、範囲検索(createdAt)を右に配置する
  @@index([status, createdAt])
}

まとめ

本記事では、検索パフォーマンスの命綱となる「インデックス」について解説しました。

• データ増加によるスロークエリの多くは、全件確認を行う 「フルテーブルスキャン」 が原因である。
• RDBの標準機能である 「B-Treeインデックス」 は、完全一致や範囲検索には強いが、否定形（!=）や後方一致には効かない。
• 複合インデックスには 「左端マッチの原則」 があり、左の列から順に使わないと機能しない。
• 途中で 「範囲検索」 を挟むと、それ以降の列のインデックスは機能停止する。そのため、完全一致の列を左に寄せて設計することが最重要。

開発の現場において、「とりあえず検索しそうな列を全部インデックスに入れておこう」という雑な対応は、パフォーマンスを改善しないどころか、データの更新速度（INSERT/UPDATE）だけを遅くする最悪のアンチパターンです。

「データベースがどうやってツリーを辿るのか」という裏側の論理を想像し、左端マッチの原則を完璧にコントロールして、1億件のデータでも一瞬で捌ける堅牢なデータベースを設計してください。