わかりやすく データベース どうやって 探す

はじめは一行ずつ見ていく

前のレッスンで、データベースは情報を表の形に並べて整理すると話しました。その中から何かを探すいちばん単純な方法は、いちばん上の行から一行ずつ合っているかを見ながら下へ進むことです。
合う行に出会ったら止まります。このように最初から最後まで順に見ていくことを、全件検索といいます。

探したい値を押してみましょう。いちばん上から一ますずつ見て下り、たどり着くまでに何回見たかを数えてくれます。

上のほうにある値は、数回ですぐに見つかりました。下のほうにある値は、その上をすべて通り過ぎてやっとたどり着きました。探す値がいちばん最後にあれば、結局すべての行を見ることになります。
行の数が少ないうちは、これでも十分速くて問題ありません。では、行がとても多くなったらどうなるでしょうか。

データが増えると、見ていくのが遅くなる

実際のデータベースは、行の数がとてつもなく多いものです。何百万行、何億行もめずらしくありません。全件検索でいちばん最後の値を探すには、そのすべての行を一回ずつ見なければなりません。
だから、行が二倍になれば見る回数も二倍になります。行が増えた分だけ探す手間もそのまま増えていく、これが全件検索の限界です。

押して件数を増やしてみましょう。いちばん最後の値を全件検索で探すのにかかる回数が、棒グラフで急に伸びていきます。

件数を増やすほど、棒がぐんぐん長くなりました。小さな表ではたいしたことのなかった仕事が、大きな表では大きな負担になります。
毎回最初から最後まで見ていくかぎり、この手間は避けられません。では、見ていかなくてもその場所へすぐ行く方法はないのでしょうか。さいわい、うまい方法があります。

索引を作って、すぐに飛ぶ

本の後ろにある索引を思い浮かべてみましょう。言葉が五十音順に並べてあり、横に何ページかが書いてあります。本を最初からめくらなくても、索引で言葉を見つけて、そのページをすぐに開けます。
データベースも、このような一覧を前もって作っておけます。これを索引、つまりインデックスといいます。

並べかえた索引の名札を押してみましょう。表を見ていかなくても、一、二回でその行へすぐに飛べます。

索引を使うと、表を見ていかなくてもすぐに着きました。いちばん最後にある値でも、一、二回で十分でした。
秘密は、索引が前もってきちんと並べかえてあることです。並んだ一覧なら、まん中を見て、探す値が前半にあるか後半にあるかを決め、もう半分を捨てることをくり返せます。そうすれば、百万個の中からでも二十回ほどで見つかります。

全件検索と索引を比べる

二つの方法を並べて、同じ件数で比べてみましょう。全件検索は、行の数と同じくらい多くの回数を見なければなりません。索引は並び順を使って、とても少ない回数で終わります。
件数が同じでも、結果は天と地ほどの差です。だから、よく探す項目には索引を作っておくと得なのです。

件数を選んで、両方の検索を押してみましょう。全件検索と索引が同じ値を探すのにかかった回数を、並べて比べます。

件数を増やすほど、全件検索の棒はぐんぐん伸びましたが、索引の棒はほとんど変わりませんでした。まさにこの差のために、データが大きいほど索引が活躍するのです。
もちろん、索引もただではありません。索引を入れておく場所がさらに必要で、新しい行が入るたびに、索引も並び順を保つように直さなければなりません。それでも、よく探す項目なら、それだけの価値があります。

まとめ

一言でまとめるとこうです。いちばん単純な探し方は、最初から一行ずつ全部見ていく全件検索です。データが少なければ、これで十分です。
でも、何億件にも増えると、見ていく手間が急に増えます。だから前もって索引を作っておき、一、二回でその場所へすぐに飛びます。同じ件数でも、索引のほうがずっと少なく見るだけですみます。

要点を順に押して振り返りましょう。（一行ずつ見る → データが増える → 索引で飛ぶ → 全件検索と索引）

これで、データベースがなぜ全件検索から索引へと移るのかがわかりました。では、その索引は実際にはどうやって作るのでしょうか。
並べかえた一覧のほかにも、ハッシュやツリーのような方法があります。次のレッスンでは、そのうち名札一つから場所をすぐに計算するハッシュを、まず見ていきます。