データベースは その なかから どう さがしだすか

さいしょは いちぎょうずつ みて さがします

まえに データベースは
ひょうの かたちに ならんで せいりされると まなびました。
その なかから なにかを さがす
いちばん たんじゅんな ほうほうは これです。
いちばん うえの ぎょうから したへ
いちぎょうずつ あっているか みていくのです。
あう ぎょうに であったら とまります。
こうして さいしょから さいごまで
ぜんぶ みるのを ぜんたい けんさくと いいます。

さがしたい あたいを おしてみて。いちばん うえから ひとマスずつ みていき、とどくまで なんかい みたか かぞえます。

うえの ほうに ある あたいは
なんかいかで すぐ みつかりましたね。
でも したの ほうに ある あたいは
その うえを ぜんぶ とおって やっと とどきました。
さがす あたいが いちばん うしろに あると
けっきょく ぜんぶの ぎょうを みた ことに なります。
ぎょうが すくないときは これでも
じゅうぶん はやくて もんだい ありません。
では ぎょうが とても おおく なったら どうでしょう?

データが ふえると みるのが おそくなる

じっさいの データベースは
ぎょうの かずが ものすごい。
すうひゃくまん、すうおく ぎょうも ふつうです。
ぜんたい けんさくは いちばん うしろの あたいを さがすとき
その ぜんぶの ぎょうを いちど みなければ なりません。
だから ぎょうが にばいに なると
みる かいすうも にばいに なります。
ぎょうが ふえた ぶんだけ
さがす コストが そのまま ふえます。
これが ぜんたい けんさくの げんかいです。

けんすうを クリックで ふやしてみて。いちばん うしろの あたいを ぜんたい けんさくで さがす かいすうが ぼうで きゅうに ふえます。

けんすうを ふやすほど
ぼうが ぐんぐん ながく なりましたね。
ちいさい ひょうでは なんでもない ことが
大きい ひょうでは 大きな ふたんに なります。
まいかい さいしょから さいごまで みる かぎり
この コストは さけられません。
では みないで そのまま
その ばしょへ いく ほうほうは ないでしょうか?
さいわい かしこい ほうほうが あります。

さくいんを つくって すぐ ジャンプ

ほんの うしろに ある さくいんを おもいうかべて。
ことばが じゅんに ならんでいて
よこに なんページか かいてあります。
ほんを さいしょから ぜんぶ めくらず
さくいんで ことばを さして
その ページへ すぐ ひらきます。
データベースも こういう いちらんを
まえもって つくって おけます。
それを さくいん、つまり インデックスと いいます。

ならんだ さくいんの なふだを おしてみて。ひょうを みずに クリック いちにかいで すぐ その ぎょうへ ジャンプします。

さくいんを さすと
ひょうを みずに すぐ いけましたね。
いちばん うしろに ある あたいでも
クリック いちにかいで じゅうぶんでした。
ひけつは さくいんが まえもって
きちんと ならんでいる ことです。
ならんでいれば どのあたりか
すぐ せばめて させます。
ぜんぶ みる ひつようが きえたのです。

ぜんたい けんさくと さくいんを くらべる

ふたつの ほうほうを ならべて
おなじ けんすうで くらべましょう。
ぜんたい けんさくは ぎょうの かずだけ
おおく みなければ なりません。
さくいんは ならびを つかって
とても すくない かいすうで おわります。
けんすうが おなじでも けっかは
てんと ちほどの ちがいです。
だから よく さがす データには
さくいんを つくって おくのが とくです。

けんすうを えらんで りょうほうの さがしを おしてみて。おなじ あたいを さがす かいすうを ぜんたい けんさくと さくいんで ならべて くらべます。

けんすうを ふやすほど
ぜんたい けんさくの ぼうは ぐんぐん のびましたが
さくいんの ぼうは ほとんど そのままでした。
まさに この さが
大きい データほど さくいんを ひからせます。
もちろん さくいんも ただでは ありません。
まえもって つくり、ならびを たもつ
てまが かかります。
それでも よく さがすなら それだけの ねうちが あります。

まとめて みましょう

ひとことに まとめると こうです。
いちばん たんじゅんな さがしは ぜんたい けんさく、
つまり さいしょから いちぎょうずつ ぜんぶ みること。
データが すくなければ じゅうぶん。
でも すうおくけんに ふえると
みる コストが きゅうに ふえます。
だから まえもって さくいんを つくり
クリック いちにかいで すぐ ジャンプ。
おなじ けんすうでも さくいんは ずっと すくなく みます。

かなめを じゅんに おして ふりかえって。(いちぎょうずつ みる → データ ふえる → さくいんで ジャンプ → ぜんたい けんさく vs さくいん)

これで データベースが
ぜんたい けんさくから さくいんへ
なぜ うつるか わかりました。
でも その さくいんを
じっさいには どう つくるのでしょう?
ならんだ いちらんの ほかにも
ハッシュや ツリーの ような ほうほうが あります。
その かしこい さくいんの しくみを
つぎの かいで ひとつずつ おってみよう。