わかりやすく インデックス データベース とは

本の後ろには索引がある

これまでのレッスンで、データベースが目当ての行をどう探すのか、そしてハッシュや平衡木がどうやってすばやく探すのかを見てきました。いよいよ、その道具がデータベースの中でどう使われるのかを見る番です。
データがとても多いと、最初から最後まで見ていくのは遅くなります。厚い本で言葉を最初のページから探すのと同じです。だから本の後ろには、言葉の横にページ番号を書いた索引があるのです。

本文を最初から見ていくのと、索引で飛ぶのを押して比べてみましょう。何回で見つかるかを数えてくれます。

索引で飛ぶと、ずっと少ない回数で見つかりました。データベースのインデックスは、まさにこの索引です。表の列を一つ選び、その値と行の位置を組にして前もって書いておいた一覧です。
でも、索引にも種類があります。正確な値を一つ探すときと範囲を探すときとでは、向いている方法が違うからです。

正確な値にはハッシュインデックス

「キム・チョルス」のように、ぴったり一つの正確な値を探したいときがあります。そんなときは、ハッシュインデックスが向いています。
前に見たハッシュが名前を受け取って、すぐに場所の番号を計算してくれます。だから、一行ずつ見ていかなくても、その場所へ一回で飛べます。ロッカーの番号を覚えておいて、そのますをすぐに開けるのと同じです。

名前を押すと、ハッシュが場所の番号を計算して、そのますへ一回で飛びます。

名前一つで、すぐに場所が見つかりました。ハッシュインデックスは、このように正確な値を探すのがとても速いのです。
でも、弱点があります。ハッシュは値を大きさに関係なく散らしておくので、「20歳から30歳まで」のように範囲で探すことはできません。そういうときは、別のインデックスが必要です。

範囲にはツリーインデックス

「20歳から30歳まで」のように、範囲で探したいときがあります。そんなときは、ツリーインデックスが向いています。ツリーインデックスは前のレッスンの平衡木で作られていて、値を小さいものから大きいものへと並べておきます。
だから、始まりの値を見つければ、そこから横へずっと続けて、範囲の中の値を順に見ていけます。辞書が五十音順になっているのと似ています。実際のデータベースのほとんどは、このツリーインデックスを基本に使っています。

探す範囲を押して決めましょう。並んだツリーインデックスが始まりの値を見つけ、範囲の中をずっと見ていきます。

並んでいるので、範囲が横へずっと続きました。ハッシュは一点をぴたりと探し、ツリーは一列をずっと見ていきます。
だから、何をよく探すかによって、合うインデックスが変わります。正確な値をよく探すならハッシュ、範囲をよく探すならツリーです。でも、インデックスはただではありません。

インデックスはただではない

インデックスには、よいことばかりがあるわけではありません。一つ目に、場所をよけいにとります。索引を別に書いておくので、その分だけ記憶する場所が多く要ります。
二つ目に、データが変わったら、インデックスもいっしょに直さなければなりません。新しい行を入れたり消したりするたびに索引も直す必要があるので、書きこみがその分遅くなります。だから、むやみにたくさん作るとかえって損です。

行を入れたり消したりしてみましょう。データが変わるたびにインデックスもいっしょに直され、使う場所も増えていきます。

データを変えるたびにインデックスもいっしょに動き、場所もだんだん多くとるようになりました。だから、インデックスはよく探す列にだけ選んで作ります。
速くなる得と、場所や直す手間というコストを、てんびんにかけるのです。うまく選べば、探すのがずっと速くなります。

まとめ

一言でまとめるとこうです。インデックスは本の後ろの索引のように、目当ての場所へすぐに飛ばせてくれる一覧です。ハッシュインデックスは正確な値を一つ、一回でぴたりと探し、ツリーインデックスは並んでいるので範囲をずっと見ていくのに向いています。
ただし、場所をよけいに使い、データが変わるたびにいっしょに直さなければなりません。だから、よく探す列にだけ選んで作ります。

要点を順に押して振り返りましょう。（本の索引 → 正確な値にはハッシュ → 範囲にはツリー → ただではない）

これで、インデックスがどうやって探すのを速くするのかがわかりました。ここまでは、表の行に並んだデータを扱ってきました。
でも、友だち関係や地下鉄の路線のように、データどうしのつながりそのものが大事な場合もあります。次のレッスンでは、点と線でつないで入れておくデータ、グラフに出会います。