この記事では、データベースのインデックスについて、初心者にも分かりやすく、図解付きで丁寧に解説しています！
インデックス
- インデックスとは素早くデータベースを検索する仕組み。本の目次みたいなもの。
B木インデックス
- B木インデックスは2分探索を応用したインデックス
ハッシュインデックス
- ハッシュインデックスはハッシュ関数を使ったインデックス
インデックスとは
インデックスとは素早くデータベースを検索する仕組みです。インデックスを設定することにより、データを検索するスピードが上がります。インデックスは本の索引みたいなものです。
インデックスは「索引にした値」と「ポインタ(格納場所)」をセットで保管します。本の目次のように、インデックスを見ることで、どこにデータがあるかすぐに分かります。
ただ、インデックスから山田花子を探すのも、生徒表から山田花子を探すのも、どっちも手間が変わらないのでは？って思いませんか？実は違うんです。
データを記録する記憶装置は、データをある一定のサイズ毎に区切って保管します。この塊をブロックと言います。仮に1ブロックに保管できるデータ量が512バイトで、生徒表1行あたりのデータ量が128バイトの場合、1つのブロックに保管できるデータは4行になります。
データベースにデータを読み書きするときは1ブロックずつ行います。なので、データを検索するときも1ブロックずつ行います。つまり、生徒表の場合、4行ずつ検索していきます。生徒表が1000行あれば、250回に分けて検索するってことですね。
一方、インデックスの1行は生徒表の1行よりもギュッと圧縮されています。
生徒表には、「生徒番号」「氏名」「住所」「クラス」など沢山項目がありますが、インデックスは「氏名」と「ポインタ」だけでOKです。インデックスの1行が16バイトだとしましょう。すると、1ブロックに保管できる行数が32行になります。生徒表をそのまま検索すると250回に分ける必要がありましたが、インデックスを検索すれば1000行÷32行=31.25となるので、分ける回数が32回でOKになります。
これがインデックスを使うと早く検索が出来るようになる理由です。インデックスにも複数種類があります。応用情報で出題されたインデックスを紹介していきましょう。
B木インデックス
B木インデックスは2分探索を応用したインデックスです。
2分探索法では、昇順に並んだ値からある値を探す時に、まず、中央の値と探したい値を比較し、探したい値が前半にあるか後半にあるかを明らかにする。そして検索範囲を絞り込んだら、再度、その範囲の中央の値と探したい値を比較し、探したい値がその範囲の前半にあるか後半にあるかを明らかにする。。。というのを繰り返しながら値を探します。
例えば、0~100の数字から「30」を探す時、「30」を0~100の真ん中である50と比較し、50より小さいことが分かったので、次は0~50のの真ん中である25と比較し、25より大きいことが分かったので、次は26~50の真ん中である37と比較し・・・を繰り返して「30」を探します。1から順番に探すよりも2分探索を使う方が早く目的の数字を探すことが出来ます。
B木インデックスは2分探索を応用しています。B木インデックスは下図のように、探したい値がどこの範囲にあるかを判断しながら検索していきます。探したい値はIDでも日付でも名前でも何でもOKです。下図では分かりやすいように数字にしています。
ハッシュインデックス
ハッシュインデックスはハッシュ法を応用したインデックスです。
ハッシュ法とは、ハッシュ関数と言う「ある特定のルール」に従ってデータの格納場所を決めるやり方です。ハッシュ関数を使って求めた値をハッシュ値と言います。
インデックスはハッシュ値とポインタを保持しています。検索したい値をハッシュ関数でハッシュ値に変換すれば、一発でポインタが分かります。ただし、「〇〇以上」とか「××で始まる」といった検索は出来ません。
応用情報技術者試験での出題例
令和7年度秋期問27、令和5年度秋期問26
応用情報技術者
午前試験 令和7年度秋期問27、令和5年度秋期問26
“売上”表への次の検索処理のうち，B⁺木インデックスよりもハッシュインデックスを設定した方が適切なものはどれか。ここで，インデックスを設定する列を＜＞内に示す。
売上（伝票番号，売上年月日，商品名，利用者ID，店舗番号，売上金額）
ア 売上金額が1万円以上の売り上げを検索する。＜売上金額＞
イ 売上年月日が今月の売上を検索する。＜売上年月日＞
ウ 商品名が’DB’で始まる売上を検索する。＜商品名＞
エ 利用者IDが’1001’の売上を検索する。＜利用者ID＞
正解は”エ”
ハッシュインデックスは「この値を検索したい！」と単一の値を検索するときに有効です。逆に範囲の検索は出来ません。よって、答えはエです。
ア 「以上」と範囲の検索になるので不可です
イ 「〇月1日以上〇月31日以下」と範囲の検索になるので不可です
ウ 「DBで始まる」と範囲を指定しているので不可です
