インデックスで検索を高速にする
ここまでの説明でおわかりのように，一般にテーブル内のレコードがディスク上に格納される順序は，レコードを追加する順序やページに空きがあるかどうかなどに左右され，特定のキーの順番に並んでいるわけではありません。そのため例えば，従業員テーブル（emp）から従業員番号（eno）が71であるレコードを抽出するSQL文である
SELECT * FROM emp WHERE eno = 71
のような単純な検索処理でも，テーブル内のすべてのレコードを一つずつ調べていかなくてはなりません。これではレコード数が膨大な場合に大変な時間がかかってしまいます。そこで，こうした特定のキーに対する検索を高速化するために用意されている仕組みがインデックス（索引）です。インデックスの基本的な考え方は，書籍の索引と同じです。例えば，書籍の中から「テーブル」というキーワードを検索する場合，あいうえお順に並んだ索引でまず「て」の位置を探し，「テーブル」が見つかったら対応する位置（ページ）を調べて本文を参照する，という手順を踏んだほうが，本文を先頭から順に探すよりもはるかに速く探すことができますね。データベースのインデックスも，書籍の索引と同様に，キーの値とその値を持つレコードの位置の組をキーの順に格納したものです。
ただ，これらの組を書籍の索引のように単に1列に並べてディスク上に格納してしまうと，インデックスからキーを検索する処理自体に時間がかかるため，あまり効率がよくありません。そこで，多くのRDBMSでは検索効率を上げるために，インデックスを「Bツリー」と呼ぶデータ構造で格納しています。
Bツリーは，文字通りツリー（木）状の構造を持ち，各ノードには一定の個数のキーとポインタ（位置情報）のペアを格納しています（図7[拡大表示]）。最下層のノードをリーフ・ノード，一番上のノードをルート・ノード，その間の層のノードをブランチ・ノードと呼びます。ブランチ・ノードは図では1階層ですが，多階層にすることも可能です。一般に，レコードの数が多くなると，それにつれてブランチ・ノードの階層が深くなります。ただ，一般的なページ・サイズとレコード数では，Bツリーの階層はせいぜい3～4階層にしかならないと考えていいでしょう。
次にノードの中身について見てみましょう。各ノードのエントリであるキーとポインタ（位置情報）のペアは，キーの値の昇順もしくは降順で並んでいます。これらのエントリはそれぞれ，そのノードの子に相当するノードと1対1に対応し，子ノードの左端のキーの値と，子ノードを指すポインタを格納します。ノードの最終階層であるリーフ・ノードのエントリには，各レコードのキーの値とレコードの位置を格納します。Bツリー・インデックスの場合は，さらにリーフ・ノードの間，およびブランチ・ノードの間を，双方向のポインタでリンクしておくのが一般的です。
各ノードの最大サイズは，通常，ページ・サイズと同じで，1ページに1ノードが格納されます。したがってページ・サイズが大きいほど多数のエントリを格納できます。テーブルに含まれるレコード数が一つのノードに格納できる最大エントリ数より少ないときは，ルート・ノードのみが存在してルート・ノードからデータベース・レコードを直接指します。
Bツリー・インデックスは範囲検索にも有効
Bツリー・インデックスを利用したレコード検索では，二分探索＊21を行いながらルート・ノード，ブランチ・ノード，リーフ・ノードとたどって，レコードの位置情報（ポインタ）を取得します。例えば，図7でキー71を探したいとします。その場合，まずルート・ノードを二分探索してキー71を探します。71は63より大きく，87よりも小さいので，キー63から始まるブランチ・ノードを探せばよいことがわかります。
このブランチ・ノードを調べると，69＜71＜81なので，キー71はキー69から始まるリーフ・ノードに含まれることがわかります。最後にこのリーフ・ノードでキー71のエントリが見つかれば，そのポインタを使ってレコードにアクセスできます。リーフ・ノードのエントリはデータベースのレコードと1対1に対応するため，リーフ・ノードに該当エントリが存在しない場合はデータベース中にレコードが存在しないことになります。
Bツリー・インデックスは昇順または降順に並んでいるため，範囲検索にも使うこともできます。例えば，先ほどの従業員テーブル（emp）で従業員番号（eno）が71より大きく83より小さいレコードを探すために，図7のインデックスで
SELECT * FROM emp
WHERE eno ＞ 71 AND eno ＜ 83
を実行する場合，最初は先ほどと同様にキー71に対してルート・ノード→ブランチ・ノード→リーフ・ノードと順に検索して71を超える最小のキーを探し出します。あとはそのリーフ・ノードのエントリをキーが83以上になるまで順に取り出していくだけで，求めるレコードすべてにアクセスできます。
各リーフ・ノードは次のリーフ・ノードへのポインタを持っています。したがって，検索するキーが複数のリーフ・ノードにまたがって格納されているような場合でも，ブランチ・ノードに戻る必要はありません。
このほか，SQL文に“ORDER BY”を指定して結果をキーの順にソートしたい場合に，別にソート処理を行う必要がないのもメリットです。リーフ・ノードのエントリの順にレコードを取り出すことで自動的に結果がキーの順にソートされるからです。
レコードを追加しても検索性能は安定している
レコード内のあるフィールドに対してインデックスを作成した場合，レコードの追加や削除といった更新系の処理をしたら，レコード自体だけでなくインデックスの内容も更新する必要があります。レコードを追加する場合は，先の検索の場合と同じようにルート・ノードから順にたどってエントリを追加するリーフ・ノードを探し出します。ノードに空きがあるなら，昇順または降順の順序を守ってエントリを追加するだけでインデックスの追加は終了します。
一方，ノードに空きがないときは，新たにノードを追加して空きエントリを作らなくてはなりません。この場合は，新たにページを割り当ててリーフ・ノードを作成し，現在のノードの前もしくは後ろ半分のエントリを作成したノードに移動します（図8[拡大表示]）。このように，一つのノードを二つに分割する操作をインデックス・スプリットと呼びます。インデックス・スプリットの結果，インデックスのエントリのデータがページ全体に占める割合はほぼ半分程度になります。
インデックス・スプリットではさらに，新たに作成したノードを指すポインタを，上位のノードのエントリに追加しなければなりません。この上位ノードにも空きがない場合には，さらにインデックス・スプリットが発生することになります。
ルート・ノードがエントリでいっぱいになったら，上位に新しいルート・ノードを作成します。この場合，自分自身はブランチ・ノードになり，さらにインデックス・スプリットでもう一つブランチ・ノードを作成します。ただし，物理的にはルート・ノードは以前のものをそのまま使用し，新たに二つのブランチ・ノードを作成します。これはルート・ノードのアドレスがデータベースの管理情報領域で多用されているため，これを変更するのは影響が大きいからです。
インデックス・スプリットでは，ルートがスプリットするケースを除けばルート・ノードからリーフ・ノードまでの距離（階層の数）は変化しません。このためレコードを追加した場合でも，検索に要する時間が安定しているのもBツリーの特徴です。
レコードを大量に削除したらインデックスを再構築する
インデックス・エントリを削除する場合は，最初に該当エントリをルート・ノードから順にたどって検索し，該当するリーフ・ノードを見つけてそのエントリを削除します。リーフ・ノードの左端の値は，その親となるブランチ・ノードのエントリにも格納されています。したがって，左端のエントリを削除した場合は親ノードのエントリを新しい左端の値で書き換えなくてはならないように思えますが，実際にはその必要はありません。親ノードのエントリに格納した値がリーフ・ノードの左端の値よりも小さいという条件を満たす限り，検索に影響が出ないからです。
リーフ・ノードのエントリの削除を繰り返して，隣接するリーフ・ノードのサイズがともに50％を下回るようになった場合でも，隣接するリーフノードをまとめて一つのページにする（マージする）のは行わないのが普通です。削除のたびにノードのサイズをチェックしていては時間がかかりますし，インデックスの追加と削除を繰り返す場合にはスプリットとマージが連続的に発生してパフォーマンスが大幅に悪化するという問題があるからです＊22。
これからわかるように，レコードを大量に追加していったんブランチ・ノードの階層が増えてしまうと，後でレコードを削除してもそれが減ることはほとんどありません。すなわち，リーフ・ノードに到達するまでのディスク入出力の回数がいったん増えてしまうと，減ることはありません。このため，データを大量に削除した場合は，インデックスを再構築して適切な構造を保つようにしたほうが良いこともあります。
レコードを更新する際は，インデックスとして使われているフィールドの値が変わらない場合には，当然ですがインデックスの書き換えは必要ありません。インデックスとして使われているフィールドの値が変わる場合は，インデックスの削除と追加が一連の処理として実行されると考えればよいでしょう。
加藤 比呂武（かとうひろむ） |
