DBのインデックスを調べてよく出てくるのが、「本の索引のようなものです。」という例えである。
が、これだけでは全くピンとこず、幾度となく調べる手を止めてしまった。

インデックスという名前なのだから索引のようなものであるのは当たり前だろ！
インデックスを指定するとき、カラム名を指定するが、

指定したカラムが本の索引の何に当たるのか
登録するとどういう処理なのか

が全くピンと来ずに「だからインデックスってなんなんだよおおお」と何度も発狂した記憶がある。

今回、自分なりに納得の行く理解ができたのでまとめておく。

※大体はこの理解で問題はないはずだが、厳密には違う点が多々あるかもしれないことは予めご理解頂きたい。

【インデックス無し時の索引について】

まず、インデックスがなぜ早くなるのかを理解するには、インデックスがない場合の索引の仕方を理解する必要がある。

インデックスがない場合、データベースは「フルテーブルスキャン」と呼ばれる処理を行い、各レコードの対象カラムを１つずつ確認して条件に一致するかどうかをチェックする。
そのため、インデックスがないと大量のデータを扱うには非常に時間がかかってしまう。
※データ量の少なく、多くなることがない場合は、インデックスと作るより早い場合もある。

【インデックスを作成するとどうなるか】

インデックスを作成するとき、大体はカラム名を指定して作成すると思うが、その時一体何が起きているのかを理解する。

インデックスを作成すると、インデックス用の別のデータ構造（よくB-treeと呼ばれる木構造）が作成される。
このデータ構造には
指定したカラムの値と、その値がテーブルの何行目に存在するかという場所を示すポインタ
が指定したカラムでソートされた状態で保存される。

この指定した
カラムの値とその場所をしめすポインタのデータ構造がインデックス
ということになる。

本の索引は、よく頭文字順で並んでいると思うが、例えの話をすると、
「本」というテーブルに対して、「頭文字」という情報、カラムで作成したインデックスが、「索引」ページということになる。

【インデックスを作成するとなぜ早くなるのか】

これまでの２つの情報からインデックスを作成するとどのような方法で探索を行い、早くなるのかを理解する。

これまでの情報をまとめると、
　インデックスを作らないと、テーブルを１件ずつ条件（WHERE句やJOIN句）に該当するかチェックしてしまう。
　インデックスを作成すると、インデックスに指定したカラムの値とその場所を示すポインタのデータ構造を作成する。
となる。

インデックスの作成されたテーブルだと、下記流れで探索を行うようになる。
　インデックスを使用してまず指定したカラムとその値が合致するポインタを見るける。
　そのポインタが指すレコードをチェックして残りのインデックスで指定していないカラムを確認して条件に合致するかをチェックする。

例えば、

{名前、年齢、性別、都道府県、市区町村}

というカラムがあるテーブルに、

{年齢、都道府県}

と指定してインデックスを作成したテーブルがあるとする。
すると、

年齢：20歳、都道府県：大阪府のデータは、22,33,43,55行目に存在する。
年齢：20歳、都道府県：東京都のデータは、17,26,38,65行目に存在する。
年齢：25歳、都道府県：東京都のデータは、20,23,48,59行目に存在する。

というデータ構造が作成されるイメージ。

そして、そのテーブルに対して、WHERE句で {年齢：20歳、都道府県：東京都、性別：男性} を指定して索引を行った際、インデックスを利用してまず、{年齢：20歳、都道府県：東京都} に一致する行のポインタを索引する。
そして索引して出た、17,26,38,65行目のレコードに対して、 {性別：男} に該当するかを確認する。
という流れになる。
そのため、全件を1レコードずつ確認するより高速でデータを索引する事ができる。

【インデックスとは「本の索引のようなものです。」】

以上を踏まえて、

「頭文字」と言うインデックスを作成したのが本の索引で、
「頭文字」が「た」に該当するデータ群の
「ページ数(レコードのポインタ)」を見て1件ずつ確認する。

ため、インデックスとは、「本の索引のようなものである。」と例えられている。

ここまで言ってくれないと私みたいな人間は理解できませんよ。

皆様はどうでしたでしょうか？
インデックスに対する理解が少しでも掴めたなら幸いです。

完全に理解するには、きっとB-tree、木構造、二分探索あたりをしっかりと理解する必要があるかと思いますが、それは自分で調べてください（笑）。

では、またいずれ。