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


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

このウェブサイトにぴったりのカップは僕たちのショップにあります。
#見た目もいい感じだし、ここでの僕の仕事を支えてくれています

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

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

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

プログラミング言語クラス名
Javajava.util.LinkedList
.NET FrameworkSystem.Collections.Generic.LinkedList
C++std::list

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

図1.1 インデックスリーフノードと対応するテーブルのデータ


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

Photo of Markus Winand
Markus Winand氏は、開発者がSQLパフォーマンスを改善するお手伝いをしています。 彼は、SQL Performance Explainedの 著者でもあり、出張トレーニングhttp://winand.at/での リモート講義も 行っています。