データベースを扱っていると必ず出てくる「インデックス」という概念。よく「検索を高速化する」と聞くけど、具体的にどんな仕組みで速くなるのかピンとこない人も多いんじゃないでしょうか？

この記事では、1,000,000件のレコードから特定のIDを検索する場合を例に、「インデックスがある場合」と「ない場合」の違いを具体的に解説します。

1. 前提条件

2. インデックスがない場合

まず、インデックスがない場合の検索動作を考えてみます。

データベースはすべてのレコードを1行ずつチェックして、条件に一致するデータを探します。SQLクエリにすると次のようになります：

SELECT * FROM documents WHERE id = 5421;

しかし、インデックスがない場合、このクエリは実質「全件スキャン」になります。

全件スキャンでは、最悪の場合すべての行を確認しなければならないため、データが増えれば増えるほど処理時間も増加します。

処理フロー（最悪のケース）:
1. レコードID=1をチェック → 不一致
2. レコードID=2をチェック → 不一致
3. ・・・
4. レコードID=5421をチェック → 一致！
5. 処理終了（最大1,000,000件確認）

インデックスを設定するとどうなるでしょうか？

インデックスはデータベースが検索を効率化するために用意する「データ構造」です。多くの場合、B-Tree（バランス木）というアルゴリズムが使用されます。

インデックスが有効な場合、以下のような階層的な探索が行われます。

ルートノード：範囲 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。
リーフノードに到達してデータを取得。

インデックスを使用すると、探索対象を毎回半分に絞るため、非常に高速です。

インデックスにはメリットだけでなく、以下のようなデメリットもあります：

検索頻度の高いカラム（例: idやuser_id）にインデックスを設定する。

複数のカラムを同時に検索する場合、複合インデックスが有効です。

add_index :documents, [:user_id, :id]

インデックスを使用すると、特に大規模データでの検索パフォーマンスが大幅に向上します！

1,000,000件の中から特定のIDを探す場合:
- インデックスなし → 最大1,000,000回チェック
- インデックスあり → 最大20回チェック

適切なインデックス設計で、アプリケーションのパフォーマンスを劇的に改善できるので、ぜひ活用してみてください。