データベースを扱っていると必ず出てくる「インデックス」という概念。よく「検索を高速化する」と聞くけど、具体的にどんな仕組みで速くなるのかピンとこない人も多いんじゃないでしょうか？
この記事では、1,000,000件のレコードから特定のIDを検索する場合を例に、「インデックスがある場合」と「ない場合」の違いを具体的に解説します。
1. 前提条件
- テーブルサイズ: 1,000,000件のレコード
-
検索条件:
id = 5421のデータを探す
2. インデックスがない場合
まず、インデックスがない場合の検索動作を考えてみます。
動作イメージ
データベースはすべてのレコードを1行ずつチェックして、条件に一致するデータを探します。SQLクエリにすると次のようになります：
SELECT * FROM documents WHERE id = 5421;
しかし、インデックスがない場合、このクエリは実質「全件スキャン」になります。
アルゴリズム: 線形探索（O(n))
全件スキャンでは、最悪の場合すべての行を確認しなければならないため、データが増えれば増えるほど処理時間も増加します。
-
処理フロー（最悪のケース）:
- レコードID=1をチェック → 不一致
- レコードID=2をチェック → 不一致
- ・・・
- レコードID=5421をチェック → 一致！
- 処理終了（最大1,000,000件確認）
3. インデックスがある場合
インデックスを設定するとどうなるでしょうか？
インデックスの仕組み
インデックスはデータベースが検索を効率化するために用意する「データ構造」です。多くの場合、B-Tree（バランス木）というアルゴリズムが使用されます。
-
B-Treeの特徴:
- 階層構造でデータを整理。
- 各ノードに「範囲情報」を持たせて、効率的に絞り込み。
- データをソートして管理。
B-Treeを使った検索の動作
インデックスが有効な場合、以下のような階層的な探索が行われます。
例: id = 5421 を探す場合
- ルートノード：範囲
1〜500,000と500,001〜1,000,000→ 範囲1〜500,000へ進む。 - 次のノード：範囲
1〜250,000と250,001〜500,000→ 範囲1〜250,000へ進む。 - さらに分割：範囲
1〜125,000→1〜62,500→1〜31,250→1〜15,625→1〜7,812→ 範囲1〜5,421。 - リーフノードに到達してデータを取得。
アルゴリズム: 二分探索（O(log n))
インデックスを使用すると、探索対象を毎回半分に絞るため、非常に高速です。
-
探索回数の例（1,000,000件の場合）:
- 最大20回の比較で目的のデータに到達（
log2(1,000,000) ≈ 20）。
- 最大20回の比較で目的のデータに到達（
4. インデックス有無の比較
| 特性 | インデックスなし（全件スキャン） | インデックスあり（B-Tree） |
|---|---|---|
| アルゴリズム | 線形探索（O(n)） | 二分探索（O(log n)） |
| 比較回数（1,000,000件） | 最大1,000,000回 | 最大20回 |
| データ増加の影響 | 増えるほど遅くなる | 増えても比較的高速 |
5. 注意点
インデックスにはメリットだけでなく、以下のようなデメリットもあります：
5.1 デメリット
-
ストレージ消費:
- インデックス自体が追加のストレージを使用します。
-
データ変更時のコスト:
- データの挿入、更新、削除時にインデックスも更新されるため、パフォーマンスに影響します。
-
インデックス設計が重要:
- 不必要に多くのインデックスを作成すると、更新処理が遅くなる可能性があります。
6. インデックスを適切に設計するには？
6.1 必要なカラムに絞る
検索頻度の高いカラム（例: idやuser_id）にインデックスを設定する。
6.2 複合インデックス
複数のカラムを同時に検索する場合、複合インデックスが有効です。
例: user_id と id
add_index :documents, [:user_id, :id]
7. 結論
インデックスを使用すると、特に大規模データでの検索パフォーマンスが大幅に向上します！
-
1,000,000件の中から特定のIDを探す場合:
- インデックスなし → 最大1,000,000回チェック
- インデックスあり → 最大20回チェック
適切なインデックス設計で、アプリケーションのパフォーマンスを劇的に改善できるので、ぜひ活用してみてください。