またはRDBよくわかんないけど「パフォーマンス調べろ、悪かったらインデックス張るから」とか言われたある新卒への説明書き、あるいは「なんでインデックス張れば速くなるの？」に対する答え。
※ 内部的な事情とか歴史的なアレコレはガン無視してます。

意義

索引、目次、指標などなど。綴は index 。
大元は「指し示すもの」の意で、語源は「in (中) 」「dicare (宣言) 」らしい。
(目録もインデックスの一種である。某とあるのルビにもなんとなく納得がいくというもの)

ものすごく大雑把に言うと「検索を速くする」ために存在する。

検索は重労働

広範な知識を持った人間 (つまり司書さん) がやるならともかく、コンピュータが単なる文書に対して素直にやると殺人的な時間がかかる。

例えば、ある本Bの中に単語Nが存在するか見るとする。とりあえず頭から見て、1文字目からNの長さNl文字目までの文字列をBの先頭から取り出し、取り出したものとNを比較する。違ったら2文字目からNl+1文字目まで、それも違えば3文字目からNl+2文字目まで……
時間がかかるどころの騒ぎではない。

RDBは制約である

ここに「テーブル, カラム, レコード」「データ型」「関係」といった様々な制約を持ち込み、検索しやすい状況を作ったのがRDBである。
1カラムには1つのデータだけが入る。文字列なら文字列、数値なら数値。変なものは入らない。
カラムがあつまるとレコードになる。レコードがあつまるとテーブルになり、1テーブルは同一構造のレコードだけが入っていることが保証されており、そのテーブルにどんなレコードが入るかはテーブルに書いてある。
非常に検索しやすい。何がどこに入っているか整理されているからだ。

しかし、そう喜んでもいられない。実際にはとんでもない量のレコードがぶち込まれるので、結局地獄の比較作業が始まるのだ。
今度は確かに1文字ずつずらす必要はない。単に全レコードの同じ1カラムを見て比較すればいいだけ。楽なもんだ。

そう、楽。ところで、それ1億回って言われてもまだ楽だって言える？

すばやく検索する工夫

先程「様々な制約を持ち込み、検索しやすい状況を作ったのがRDB」と書いた。
この理屈に則れば、つまり制約を足せば検索を楽に……する余地が生まれる。

実際には検索する機構自体に工夫が必要だし、適切な制約でなければ意味がない。
使う側からして扱いづらくてもダメだ。それでは使われない。存在しないのと同じだ。

索引

そこで、頭のいいやつは名案を思いついた。

カラムを指定し、これの一覧表を作る。「一覧」はRDBにとって都合の良い順番に並べてあり、カラムに入っている情報たちと一緒に「これはここらへんにあるよ」とRDBにならわかる場所の情報がつけてある。
そのカラムを条件とする検索が要求された時、RDBはまずこの「一覧」を見る。なぜならこの「一覧」の順序ルールはRDB自身すでに知っているからだ。どのあたりに何があるかは簡単に見当がつく。

既に気がついているかもしれないが、これこそがインデックス。紙の辞書や技術書や教科書なんかの最後らへんについている索引と同じ発想で出来ているし、名前も同じだ。
英語ならアルファベット順、日本語のものなら50音順+アルファベット順で並んでいると我々は知っている。少なくとも「い」のあとに「あ」が来ないことぐらいは想像がつくだろう。
（このあたりの「順番がわかっているものから探す」アルゴリズムはいろいろあるが、調べたいと思ったらまず「二分探索木」がよい。まず使われないが、最もシンプルでわかりやすいだろう）

しかし、インデックスにも欠点がある。

欠点

「一覧」は一種の表 (のようなもの) である。ということはデータとして存在しなければいけない。でなければ見られないからだ。
しかし、存在するということは多少なりとも容量を使う。現在のストレージ容量・価格なら気にならないのは救いではあるが、設定をしくじると死活問題にもなりうる。

「一覧」はただの表ではない。「本物の表」に連動する表なのだ。ということは「本物の表」が更新されたら「一覧」も更新しなければならない。さもなくば「一覧」は陳腐化して使えなくなる。
こちらは大問題だ。これは「本物の表」の更新 (update) や新規データの挿入 (insert) に余計な手間がかかることにほかならない。
社内システムのようなのんびりしたものならまだしも、広く使われて大量に挿入・更新されるもの……例えばソシャゲのようなものではなかなか大変なことになる。10連ガチャを1000人が引いたら10000件になるのだ。洒落にならない。

そしてそもそも、「一覧」ですばやくなるのは「大量のデータから特定カラムを使って持ってくる」ものだけだ。
なにしろ「一覧」とは特定カラムの一覧とその「ありそうな場所」の対応表なわけであって、「対応表を見る」というワンアクションが増えている分、データ量が少ないと効果が出ない。
また、検索に「一覧」が見ているカラムが使われていなければそもそも使うことすら出来ず、変なところで抜け落ちることになりかねない。割とデリケートなのだ。

まとめ

インデックスは名前の通り、データベースという辞書の索引である。
索引なので使えないときは使えないし維持管理に手間がかかる。じゃけんちゃんと考えてはりましょうネ。
Q. どう張ればいいの？ A. よく使う (or遅い) 検索の条件になってるカラムに張ればOK。でもレコードいっぱいあるんでもなければあんまり効かないぞ。大抵詳しい人がいるので教えてもらうとよい。