インデックスリーフノードは、任意の順序で保存され、ディスク上の 保存場所は、インデックスの順序に従った論理的な場所とは関係ありません。これは、ページの順序がバラバラの電話帳のようなものです。この場合、 「タナカ」を探そうとしてまず開いたページに「サトウ」があった時、サトウの後にタナカがあるとは限らないことになります。データベースには、 バラバラに並ぶページ間を素早く検索できる別の構造が必要になります。 それが、バランス検索木、略してBツリーです。
図1.2Bツリーの構造
図1.2は、要素が30個あるインデックスの例を表しています。双方向連結リストによって、 リーフノード間の論理的な順序が表現されています。ルートノードとブランチ ノードによって、リーフノード間の素早い検索ができるようになっています。
左側は、ブランチノードと、それが指し示すリーフノードを拡大した 図です。各ブランチノードの中身は、それぞれのリーフノードの最大値です。最初のリーフノードの最大値は46なので、ブランチノードの最初の要素も 46になっています。その他のリーフノードに関しても同様なので、ブランチ ノードの要素は46、53、57、83になっているというわけです。この方法に従って、 全てのリーフノードがブランチノードに含まれるように、ブランチノードのレイヤが作られていきます。
協力してください
この記事が気に入ったら、私の書いた本「SQLパフォーマンス詳解」や私によるトレーニングもきっと気にいるはず。
次のレイヤも同じように作られますが、最初のブランチノードのさらに上の レベルになります。この手順は、全てのキーが1つのノード、すなわちルートノードに収まるまで続けます。この構造は、ルートノードからリーフノード までの深さがどこでも同じであることから、バランス検索木と呼ばれます。
注記
Bツリーは、二分木(binary tree)ではなく、バランス木(balanced tree)です。
ひとたびインデックスが作られると、データベースはインデックスを
自動的にメンテナンスしていきます。全てのinsert、delete、updateをインデックスに適用し、ツリーの深さを同じに保ちます。このため、書き込みに関しては
メンテナンスのオーバーヘッドがあります。第8章8, 「データの変更」
では、この動作について詳しく説明しています。
図1.3Bツリーの走査
図1.3は、キー「57」の検索を表した、インデックスの一部です。ツリーの走査は図の 左側のルートノードから始まります。各エントリが、検索する値「57」以上(>=)であるかどうかを確認します。この図では、エントリ83がそれに あたります。データベースは、対応するブランチノードへのポインタをたどり、ツリーの走査がリーフノードに達するまで同じ手順を繰り返します。
重要
Bツリーは、データベースがリーフノードを高速に見つけるのに役立ちます。
このツリーの走査は非常に効率的な処理なので、ここでは インデックスの強力さの1つ目としましょう。この仕組みは、 巨大なデータセットに対してもほとんど一瞬で処理できます。これは、ツリーのバランス構造が主な理由で、このために全ての要素に同じステップ数で到達 できます。さらに、ツリーの深さが対数的に増えるということも理由です。つまり、リーフノード数の増加に比べ、ツリーの深さの増大は非常に遅いという ことです。実際には、数百万レコードのインデックスのツリーの深さは、4あるいは5です。深さが6に達することはめったにありません。コラム「対数的スケーラビリティ」で、さらに詳しく説明しています。
