InsightTechnology 旧ブログ

＜インデックスに関する検証 その2＞ ペンネーム つけまい

— インデックス利用の落とし穴
レンジ検索で全件検索よりも性能ダウン —

●インデックスの構造
実験結果に入る前に（ご存知の方も多いと思うが）、インデックスの基本構造
（B-Tree）について簡単に説明する。

インデックスは

のようなバランス・ツリーと呼ばれる構造をしている。ルート・ノードおよびブラン
チ・ノードには実際のインデックスキーの存在するリーフ・ブロックの先頭の
キーと共に、そのキーが格納されているブロックを指すデータ・ブロック・アド
レス (DBA)が入っている。また、実際のインデックスキーが入っているリーフ・
ブロックには、そのキーに対するレコードのROWIDがあり、これにより実際の
テーブルの物理的位置を特定している。この例では、それぞれのブランチの先
頭にキーが入っておらずデータ・ブロック・アドレス(DBA)だけが記述してあるが、
Oracleは下位ノードの先頭リーフ・ブロックのキーをあえて持っていない。こ
れは、2番目のDBAを指すキーの値よりも小さい値は、先頭のDBAに格納されること
を意味している。

【注釈】ROWID = 実際のデータが格納されている物理的な位置を表したもの

●リーフ分割が発生するタイミング

の図からもわかるようにリーフ・キーは昇順にならべられている。ここで各リーフが満杯状況である場
合を想定し、「新規の挿入によるレコード35はどこに入るか？」を

の図で説明すると・・

新規レコード35を1番目のリーフ・ブロックの30の下に挿入したいのだが、1番目
のブロックには空きがない。そこで、リーフ分割という現象が発生する。パフォ
ーマンスを無視すれば1番目以降のリーフ・データをずらしながらデータ35を1番
目のリーフ・ブロックに挿入する事も考えられるのだが、当然その様な事はしない。

上の図はリーフ分割を解説したものだが、レコード35は後に続くレコード40等といっしょに新しいリー
フ・ブロックを作ってしまう。これにより、新しいリーフあるいは分割されたリ
ーフには相当の空きが生じる可能性がある。この空きの量は、データの挿入さ
れる順番に大きく左右される。もし、データが昇順に挿入されていれば空き領
域は生まれないが、降順または飛び飛びに挿入されるとリーフ分割が多発する。
実際のシステムでは、データの挿入順など考慮していないのでリーフ分割を予
測する事などできない。

●インデックスは止まらない？
インデックスは、先に説明したようにルート、ブランチ、リーフと、3段階の過
程を経て目的とするレコードに到達する。しかし、これはあくまでもイコール
検索時の場合である。

一方のレンジ検索は、レコードに到達するまでの過程は同じだが、昇順に格納
されているという特性を利用して条件の到達点に達すると、そのブロックより
前（あるいは後へ）目的のブロックまでひたすら読み続けるという特性を持っ
ている。

今回の実験は、インデックス構造上の特性を、主にレンジ検索にスポットをあ
てて、実際にリーフ・ブロックをSkew（偏り）させて、「削除されたはずのイ
ンデックス・キーまで読んでしまう」という不可解な動きについての検証を試
みたものである。

初夏 茅ヶ崎にて

～インデックスに関する検証 その2～
by つけまい