この特集の目的は，SQL文の処理手続きの問題点を見抜けるようになることです。処理速度はディスク・アクセス回数に大きく左右されますので，手続きごとのディスク・アクセス回数を見極められるようになることと言ってもいいでしょう。ディスク・アクセス回数を減らす最も基本的な技術が，今回取り上げる「インデックス」です。インデックスにはいろいろな種類があります注1が，ここでは最もよく使われる「Bツリー・インデックス」に絞ります。
「インデックスを使うと検索時間が短くなる」。このことをきちんと理解するには，インデックスの内部構造を知る必要があります。書籍の索引を例に一般的なインデックスを説明し，その後，データベースのBツリー・インデックスの内部構造について解説します。
ページをめくる回数を減らす書籍の索引
インデックスを日本語で言えば「索引」です。たいていの専門書籍には，用語とその用語の登場するページ番号をまとめた索引があると思います（図1左）。書籍を頭から読むのではなくピンポイントで何かを調べたい場合，索引があるのとないのとでは，該当ページを見つけるまでの時間に大きな差が生じます。
 |
| 図1●書籍の索引とデータベースのインデックス 索引の用語は（検索条件の）カラム値に，索引のページ番号はポインタに相当する。インデックスはこの二つの要素からなる [画像のクリックで拡大表示] |
索引がなければ，どうやって該当ページを見つけるのでしょうか。おそらく，先頭からぱらぱらとページをめくって探すことになるでしょう。それらしいページを見つけても，もっと詳しい説明個所があるかもしれないと考え，結局最後のページまでめくることになるかもしれません。索引があれば，用語から該当ページをピンポイントに見つけることができます。索引のページ数は通常少ないので，ページをめくる回数を大幅に削減できることになります。
データベースのインデックスもこれと同じようなものです。ページをめくることがディスク・アクセスに相当し，索引（インデックス）があることで，ディスク・アクセス回数を大幅に削減できるというわけです。
書籍の索引をデータベースに置き換えて考えてみましょう。索引に載っている用語は探したい情報ですので，データベースで言えば，SELECT文の検索条件に相当します。シンプルな検索条件（例えば，WHERE 顧客番号＝1030）を想定すると，索引の用語は「レコードごとのカラム値」になります。同様に索引のページ番号は，ピンポイントに情報にたどりつくためのものなので，データベースで言えばディスク上の格納場所（本特集では「ポインタ」と呼びます）になります（図1右）。まとめると，データベースのインデックスに含まれるデータは，（1）各レコードのカラム値と，（2）レコードのポインタ注2の二つ。これは，今回取り上げる「Bツリー・インデックス」の構成要素と同じです。
ただし，書籍の索引とデータベースのBツリー・インデックスでは，構造がまったく異なります。書籍の索引はいわば単純な配列構造です。それに対してBツリー・インデックスは，樹木のような構造（木構造）になっています（図2左）。3層構造になっており，上位に位置するのが「ルート」，中間が「ブランチ」，下位に位置するのが「リーフ」です。レコード数が少ないとブランチが無かったり，逆にレコード数が多いとブランチが複数層になることがあります。ルート，ブランチ，リーフにはすべて（1）カラム値を含みます。
 |
| 図2●Bツリー・インデックスの構造 論理的には左のように3層構造で，ルートは一つである。物理的には右のように，ルート，ブランチ，リーフは別々のブロックに格納している [画像のクリックで拡大表示] |
レコードをディスクに格納するときはブロック注3単位になりますが，インデックスをディスクに格納するときもブロック単位になります。通常，ルート，ブランチ，リーフは，それぞれ別々のブロックに格納されます（図2右）。（2）レコードのポインタはリーフにのみ含み，ブランチにはリーフのポインタを，ルートにはブランチのポインタを含みます。
|
