数えきれない中から、どうやって 一つを はやく さがすのか

じょうほうを いれるのにも かたちが あり、その かたちを いれものと よびます。おなじ データでも れつで もつか、ひょうで もつか、えだで もつかで かたちが かわります。いれものは てきとうに えらぶのでなく、やりたい ことに あわせて えらびます。じゅんに みたいなら れつが よく、なまえで はやく さがしたいなら ひょうが よい。そして ひとつの いれものが すべてを おなじだけ うまく できる わけでは ありません。ある どうさは はやく、ある どうさは おそい。だから よい いれものを えらぶことが はやい プログラムの はじまりです。つぎの かいで だいひょうてきな いれものを ひとつずつ みていきます。

はいれつは ばんごうの ついた マスが ぴったり ならんだ ロッカーです。ばんごうを いえば その マスへ すぐ とび、とても はやく とりだせます。リストは マスが あちこちに ちらばり、それぞれが つぎの マスの じゅうしょを かいた メモを もっています。だから 5ばんめを とるには さいしょから メモを たどって ひとマスずつ いくので、すこし おそい。でも まんなかに あたらしい マスを はさむときは メモを 2まい なおすだけなので かんたん。はいれつは ぎゃくに うしろの マスを ぜんぶ おさないと いけず めんどう。はやい アクセスが ほしければ はいれつ、まんなかの そうにゅうが おおければ リスト、と まちかえて えらびます。

スタックは おさらの つみかさねです。うえに のせて、とりだすときは いちばん うえ(さいごに いれた もの)から でます。だから あとに いれた ものが さきに でます。キューは れつです。うしろに ならび、とりだすときは いちばん まえ(さきに きた もの)から でます。だから さきに いれた ものが さきに でます。どこに つかう? いま やった ことを ぎゃくに もどしたり もどりたいときは スタックが ぴったり。さいごの どうさから じゅんに とりけされるからです。きた じゅんに こうへいに しょりしたいときは キューが あう。いんさつ まちや ばんごうふだの ように。つみかさねは あとさき、れつは さきさき、この いちぎょうだけ おぼえれば いい。

データベースは じょうほうを きちんと しまう きょだいな そうこです。ふつう ひょうに せいりします。よこ いちぎょう(ぎょう)が ひとつの けん、たて いちれつ(れつ)が なまえや ねんれいなどの こうもくです。あたらしい じょうほうが きたら、あう ひょうの あう れつに きちんと いれます。ただ ファイルに かくのと ちがう ところは ふたつ。ひとつ、たくさんの じょうほうを いちどに あんぜんに しまう。ふたつ、なんおく けんの なかからも ほしいものを はやく さがす。だから たくさんの じょうほうを あつかうときは ファイルでなく データベースを つかいます。

データベースが なにかを さがす いちばん たんじゅんな ほうほうは、さいしょから いちぎょうずつ さいごまで みる ぜんたい けんさくです。データが すくないときは じゅうぶん はやい。でも けんすうが すうおくに ふえると、みる ぎょうも それだけ おおくなり、だんだん おそくなります。だから まえもって さくいんを つくります。さくいんは ならんだ なふだの いちらんの ようで、ぜんぶ みずに クリック いちにかいで すぐ その ばしょへ ジャンプします。おなじ けんすうでも さくいんは ぜんたい けんさくより ずっと すくない かいすうで さがしだします。さくいんを じっさいに どう つくるか(インデックス、ハッシュ、ツリー)は つぎの かいで つづきます。

ハッシュは あたいを みて けいさんで ばしょの ばんごうを きめ、その ばしょに すぐ いれて すぐ さがす やりかたです。ばしょを ひとつずつ みていかず いっぱつで とどくので とても はやい。いれるときも さがすときも おなじ けいさんを つかうので、いれた ばしょと さがす ばしょが ぴったり あいます。よわみも あります。ちがう あたい ふたつが けいさんの けっかが おなじで おなじ ばしょへ いく ぶつかり(しょうとつ)が おきることが ある。そのときは ひとつの ばしょに まとめて いれるか、となりの ばしょへ ずらして べつに しょりすれば いい。まとめると、けいさんで ばしょを きめて すぐ さがし、しょうとつは べつに しょりするのが ハッシュです。

データを 一れつに ならべる かわりに きの かたちで おくと、一つの ねもとから えだに わかれて おりていきます。さがす あたいが いまの ますより 大きければ かたほうの えだへ、小さければ もうかたほうの えだへ いきます。すると 一だん おりるたびに みる こうほが はんぶんずつ へります。だから 何千こ あっても 何だんかで みつかります。だんの かず、つまり きの ふかさが はやさを きめます。データが 二ばいに ふえても ふかさは 一だんだけ ふえるので、とても おおくても ゆっくり ふかくなります。じしょを まんなかから ひらいて はんぶんずつ しぼるのと おなじです。

ツリーは えだで はんぶんずつ さがすとき はやい。でも あたいを じゅんばんに だけ いれると えだが わかれず かたほうだけ ながくなり、ほぼ いちれつに なって おそく なります。バランス ツリーは これを ふせぎます。いれたり ぬいたり して かたほうが おもくなると じぶんで ノードの ばしょを とりなおします。これを かいてんと いいます。かいてんで りょうがわの ふかさを いつも にたように たもてば、データが いくら ふえても ふかさは ゆっくり(log) そだちます。だから いつでも すうだんかいで さがせると ほしょうします。わたしたちは ただ いれたり ぬいたり するだけで、ツリーが じぶんで バランスを まもります。

データが おおいと さいしょから ぜんぶ みるのは おそい。インデックスは ほんの うしろの さくいんのように、データベースが ほしい ばしょへ すぐ ジャンプできるよう まえもって つくった ちずです。しゅるいは ふたつ。ハッシュ インデックスは せいかくな あたい ひとつを いっぱつで さがします。ツリー インデックスは あたいが ならんでいるので はんいを みるのに むいています。ただし ただ ではない。インデックスは ばしょを よけいに とり、データが かわると インデックスも いっしょに こうしんします。それでも うまく つかえば さがすのが ずっと はやくなります。

グラフは たいしょうを てんに、たいしょう どうしの かんけいを せんに もつ しりょうです。ひとを てんに、ともだち かんけいを せんに おくと、つながりが ひとめで みえます。ひとつの てんから せんを たどると となりが でて、その となりの せんを また たどると ともだちの ともだちが でます。こうして せんを たどって ひろがれば、つながった むれ ぜんたいを みてまわれます。おすすめや つながり さがしの ように かんけいが かなめの しごとでは、ひょうなら なんども みなおす ものを、グラフなら せんを たどるだけで とどきます。まとめると、てん=たいしょう、せん=かんけい、そして となりを たどる、これが グラフです。

SQL は データベースに ほしい ものを えるために たずねる ことばです。いう ことは ふたつだけ。まず どの れつを みるか えらびます。ひょうには れつが いくつも あって、その なかで みたい れつだけ のこします。これを SELECT と いいます。つぎに どの ぎょうを のこすか じょうけんを かけます。ぜんぶの ぎょうでは なく じょうけんに あう ぎょうだけ のこす。これを WHERE と いいます。えらんだ れつと のこした ぎょうが であうと、じょうけんに ぴったり あう ちいさな けっかの ひょうが でます。ひょう ひとつを れつえらびと ぎょうの しぼりこみで たずねると こたえが ひょうで かえる、それが SQL の きほんです。

データは ふつう いくつかの ひょうに わかれています。ちゅうもんは ちゅうもんの ひょうに、ひとの じょうほうは こきゃくの ひょうに べつべつ。ひとつの ひょうだけ みても ひょうを またぐ しつもんには こたえられません。だから ふたつの ひょうが ともに もつ きょうつうの はしらを さがします。こきゃくばんごうのように。その はしらの あたいが おなじ ぎょうどうしを くみあわせると、ふたつの ひょうが いちぎょうに つながります。こう つなげば ひとつの ひょうのように あつかえ、この ちゅうもんを した ひとの なまえ といった しつもんに こたえられます。まとめると、きょうつうの はしらで ぎょうどうしを くみあわせ ばらばらの ひょうを つなぐのが ジョインです。

せいきかは ひとつの ひょうに くりかえし かかれる じょうほうを はがして べつの ひょうに わけ、きょうつうの れつで また つなぐ せいりです。こきゃくの なまえを ちゅうもんごとに かく かわりに、こきゃくは こきゃく ひょうに いちどだけ かき、ちゅうもん ひょうには こきゃく ばんごうだけ のこします。すると ばんごうが かわっても こきゃく ひょうの ひとぎょうを なおせば おわりなので くいちがいが おきません。ちらばった ぎょうを ひとつずつ なおして もらす ことも ない。ただし こまかく わけすぎると なにかを みるたびに ひょうを いくつも つなぎなおさねば ならず おそく なることが ある。そんなときは よく いっしょに みる じょうほうを わざと ひとつの ひょうに あわせて おくこともあり、これを ひせいきかと いいます。けっきょく くりかえしを はがして わけ かんけいで つなぎつつ、わけすぎたら また あわせる つりあいが せいきかです。

トランザクションは いくつかの しゅうせいを ひとつの たばとして あつかい、ぜんぶ できるか ぜんぶ できないかに する やりかたです。ふりこみのように ひくと たすが ペアの とき、ふたつ とも おわって はじめて ほんとうに はんえいします。とちゅうで でんげんが きえたり なにかが くいちがったら、はんぶんだけ のこさず まるごと まえの じょうたいに もどします。これを ロールバックと いいます。また なんにんも どうじに おなじ ざんだかを かえようとしたら、ひとりずつ じゅんに しょりして たがいに うわがきしないように します。いちどに からまっていた ことが じゅんばんに なります。まとめると、ぜんぶか ゼロか、くいちがいは ロールバック、どうじでも からまない。この みっつが トランザクションです。

キャッシュは よく つかう データの しゃほんを ちかくに おく やりかたです。とおい ほぞんばしょは いき かえりの みちが ながく おそい。でも しゃほんを ちかくに おくと つぎからは みじかい みちで すぐ とりだす。さがす ものが キャッシュに あれば ヒットと よび すぐ はやく とりだす。なければ ミスと よび、とおい ばしょまで いって もってきた あと、その しゃほんを キャッシュに のこす。だから つぎは ヒットに なる。よわみも ある。げんぽんが かわっても キャッシュには ふるい しゃほんが のこり、ふるい あたいを わたすことが ある。これを キャッシュが ふるく なったと いう。だから ときどき キャッシュを いれなおすか、いっていの じかんが すぎたら すてて ふるいものを ふせぐ。まとめると、ちかくに しゃほんを おいて ヒットすれば はやく、げんぽんが かわったら キャッシュを あたらしく するのが キャッシュです。

あっしゅくは おなじ じょうほうを より ちいさく しまう ぎじゅつです。ふたつの うでが あります。ひとつは くりかえしを へらすこと。AAAA のように おなじ ものが つづいたら A を よんかい と かけば みじかく なります。もうひとつは よく でてくる かけらに みじかい コードを あたえること。ながい かけらを みじかい きごうに かえると ぜんたいが へります。そして あっしゅくした ものは もどせば げんぽんと まったく おなじ。すてた ものが ないからです。これを むそんしつと いいます。つよく あっしゅくすると もっと ちいさく なりますが、あっしゅくと かいとうに じかんが もっと かかる。だから どれだけ ちいさく と どれだけ はやく を まちかえて えらびます。まとめると、くりかえしを へらし みじかい コードを あたえて ちいさく しまいつつ、もどせば げんぽんの ままなのが あっしゅくです。

データが いちだいで てに おえないほど 大きくなると、こまかく わけて なんだいかに しまいます。これを ぶんさんと いいます。それぞれの だいは ぜんたいの いちぶだけ もつので、あつまれば とても 大きな データも しまえます。そして いちだいが しんでも こわれないよう、おなじ データを なんだいかに コピーして おきます。これを ふくせいと いいます。わけて しまう ぶんさんと、コピーする ふくせいは ちがう かんがえ。ぶんさんは にもつを きざんで わけること、ふくせいは おなじ にもつを なんかしょにも おくこと。こう きょだいで はやい しょりの ために、きびしい ひょうの かたちを ゆるめた うつわを NoSQL と いいます。ハッシュのように キーで あたいを すぐ いれて さがす うつわを 大きく そだてた ようなもので、つぎの りょういきである じんこうちのうが あつかう ぼうだいな データへの はしに なります。