インデックスリーフノード

インデックスの最も重要な目的は、インデックスを張ったデータに対して順序をつけてアクセスできるようにすることです。実際のところ、 insert文がデータを挿入する際にデータを順番に並べていく のは、そのデータに続く要素を全て後ろにずらして場所を空ける必要があるため、 ほとんど不可能です。大量のデータを動かすのは、非常に時間のかかる処理なので、insert文が非常に遅くなってしまうのです。この問題への 対策として、メモリ上の物理データの並び順とは独立して、論理的な順序付けを作るわけです。

論理的な順序付けは、双方向連結リストで作ります。各ノードは、隣り合う エントリと鎖のようにつながります。新しいノードは、既存の2つのノードの間に、それぞれから参照される形で挿入されます。この双方向連結リストが論理的な 順序付けを維持してくれるので、新しいノードの物理的位置を気にする必要はありません。

各ノードが、前のノードと後に続くノードを参照する仕組みになっているので、 このようなデータ構造を双方向連結リストといいます。これにより、データベースはインデックスを必要な時に 前後に読み進められるようになります。また、大量のデータを動かさずに、ポインタを変更するだけでデータを挿入できるようになります。

双方向連結リストは、多くのプログラミング言語で、コレクション(コンテナ)を実装するのにも使われています。

データベースは、いわゆるインデックスリーフノードを連結するのに、双方向連結リストを 使います。各リーフノードは、データベースブロック あるいはページと呼ばれる、データベースが扱える最小の 格納単位に保存されます。全てのインデックスブロックは同じサイズになっていて、 一般的には数KBです。データベースは、各ブロック内のスペースを可能な限り使い、 インデックスのエントリを詰め込めるだけ詰め込みます。つまり、インデックスの順序は、各リーフノード内の順序と、双方向連結リストでつながれた各リーフ ノード同士の順序の、2つのレベルで管理されていることになります。

図1.1 は、インデックスリーフノードと、そこからテーブルのデータへの接続状態を表しています。インデックスの各エントリは、インデックスを張ったカラム (キー、ここではカラム2)と、対応するテーブルの行への参照(ROWIDまたはRIDから参照)。インデックスと違って、テーブルのデータ自体はヒープ構造で 保存されており、ソートはされません。同じテーブルブロックに保存されている 行同士は何の関係もなく、同様に、ブロック同士も関連はありません。