by Hayato Matsuura.

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


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

協力してください

この記事が気に入ったら、私の書いた本「SQLパフォーマンス詳解」や私によるトレーニングもきっと気にいるはず。

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

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

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

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

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

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

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

著者について

Markus Winandの写真

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

彼の本

カバー『SQLパフォーマンス詳解』

核心をわかりやすく 解説。

Markusから購入します
(送料無料+PDF)

Amazonで購入
(印刷版のみ)

Do not use offset for pagination

Learn why

Visit my sibling!A lot changed since SQL-92!

Use The Index, Luke のカップは

ステッカー、コースター、本、コーヒーマグ。 学習に必要なものすべて。

今すぐ購入

Connect with Markus Winand

Markus Winand on LinkedInMarkus Winand on XINGMarkus Winand on Twitter
“Use The Index, Luke!” by Markus Winand is licensed under a Creative Commons Attribution-Noncommercial-No Derivative Works 3.0 Unported License.
法律上の通知 | お問い合わせ | 無保証 | 商標 | プライバシーとGDPR | CC-BY-NC-ND 3.0 license