基礎前提知識

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

定義

フルテーブルスキャンとは、インデックスを使わずにテーブルの先頭から末尾まで順に1行ずつ読んで条件に合う行を探す方法である。件数に比例して遅くなる。

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

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

フルテーブルスキャンの動き

探す id：

読んだ行数 0 / 15

name

SQL

SELECT *
FROM users
WHERE id = 55;

状況

「スキャン開始」を押すと、先頭から順に走査していく様子が見える。検索対象が末尾の 88 や 99 のときと、先頭付近の 4 のときで比べてみるとよい。

テーブルは id でソートされていない前提。目的の行が末尾に近いほど、フルスキャンは遅くなる。

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

Q.フルスキャンとインデックスは何が違いますか？

A.フルスキャンはテーブルの先頭から最後まで全行を順に読む方式で、件数に比例して遅くなります。インデックスはあらかじめキー順に並んだ小さな構造で、目的の位置を対数時間で特定できます。

Q.インデックスを貼れば必ず速くなりますか？

A.いいえ。テーブルの多くの行に該当するようなクエリではインデックスを使ってもテーブルアクセスの繰り返しが発生し、フルスキャンの方が速い場合があります。オプティマイザは統計情報を見てどちらが有利かを判断します。