Delphiアルゴリズムトレーニング

第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

icon B木とは何か

 B木はAVL木と同様なバランス木の一種です。AVL木では各節点にキーがあり、そのキーに対する大小で左右への振り分けを行っていくというルールでした。B木では、節点に複数のキーを格納できます(これをバケットと呼びます)。新たな要素は、それぞれのキーに対して大きいのか、あるいは小さいのかを比較して子の節点へ振り分けられていきます。

●B木(2次のB木)
B木
B木は多分木、つまり1つの節点に2を超える子節点をもつ木構造であり、またバランス木である

 B木がバランスを保って保持されるためには以下のルールが守られる必要があります。これをK次のB木といいますが、ちょっと直感的ではないですね。

  1. 各節点は最大で2×K個のキーを保持する
  2. 根節点以外の各節点は、最小でK個のキーを保持する
  3. M個のキーを持つ節点はM+1個の子を持つ
  4. 葉はすべて同じレベルになる

 B木で値を検索する場合、ルートから行きがかり順でたどっていきます。まず、ルートの一番小さいキーから見始めて、検索値よりも大きな値が見つかったら、その左側の子の節点へと検索対象を移します。

 検索値よりも大きな値が見つからない場合は、キーの最大値の右側の子を検索対象としてツリーを下っていきます。この順序で探していって、最終的にnilになっている節点を訪ねあてたら検索値はなかったということになります。

icon B木の成長

 値が何も入っていない状態から、B木が成長していく様子を見てみましょう。まず、ルートのバケットがいっぱいになるまではキーをソートしながら、バケットに値を追加していきます。

B木の成長1

 バケットがいっぱいになっているところへ新たな値の追加があるとバケットの分割が発生します。この図では、バケットには4つの値が入りますから、5つ目の値が追加された時点でその中央値を新しい親節点の一番左へ追加して、2つの子節点にそれぞれ2個づつのキーを格納した上で、ポインタでリンクさせます。

B木の成長2

 2の条件を満たしているのが分かりますね。ルート以外にはちゃんと2個のキーが格納されています。

 さらに、右側の節点に格納される値をどんどん追加していくと、今度は右側の子節点でバケットの分割が発生します。中央値を親節点であるルートへ格納して、分割された子節点の大きい方をルートに追加したキーの右側にあたる位置でポインタでリンクさせます。

B木の成長3

 同じように値を追加していくとどんどん分割が発生します。

B木の成長4

 このまま値を追加していくと、今度はルートのバケットがいっぱいになってしまいます。そうするとルートの分割が再度発生して、ルートにはキーが1つだけという状態で、ツリーが一段高くなります。これはツリーの生成後の状態で発生するルートの分割と同じ動作になります。

 
1/3
next

Index
RDBMSで使われるB木を学ぼう
Page1
B木とは何か
B木の成長
  Page2
B木への要素の追加(葉の場合)
B木への要素の追加(葉でない場合)
B木の実装の工夫
  Page3
B木のテストプログラム
  Appendix
BTree.pasのソースコード

index 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の世界を体験してみよう
  Coding Edgeフォーラムフィード  2.01.00.91


Coding Edge フォーラム 新着記事
@ITメールマガジン 新着情報やスタッフのコラムがメールで届きます(無料)

注目のテーマ

>

Coding Edge 記事ランキング

本日 月間