インデックス（索引）

📌

インデックスとは

インデックス（索引）とは、列の値（検索キー）と、その行が置かれている格納位置を対応づけて、検索を高速化する仕組みのことです。データ本体とは別に、検索用の小さな案内表を用意するイメージです。

身近な例で考えると、分厚い本の巻末にある索引（さくいん）とまったく同じ仕組みです。調べたい言葉が本文のどこにあるか、最初のページから順に探すのは大変ですが、索引を見れば「その言葉は123ページ」とすぐ分かります。インデックスは、この「言葉→ページ番号」の対応を、データベースの「検索キー→格納位置」として持っているわけです。

上のツールで▶ボタンを押すと、索引がない場合（フルスキャン）と、索引を使う場合とで、目的の行にたどり着く手間がどれだけ違うかを見比べられます。

⚡

高速化の仕組み

インデックスがないと、データベースは目的の行を見つけるために先頭から1件ずつ全部の行を調べるしかありません。これをフルスキャン（全表走査）と呼びます。100万件あれば最悪100万回近く調べることになります。

インデックスが速い理由は、次の2点にあります。
・キー順に整列している：索引は検索キーの順に並んでいるので、目的の値を二分探索（＝半分ずつ範囲を絞る探し方）などで少ない回数で見つけられる
・格納位置を直接指す：見つけたエントリには「行の格納位置」が書いてあるので、本体のその位置へ一気にジャンプできる

つまり、全部を順に見る代わりに、整列した索引で当たりをつけて目的地へ直行するのがインデックスの高速化の正体です。多くのデータベースでは、この索引を木構造（B-tree）で持つことで、データが増えても探す回数の伸びをとても小さく抑えています。

⚖️

メリットとデメリット

インデックスは検索を速くする便利な仕組みですが、万能ではなく代償もあります。良い面と注意点をセットで理解しておくことが大切です。

本の索引を作るのに手間とページがかかり、本文を書き直すたびに索引も直す必要があるのと同じです。そのため、検索でよく条件に使う列にだけインデックスを作り、更新が頻繁な列には作りすぎないのが上手な使い方です。何でもかんでも索引を付ければ速くなる、というわけではない点に注意しましょう。

🌲

なぜ木構造だと速いのか

実際のデータベースでは、インデックスを木（ツリー）の形で持っています。もっともよく使われるのがB木（B-tree）という構造です（Bはバランスの略と思えばOK）。

木構造が速い理由は「比べるたびに半分ずつ候補が減る」からです。上の図を例にすると、
・ルート（根）：まずここのキーと比べる（例：E05）
・目的の値がそれより大きければ右、小さければ左へ進む
・これを繰り返すと、1回比べるたびに探す範囲が半分になる

たとえば100万件のデータでも、木の深さは約20段程度（2の20乗＝約100万）。つまり最悪でも20回比べれば見つかるのに対し、全部を順に調べると最大100万回かかります。件数が増えても比べる回数がほとんど増えないのが、木構造の最大の強みです。

🔑

どの列にインデックスを作るか

インデックスを作るほど速くなるわけではありません。どの列に作るかの判断が大切です。効果が高いのは次のような列です。
・検索でよく使う列：WHERE 列名 = 値 のように条件に指定される列
・値の種類が多い列（＝特定の値に絞ると件数がぐっと減る列）：社員IDやメールアドレスなど

逆に、効果が薄い・むしろ逆効果になるのは次のような列です。
・値の種類が少ない列：「性別（男・女）」「フラグ（0か1）」は索引を引いても大量の行が残り、あまり絞れない
・更新が非常に頻繁な列：行を追加・変更するたびに索引の書き直しが発生し、更新が重くなる

本の巻末索引で考えると、「は・ひ・ふ・へ・ほ」のページを全部载せても絞れませんが、「特定の専門用語」なら1ページに絞れます。それと同じで、索引が役立つのは「その値で大幅に件数が絞り込める」ときだけです。

🎯

基本情報技術者 練習問題