by Hayato Matsuura.

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


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

図Bツリーの構造

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

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

協力してください

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

次のレイヤも同じように作られますが、最初のブランチノードのさらに上の レベルになります。この手順は、全てのキーが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/での リモート講義も 行っています。

彼の本

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

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

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

Amazonで購入
(印刷版のみ)

“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