データベース内の数百万件のデータから、目的のレコードを一瞬で探し出す仕掛けが「インデックス」です。この記事では、インデックスの基本的な考え方と、なぜこれほど高速に検索できるのかを図解を交えて分かりやすく解説します。

インデックスがない検索の限界

データベースにインデックスが存在しない場合、データは単に並んでいるだけの状態です。この状態から特定のデータを探すには、端から順番に1件ずつ確認していく「線形探索（リニアサーチ）」しかありません。

データが100万件あれば、最悪の場合100万回の確認が必要です。データが増えるほど検索時間が比例して伸びてしまうため、大きなWebサービスでは動作が重くなってしまいます。

木構造（B-tree）による高速検索の仕組み

そこで使われるのが、データを樹木のように分岐させて保持する「B-tree（B木）」という仕組みです。

B-treeは一番上の「ルート（根）」から順に数字を比較し、目的の値が「小さければ左の枝」「大きければ右の枝」へと分岐して進みます。

1回の比較ごとに探す範囲が大幅に絞り込まれるため、100万件のデータがあっても、わずか3〜4回の分岐を辿るだけで目的の場所に到着できます。

データベースで使われる進化形「B+tree」の特徴

実際のデータベース（MySQLやPostgreSQLなど）では、B-treeをさらに発展させた「B+tree」が使われています。

実データは最下層（リーフ）だけに配置
途中の中間ノードには検索用のキー情報だけを置き、実際のデータは一番下のノード（リーフ）だけに集約します。これにより、途中の読み込みがより軽量化されます。

横の繋がりによる範囲検索の高速化
一番下のリーフノード同士が鎖のように順番に繋がっています。そのため、「ID 20から50まで」といった範囲検索（BETWEEN検索）をする際も、最初の一件を見つけた後は横に辿るだけで一括取得できます。

データが増えても速度が落ちない「ノードの分裂」

データを新しく追加しても、ノードが一定のデータ量を超えた段階で自動的に2つに「分裂（スプリット）」し、木全体のバランスが崩れないよう保たれます。

一部の枝だけが伸びて遅くなることがないため、データがどれだけ増えても一定の高速な検索スピードが維持されます。

まとめ

データベースのインデックスが速い理由は、全件を順番に調べるのをやめ、木構造（B+tree）を使って枝分かれしながら目的地へ直行するからです。

Webアプリケーションのパフォーマンスを高めるためにも、インデックスがどのように検索を助けているのかを意識しておくと役立ちます。