インデックスの仕組み

100 万行の orders から、user_id が 42 の行を探します。インデックスが無いと、データベースは 1 行目から最後まで全部読んで、42 かどうかを 100 万回確かめます。数十件を取り出すための作業としては、明らかに多すぎます。

索引の無い本から、1 語を探している

厚い技術書で「トランザクション」という語を探すとき、1 ページ目からめくる人はいません。巻末の索引を引いて、そこに載っているページだけを開きます。索引は語が五十音順に並んでいるので、目当ての語まで数秒で辿り着けます。

データベースのインデックスは、これとまったく同じものです。列の値を並べ替えた見出しの一覧を、本体とは別に持っておきます。探すときは見出しのほうを引き、見つかった場所だけ本体を読みます。全ページ読む必要が消えます。

並んでいるから、半分ずつ捨てられる

見出しが並んでいると、真ん中を 1 つ見るだけで「探している値は前半か後半か」が決まります。これを繰り返すと、確かめる回数が一気に減ります。実際のインデックスは、この絞り込みを段に分けた木の形で持っています。

上から順に「どの枝か」を選ぶだけで、いちばん下に着いたときには候補が数十行まで絞れています。1 つの節から出る枝が多いほど、少ない段数で多くの行を扱えます。枝が 100 本なら 3 段で 100 万行、4 段で 1 億行に届きます。行が 100 倍に増えても段が 1 つ増えるだけ、というのがインデックスの効きどころです。

前から順にしか辿れない

索引は語の先頭から並んでいるので、「途中に『ザクション』を含む語」は索引では探せません。インデックスも同じで、次のような書き方をすると使われません。

効いているかどうかは推測せず、EXPLAIN を頭に付けて確かめます。

type が ALL、key が NULL と出ていれば、インデックスは使われず全件読んでいます。

解説

遅いクエリを見つけたら、まず EXPLAIN です。インデックスを足す前に、既にあるインデックスを避ける書き方をしていないかを見るほうが、早く終わることが多くあります。