なぜインデックスが必要か（フルスキャンの限界）

そもそも「探す」というのはコンピュータにとって重い処理

テーブルに1万件、100万件、1億件のデータがあるとき、条件に合う行を見つけるのに何が起きるのかを考えたことはありますか？ インデックスを貼っていない場合、DBは先頭から1行ずつ順に全部読むという素朴な方法を取ります。 これがフルテーブルスキャン（あるいはシーケンシャルスキャン）です。

SELECT *
FROM users
WHERE id = 55;

件数が増えると線形に遅くなる

フルスキャンの計算量はO(N)（データ件数に比例）です。100万件で我慢できても、1億件になると単純計算で100倍遅くなります。 インデックスはこの問題を「対数時間」O(log N) に近い形に置き換える仕組みです。

次に読むとよいトピック

• ページと行ID — フルスキャンで「1行ずつ読む」の実態は「ページ単位で読む」こと。物理的な仕組みを一段深く理解する。
• B-treeインデックス — 最も使われる索引構造。フルスキャンとの差を体感できる。
• ハッシュインデックス — 等価検索なら究極に速い方式。