索引の構造

データベース・マネージャーは、 索引の保管に B+ ツリー構造を使用します。

B+ ツリーには、図 1 に示されているように、いくつかのレベルがあります。ここで「rid」はレコード ID (RID) を意味します。

図 1. B+ ツリー索引の構造

トップレベルはルート・ノード と呼ばれます。 最下位レベルはリーフ・ノード で構成され、ここに索引キー値と、対応するデータが入っている表の行へのポインターが保管されます。 ルート・ノードとリーフ・ノードの間のレベルは、中間ノード と呼ばれます。

特定の索引キー値を検出するとき、索引マネージャーは、 ルート・ノードから開始して、その索引ツリーを検索します。 ルート・ノードには、その次のレベルにある (中間) ノードごとに 1 つのキーがあります。 それらの各キーの値は、 その次のレベルの対応するノードに存在する最大のキー値です。 例えば、図に示すように、索引に 3 つのレベルがあるとします。 特定の索引キー値を検出するために、索引マネージャーは、ルート・ノードから、検索キー値以上のキー値のうちの最初のものを検索します。 ルート・ノード・キーは特定の中間ノードを指しています。 索引マネージャーは必要とする索引キーを持つリーフ・ノードが見つかるまで、各中間ノードでこの手順を行います。

図 1 で検索しているキーは「I」であるとします。 ルート・ノードの中で、「I」以上の最初のキーは「N」です。 これはその次レベルの真ん中のノードを指しています。 その中間ノードで「I」以上の最初のキーは「L」です。 これは「I」の索引キーとそれに対応する RID が見つかる特定のリーフ・ノードを指しています。 その RID は基本表内の対応する行を識別します。

リーフ・ノード・レベルには直前のリーフ・ノードへのポインターが入っている場合もあります。 こうしたポインターによって、 索引マネージャーはどちらの方向にでもリーフ・ノードをスキャンして、範囲内の 1 つの値を見つけた後、 値の範囲を検索することができます。 いずれの方向にもスキャンを実行する機能は、ALLOW REVERSE SCANS オプションを使用して索引が作成された場合にのみ使用可能です。

マルチディメンション・クラスタリング (MDC) 表または挿入時クラスタリング (ITC) 表の場合、表のために指定したクラスタリング・ディメンションごとにブロック索引が自動的に作成されます。 複合ブロック索引も 1 つ作成されます。 この索引の中には表のディメンションに関係した列ごとのキーの部分が含まれます。 それらの索引には RID ではなく、ブロック ID (BID) へのポインターが含まれ、データ・アクセスを改善します。

索引のリーフ・ページで RID ごとに保存される 1 バイトの ridFlag は、論理的に削除されたとして RID にマークを付け、後で物理的に除去できるようにする目的で使用されます。 更新または削除操作のコミット後、削除済みとマークされたキーは除去できます。 索引内のそれぞれの可変長列について、追加の 2 バイトで列の値の実際の長さを保管します。