第5回 RDBMSで使われるB木を学ぼう
はやしつとむ
アナハイムテクノロジー株式会社
2009/6/22
オブジェクト指向によって、アルゴリズムは隠ぺいされていることが多くなった。しかし、「用意されていない処理」が求められたときに対応できるだろうか（編集部）
第3回「AVL木で木構造を学ぼう」、第4回「もっとAVL木で木構造を学ぼう」と2回連続でAVL木について解説しました。
今回はAの後だからBというわけではありませんが、B木（B-Tree）を取り上げます。
B木の変種であるB+木やB*木は、OracleやPostgreSQL、Firebirdなどのリレーショナルデータベースでインデックスとして利用されている、メジャーな木構造です。
筆者はDelphi 2009でサンプルプログラムを作成していますが、Delphiをお持ちでない方は下記のURLからTurboDelphiをダウンロードして、インストールしてみてください。
| 関連リンク： | |
 |
Delphiトライアル版／無償バージョン http://www.codegear.com/jp/downloads/free/delphi |
B木とは何か
B木はAVL木と同様なバランス木の一種です。AVL木では各節点にキーがあり、そのキーに対する大小で左右への振り分けを行っていくというルールでした。B木では、節点に複数のキーを格納できます（これをバケットと呼びます）。新たな要素は、それぞれのキーに対して大きいのか、あるいは小さいのかを比較して子の節点へ振り分けられていきます。
B木がバランスを保って保持されるためには以下のルールが守られる必要があります。これをK次のB木といいますが、ちょっと直感的ではないですね。
- 各節点は最大で2×K個のキーを保持する
- 根節点以外の各節点は、最小でK個のキーを保持する
- M個のキーを持つ節点はM＋1個の子を持つ
- 葉はすべて同じレベルになる
B木で値を検索する場合、ルートから行きがかり順でたどっていきます。まず、ルートの一番小さいキーから見始めて、検索値よりも大きな値が見つかったら、その左側の子の節点へと検索対象を移します。
検索値よりも大きな値が見つからない場合は、キーの最大値の右側の子を検索対象としてツリーを下っていきます。この順序で探していって、最終的にnilになっている節点を訪ねあてたら検索値はなかったということになります。
B木の成長
値が何も入っていない状態から、B木が成長していく様子を見てみましょう。まず、ルートのバケットがいっぱいになるまではキーをソートしながら、バケットに値を追加していきます。
バケットがいっぱいになっているところへ新たな値の追加があるとバケットの分割が発生します。この図では、バケットには4つの値が入りますから、5つ目の値が追加された時点でその中央値を新しい親節点の一番左へ追加して、2つの子節点にそれぞれ2個づつのキーを格納した上で、ポインタでリンクさせます。
2の条件を満たしているのが分かりますね。ルート以外にはちゃんと2個のキーが格納されています。
さらに、右側の節点に格納される値をどんどん追加していくと、今度は右側の子節点でバケットの分割が発生します。中央値を親節点であるルートへ格納して、分割された子節点の大きい方をルートに追加したキーの右側にあたる位置でポインタでリンクさせます。
同じように値を追加していくとどんどん分割が発生します。
このまま値を追加していくと、今度はルートのバケットがいっぱいになってしまいます。そうするとルートの分割が再度発生して、ルートにはキーが1つだけという状態で、ツリーが一段高くなります。これはツリーの生成後の状態で発生するルートの分割と同じ動作になります。
1/3 |
 |
| Index | |
| RDBMSで使われるB木を学ぼう | |
 |
Page1 B木とは何か B木の成長 |
| Page2 B木への要素の追加（葉の場合） B木への要素の追加（葉でない場合） B木の実装の工夫 |
|
| Page3 B木のテストプログラム |
|
| Appendix BTree.pasのソースコード |
|
 |
Delphiアルゴリズムトレーニング |
| Coding Edgeお勧め記事 |
 |
いまさらアルゴリズムを学ぶ意味 コーディングに役立つ！ アルゴリズムの基本（1） コンピュータに「3の倍数と3の付く数字」を判断させるにはどうしたらいいか。発想力を鍛えよう |
|
Zope 3の魅力に迫る Zope 3とは何ぞや？（1） Pythonで書かれたWebアプリケーションフレームワーク「Zope 3」。ほかのソフトウェアとは一体何が違っているのか？ |
|
貧弱環境プログラミングのススメ 柴田 淳のコーディング天国 高性能なIT機器に囲まれた環境でコンピュータの動作原理に触れることは可能だろうか。貧弱なPC上にビットマップの直線をどうやって引く？ |
|
Haskellプログラミングの楽しみ方 のんびりHaskell（1） 関数型言語に分類されるHaskell。C言語などの手続き型言語とまったく異なるプログラミングの世界に踏み出してみよう |
|
ちょっと変わったLisp入門 Gaucheでメタプログラミング（1） Lispの一種であるScheme。いくつかある処理系の中でも気軽にスクリプトを書けるGaucheでLispの世界を体験してみよう |
フィード 2.0／1.0／0.91
- プログラムの実行はどのようにして行われるのか、Linuxカーネルのコードから探る （2017/7/20）
C言語の「Hello World！」プログラムで使われる、「printf()」「main()」関数の中身を、デバッガによる解析と逆アセンブル、ソースコード読解などのさまざまな側面から探る連載。最終回は、Linuxカーネルの中では、プログラムの起動時にはどのような処理が行われているのかを探る - エンジニアならC言語プログラムの終わりに呼び出されるexit()の中身分かってますよね？ （2017/7/13）
C言語の「Hello World！」プログラムで使われる、「printf()」「main()」関数の中身を、デバッガによる解析と逆アセンブル、ソースコード読解などのさまざまな側面から探る連載。今回は、プログラムの終わりに呼び出されるexit()の中身を探る - VBAにおけるFileDialog操作の基本＆ドライブの空き容量、ファイルのサイズやタイムスタンプの取得方法 （2017/7/10）
指定したドライブの空き容量、ファイルのタイムスタンプや属性を取得する方法、FileDialog／エクスプローラー操作の基本を紹介します - さらば残業！ 面倒くさいエクセル業務を楽にする「Excel VBA」とは （2017/7/6）
日頃発生する“面倒くさい業務”。簡単なプログラミングで効率化できる可能性がある。本稿では、業務で使うことが多い「Microsoft Excel」で使えるVBAを紹介する。※ショートカットキー、アクセスキーの解説あり
 |
|
|
|
|
注目のテーマ
Coding Edge 記事ランキング
転職／派遣情報を探す
