女子大生とゼロから学ぶ　データベースの基礎 第3回

RDBMSの考え方を基礎から学ぼう

「インデックスとトランザクションって」（由美）

今回は、データベースの検索機能を支えるインデックスの仕組みと、データの一貫性を保つトランザクションの性質や処理方法について説明していこう。このインデックスとトランザクションの処理はデータベースの根幹に関わるものなので、よく理解しておきたい。

先生（左）：由美ちゃんの通うテニススクールに来ている情報系大学の講師／由美ちゃん（中）：地元の大学に通う学生。大学の授業でコンピュータを少しかじっている／お父さん（右）：文房具屋の店主。表計算ソフトで商品や顧客の管理をしているが、最近面倒になってきている

インデックスとトランザクションを勉強しよう

先生：今日はインデックスとトランザクションの話をしましょう。

由美・お父さん：よろしくお願いします。

先生：では、インデックスから始めましょう。中村さん、この前の製品台帳をまたお借りしますね。

お父さん：はい、どうぞ。

先生：じゃあ由美さん、ここに書いてある情報を探してください。そうですね、まずC社の鉛筆1本の卸値を探してください。

由美ちゃんは製品台帳をめくって探しはじめた。

由美：見つけました。

先生：早かったですね。じゃあ、今度は、B社の消しゴム1個の売値を探してください。

由美ちゃんは再び製品台帳をめくって探しだした。しかし、今度はすぐに見つけられないようだ。

由美：やっと見つけました。

先生：お疲れ様でした。2番目の質問の答を探すのにずいぶんと時間がかかってしまいましたね。なぜでしょう。

由美：どこに何が書いてあるか分からないので、最初からページをめくってました。1番目の質問は最初のほうにあったのですぐに見つけることができましたが、2番目の質問は、台帳の最後の方に書かれていたので、時間がかかってしまいました。

先生：そうですね。コンピュータを使って管理しても、何も工夫していなければ奥のほうに格納されたデータを検索するには非常に時間がかかってしまいます。そのため、リレーショナルデータベースには索引にあたる「インデックス」を作成する機能があります。

インデックスとして代表的なBツリー

由美：インデックスの仕組みは、どうなっているんですか？

先生：インデックスはデータベースの属性の値、すなわち各レコードのフィールドと、その値を持っているレコードの位置を記録した表です（図1）。この表の作り方次第でインデックスの性能が左右されます。ここではインデックスの代表的な例としてBツリーについてお話しましょう。

図1●インデックスはレコードの要素がどこにあるかをすばやく探せるようにする索引

由美：Bツリー？

先生：はい、Balanced Treeという意味で、ミュンヘン工科大学のベイヤー（Bayer）教授によって提唱されたインデックスの構成法です。ツリー構造のメモリ領域を用意して、さっきの表をそのノードやリーフ（葉）という領域に格納します（図2）。各ノードには属性の値やレコード上の位置のほか、他のノードやリーフへのリンク（ポインタ）が格納されます。

図2●Bツリーは深さのバランスが取れたツリー構造

お父さん：なるほどそれでツリーなんですね。ところでBalancedというのはどういう意味ですか？

先生：ルートノードから各末端のリーフまでの距離、つまりどの部分もツリーの深さが同じになるように配分（バランス）するという意味です。

由美：なるほど、そういう風にバランスよく配置すれば、どのノードを探す場合でも検索時間はほぼ同じになるのですね。

先生：まさしくその通りです。ところで由美さん、このツリー構造の図ですけど、どこかでみたことないですか？

由美：うーんと、確かにどこかで見たことあるんだけど……思い出したわ。LISP言語で出てきたリスト構造ですね（図3）。リスト構造を使うことで、簡単にインデックスの追加とか削除ができるわけね。

図3●リスト構造によって、要素の削除や追加が簡単になる

先生：そういうことです。

（次ページ、「トランザクションは切り離せないひとまとまりの処理」に続く）