この特集で使用する［顧客］テーブル（表1）を基に，インデックスの構造を具体的に考えて見ましょう。［顧客］テーブルは30レコードあります。このテーブルの［顧客番号］カラムにBツリー・インデックスを付けると，図1のようになります。説明を簡単にするために，ルートに含むカラム値は1個（ブランチは2個）にしていますが，実際はもっとたくさんのカラム値を含みます。
 |
| 表1●［顧客］テーブル |
 |
| 図1●［顧客］テーブルの［顧客番号］カラムに付けたインデックス 一つのルート（，ブランチ，リーフ）に含まれるカラム値は，実際はもっと多い。だが基本的に，レコード数が多くなっても構造は同じである [画像のクリックで拡大表示] |
ここで，ルート，ブランチ，リーフに含むカラム値に着目してほしいのですが，ルート配下にある二つのブランチの一方は，ルートに含むカラム値以下の値，もう一方はルートに含むカラム値より大きな値になっています。ブランチとリーフの関係も同じです（二つのカラム値があり三つのリーフを指していますが，その構造は基本的に同じです）。
単純な配列構造に比べると複雑に感じるかもしれません。なぜ，こうした構造になっているかを説明する前に，あるカラム値を持つレコードを見つけるまでの動きをたどってみましょう。カラム値1030のレコードを見つける場合を考えてみます。まずルートを読み取り，そこに含まれるカラム値から，次にブランチ2を読めばよいことが分かります。同様に，ブランチ2のカラム値から，次はリーフ6を読めばよいことが分かります。そしてリーフ6のデータから，顧客番号が1030のレコードのポインタを特定できます。ルート，ブランチ，リーフ，レコードをそれぞれ1回ずつ読むので，ディスク・アクセス回数は4回になります。
サンプル・テーブルのようにレコード数が少ないなら，書籍の索引のように単純な配列構造の方が，ディスク・アクセス回数が少なくなるのではないか。そのように思われた読者もいることでしょう。確かに30レコードなら，単純な配列構造の方がディスク・アクセス回数は少なくなります。ですが，実際の業務アプリケーションでは，レコード数はもっと多くなります。インデックスのデータ（カラム値とポインタ）は，レコードそのものに比べればサイズは小さいですが，レコード数が増えれば比例して大きくなります。ということは，レコード数が増えれば（インデックスの）ディスク・アクセス回数も増えるということです。
それに対してBツリー・インデックスは，レコード数が増えてもルート，ブランチ，リーフをそれぞれ基本的に1回ずつ読めばよく，ディスク・アクセス回数は一定になります。これが，樹木のような3層構造になっている理由の一つです。一定になるだけでなく，実業務で利用するデータベースを想定すると，Bツリー・インデックスのディスク・アクセス回数は，単純な配列構造に比べて少なくなると言えるでしょう。
|
