パフォーマンス劣化はインデックスのせいなのか!? をみっちり検証：おら! オラ! Oracle再検証 ＠IT出張所（1）（2/4 ページ）

本連載は、インサイトテクノロジーが発行しているメールマガジン「おら！オラ！ Oracle どっぷり検証生活」で過去に取り上げたテーマを、最新のバージョンや新しい切り口で再検証してみようという企画です。最初に取り上げるテーマは、メルマガの歴史の中でも最も古いテーマであるインデックス検証（B-Treeインデックスのパフォーマンス劣化に関する検証）についてです。

[内山義夫，株式会社インサイトテクノロジー]

インデックスの構造

　では、データはどのようにインデックス内に格納されているのでしょうか？

　Oracleでは、データをただ小さい順に並べているわけではなく、いくつかの小さな塊にしてインデックスという大きな箱の中に格納しています。この小さな塊を「ブロック」といいます。そして、その小さい塊に何が格納されているかを別の小さな塊で管理しています。

ブランチブロックとリーフブロック

　具体的には、1から10000までの値が1つずつある項目にインデックスが付いているとします。

　このブロックには100個分の値しか格納できないとすると、ブロックは全部で100個存在することになります。この状態ではどのブロックにどのような値が格納されているかが分かりません。そこで、別のブロックを用意し、そこにこのブロックの情報を入れて管理しています。その情報とは100個のブロックの最小値になります。

　このとき、管理しているブロックを「ブランチブロック」と呼びます。値が格納されているブロックは「リーフブロック」と呼びます。ブランチブロックには、リーフブロック1：1、リーフブロック2：101、リーフブロック3：201……リーフブロック100：9991、というように100個の値が格納されていることになります（図1）。値を参照するときは、ブランチブロックを参照した後にリーフブロックを参照して目的の値を取得しています。

図1　ブランチブロックとリーフブロック によるデータ格納と参照

1対では格納できない場合

　ちなみに、このインデックスに10001という値が追加された場合、ブランチブロックにはすでに100個の値が格納されているので、101個目を格納できません（図2）。

図2　101個目の値が格納できない

　このような場合、ブランチブロック2を新たに追加してそのブロックの中に10001という値を格納します。ただし、ブランチブロックが2つになってしまうと、値を参照しようとしたときに両方のブランチブロックを参照しなければならなくなってしまいます。

ルートブロックを頂点とした管理

　そこで、2つのブランチブロックを管理するための新たなブランチブロック3を作成します。今回の例でいうと、1という値と10001という値を格納したブランチブロック3が作成されたことになります（図3）。

図3　2つのブランチブロックを管理するブランチブロックが追加される

　このように、インデックス内では常に1つのブランチブロックを頂点にして値を管理しております。この頂点にあるブランチブロックのことを「ルートブロック」と呼びます。

　ちなみに、ブランチブロック3はブランチブロック1、2を管理していて、ほかのブランチブロックと階層が異なっています。このような階層のことをレベルと呼びます。ブランチブロック1、2はレベル1、ブランチブロック3はレベル2となります。下の階層をレベル1と呼んでいるのは、ブロックが増えた時に上に新たな階層が増えていくことを考慮しているようです。

リーフブロック分割の方法はどうなっている？

　では、ここで問題です。

　1から10000までの値が格納されているテーブルにその間の値――例えば2という値を新たに追加した場合、インデックスはどうなってしまうでしょうか？ ユニークキーだとエラーになってしまいますので、ユニークキーでないことが前提です。

いっぱいのブロックに小さな値を追加したらどう動く？

　2という値はリーフブロック1に格納されていますが、1と2の値の間に格納されるのでしょうか？ リーフブロック1はすでにブロックいっぱいに格納されています。ということは、最大値である100の値をリーフブロック2に移動するのでしょうか？

　そうすると、リーフブロック2もいっぱいなので、200という値をリーフブロック3にずらして……というように、すべてのリーフブロックの値を1つずつずらしていくということなのでしょうか？

　正解は、実際の環境で確認してみることにしましょう。