データベースシステム入門：「データベースは体育会系図書館？」

（データベースシステムとその研究の世界を一般の人にわかりやすく伝えるため、「図書館」をモデルにした話を書いてみました。試験に出そうな（？）部分は太字で強調してあります。）

データベースシステムは図書館

「データベース」という言葉は、データの集まりという意味です。データベースシステムの研究では、例えて言うなら「欲しい本がすぐに見つかる図書館」をいかに作るかという問題を考えます。ここで「データ」は図書館の「本」に相当し、「ハードディスク」は「本棚」がたくさん収められている図書館の建物だと考えてください。

「欲しい本がすぐに見つかる」とはどういうことでしょうか？例えば、図書目録を調べて目的の本棚の番号がわかったとしても、本棚までの距離が遠ければがっかりしてしまいますよね？（高すぎて手が届かない、とか泣けてきます）

「キャッシュ」は新刊コーナー

歩く距離を減らす工夫として、新刊書籍のように人気があるものは「新刊コーナー」にまとめて置いておくと便利です。この「新刊コーナー（あるいは人気の図書コーナー）」がいわゆる「キャッシュ」です。キャッシュはハードディスクより速くアクセスできる「メモリ」上に用意するのが普通で、図書館でいうと「受付カウンターの近く」というわけです。

重力・空間を無視して本棚を並び替えよう (B-tree)

しかし「新刊コーナー」の棚も大きさには限界があるので、入りきらない本のための本棚の方がどうしても多くなります。そこで、その本棚まで歩く距離（ディスクI/Oの回数）を減らすためにどうしたらいいかを考えます。現代社会に生きる私たちは、どうしても書店のように本棚を縦横に綺麗に並べたくなってしまいますが、そこはさすが1970年代の研究者。発想が違います。彼らは本棚を縦横ではなく、ピラミッド状に並べることを考えました。本棚を一つ設置したら、次は、1m空けて10個の本棚を並べる。そしてその10個の本棚それぞれにつき、また1mずつあけて本棚を10個並べる、といった具合です。

1m間隔で10,000個の本棚を一列に並べたら10,000mにもなってしまってとても大変です。この大変さを表すために、nを本棚の数として、O(n)（オーダー n）と書きます。これは、n=10,000のとき、10,000m歩かなくてはいけない本棚の並び方、ということを意味します。一方、ピラミッド方式だと、どの本棚にでも4m歩くだけで到達できます（4m = log 10,000、1mおきに10個の本棚があるので、10を4回かけて10 x 10 x 10 x 10 = 10,000個の本棚になる）。これをO(log n) （オーダー ログn）と表します。ログオーダーのピラミッド方式では、本棚の数が10倍になっても、1mしか歩く距離が増えません（log 100,000 = 5。もしかしたら空中に浮かぶ本棚までジャンプする必要があるかもしれないですが…）。この本棚の配置はB-treeと呼ばれ現在最もよく使われています。

本はきちんと元の場所に整理して戻しましょう（インデックスとプロトコル）

ピラミッド型配置で本棚までの距離は短くなりましたが、これだけではまだ欲しい本が次の10個の本棚のうちどこにあるかまではわかりません。そこで、各本棚に、五十音やジャンル（小説、歴史など）のラベルを張っておきます。そして、本棚を、左から右の方向にジャンルごとに、しかも、五十音順に並べる、という索引（インデックス）を作るのです。抜き取った本を元の場所に戻さない悪い人がいると、当然この索引は役立たずになってしまいますので、ルールを守るように監視するのがデータベースシステムの仕事でもあります。このルールは「プロトコル（約束・手順）」と呼ばれます。

図書館は仲良く使いましょう （トランザクション管理、同時アクセス制御）

図書館の人が本棚に本を戻しつつ、たくさんの利用者が本を借りにくると、どうしても本棚までの通路が混雑して渋滞が起こってしまいます。この渋滞を解消するために、「今まとめて本を棚にもどすから、ここは通行止め（ロック）ね」とか、「こっちの棚は空いているからどうぞ」などと誘導して移動をスムーズにする（スループットを上げる）のが、「トランザクション管理」です。ロックなどを用いて複数の人の流れをコントロールすることを「同時アクセス制御（concurrency control)」と言います。

手狭になったらもう一つ増やそう　（分散データベース）

そして、一か所の図書館で蔵書や利用者の数をさばけなくなると「分館」を作ります。これがいわゆる「分散データベース」で、離れた図書館にしかない本が欲しい場合は、やむなく「取り寄せ（ネットワーク通信）」をするのですが、取り寄せはコストがかかるので、1つの本はあらかじめ3か所の図書館で読めるように3冊購入（といいつつ実はコピー）しておいたり（複製・レプリケーション）、近くの図書館同士なら取り寄せも簡単なので、敢えて離れた図書館に3冊目を置いておいて移動コストを減らす（分散配置・アロケーション）などの工夫もできます。

ハードディスクは体育会系？

そして図書館を形作る「ハードディスク」は、力持ちで大雑把なことは得意ですが、細かい仕事は苦手な体育会系なので、扱いがとても難しいです。「一列に並んだ本棚を100個まとめて持ってきて(シーケンシャルスキャン)」というと片手でひょいっと持ち上げるような頼もしいやつなのに、「こっちと、あれと、あそこと、あの本棚合わせて10個を持ってきて（ランダムアクセス）」というと、本棚100個を移動するより時間がかかってしまったりします。実際、上のハードディスクの写真を見てもらうとわかりますが、ハードディスクというのは要するに回転するレコードに針を当ててデータを読む構造なので、針を細かく動かす仕事は苦手です。そんな彼のために、「とりあえず100個をここ（バッファ）に持ってきて。あとはこっちで探すから」という指示を出すのもデータベースシステムの仕事です。最近流行りのフラッシュメモリー（SSD）も仕事は速いけれどどうやら体育会系脳はそのままのようで。

• Leo’s Chronicle: Flash-Based DBMSの最前線

ここに挙げた項目はそれぞれ奥が深く、今でも熱心に研究されています。そして、ハードディスクのような体育会系脳をいかに賢くするか、というのがデータベース研究の醍醐味でもあります。それに関連する話はまた次の機会に。

（体育会系の人がアホだとか言っているわけではありません。あしからず）

関連：

• Leo’s Chronicle: ぜひ押さえておきたいデータベースの教科書