by Hayato Matsuura.

検索ツリー (Bツリー) がインデックスを高速に動作させる


インデックスリーフノードは、任意の順序で保存され、ディスク上の 保存場所は、インデックスの順序に従った論理的な場所とは関係ありません。 これは、ページの順序がバラバラの電話帳のようなものです。この場合、 「タナカ」を探そうとしてまず開いたページに「サトウ」があった時、 サトウの後にタナカがあるとは限らないことになります。データベースには、 バラバラに並ぶページ間を素早く検索できる別の構造が必要になります。 それが、バランス検索木、略してBツリーです。

図Bツリーの構造

は、 要素が30個あるインデックスの例を表しています。双方向連結リストによって、 リーフノード間の論理的な順序が表現されています。ルートノードとブランチ ノードによって、リーフノード間の素早い検索ができるようになっています。

左側は、ブランチノードと、それが指し示すリーフノードを拡大した 図です。各ブランチノードの中身は、それぞれのリーフノードの最大値です。 最初のリーフノードの最大値は46なので、ブランチノードの最初の要素も 46になっています。その他のリーフノードに関しても同様なので、ブランチ ノードの要素は46、53、57、83になっているというわけです。この方法に従って、 全てのリーフノードがブランチノードに含まれるように、ブランチノードの レイヤが作られていきます。

次のレイヤも同じように作られますが、最初のブランチノードのさらに上の レベルになります。この手順は、全てのキーが1つのノード、すなわち ルートノードに収まるまで続けます。この構造は、ルートノードからリーフノード までの深さがどこでも同じであることから、バランス検索木 と呼ばれます。

注記

Bツリーは、二分木(binary tree)ではなく、バランス木(balanced tree) です。

ひとたびインデックスが作られると、データベースはインデックスを 自動的にメンテナンスしていきます。全てのinsertdeleteupdateをインデックスに 適用し、ツリーの深さを同じに保ちます。このため、書き込みに関しては メンテナンスのオーバーヘッドがあります。 第8章, 「データの変更 では、この動作について詳しく説明しています。

図Bツリーの走査

は、 キー「57」の検索を表した、インデックスの一部です。ツリーの走査は図の 左側のルートノードから始まります。各エントリが、検索する値「57」以上 (>=)であるかどうかを確認します。この図では、エントリ83がそれに あたります。データベースは、対応するブランチノードへのポインタをたどり、 ツリーの走査がリーフノードに達するまで同じ手順を繰り返します。

重要

Bツリーは、データベースがリーフノードを高速に見つける のに役立ちます。

このツリーの走査は非常に効率的な処理なので、ここでは インデックスの強力さの1つ目としましょう。この仕組みは、 巨大なデータセットに対してもほとんど一瞬で処理できます。これは、ツリーの バランス構造が主な理由で、このために全ての要素に同じステップ数で到達 できます。さらに、ツリーの深さが対数的に増えるということも理由です。 つまり、リーフノード数の増加に比べ、ツリーの深さの増大は非常に遅いという ことです。実際には、数百万レコードのインデックスのツリーの深さは、4 あるいは5です。深さが6に達することはめったにありません。コラム 対数的スケーラビリティで、さらに詳しく 説明しています。

対数的スケーラビリティ

数学的には、与えられた底に対するある値の対数とは、その値を割り出す ために必要な累乗の回数、つまり指数のことです。[Wikipedia].

検索木において、底はブランチノード1つに保存されるエントリの数であり、 指数は木の深さになります。 の例では、 ノードあたり4つまでのエントリを持ち、木の深さは3なので、インデックスは 最大64(43)のエントリを保持できます。木の深さを1レベル増やす だけで、256(44)エントリを保持できるようになるのです。木の深さを 増やすたびに、インデックスの保持できるエントリ数は 4倍に増えていきます。対数はこの関数の逆関数に なるので、木の深さはlog4(インデックスのエントリ数)となります。

木の深さインデックスのエントリ数
364
4256
51,024
64,096
716,384
865,536
9262,144
101,048,576

対数的な数字の増加により、例のインデックスでは100万レコードを 10レベルの木で検索することができます。しかし、現実世界でのインデックスは これよりさらに効率的です。木の深さや検索のパフォーマンスに大きな影響を 及ぼすのは、各ノードに格納するエントリの数です。数学的に言えば、 この数が対数の底になります。底が大きければ、木の深さは浅くなり、木の走査も 高速になります。

データベースは、この仕組みを最大限に使い、通常、数百の単位で 可能な限り各ノードにエントリを格納します。つまり、新しいレベルを追加する ことで、数百倍多くのエントリを扱えるようになるわけです。

著者について

Markus Winandの写真

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

“Use The Index, Luke!” by Markus Winand is licensed under a Creative Commons Attribution-Noncommercial-No Derivative Works 3.0 Unported License.
法律上の通知 | 接触 | 無保証 | 商標 | Privacy | CC-BY-NC-ND 3.0 license