日別アーカイブ: 2015年11月5日

B木とデータベース

前回の授業で、２分木の話の中にて構文木とかで複数の枝を持つデータ構造の話をしたので、今回はB木について説明

B木はデータベースに利用されているデータ構造であり、位数をNとした場合、１ノード内には、N個以上、2N未満のデータを持つ。また、data[i-1] < x < data[ i ] の条件を満たすデータは、pointer[ i ] で示すノードに保存する。

// B木のデータ構造の宣言例
#define SIZE 2
struct BTree {
   int  size ; // ノード内のデータ件数
   int  data[ SIZE * 2 ] ;
   struct BTree* pointer[ SIZE * 2 + 1 ] ;
} ;

B木では、ノードにデータを追加する場合には、ノードが2Nにならないのであれば、単純にそのノードにデータを追加する。追加してノード内データが2N個を越える場合には、追加後のデータ列の中央値を、上位ノードに移動させ、そのノードは中央値の前後の２つのノードに分割を行う。

こうすることにより、データ追加時に一方的に延びる不均一な構造を避けることができる。

このB木では、データを効率よく扱えるが、データベースシステムでは、目的の１件を探すだけでなく、条件に合ったデータの組合せを全データの中から探す処理も重要となる。

この全件処理は、2分木であれば、再帰処理などを伴いデータベースシステムには取り扱いが困難となる。そこで、全件をシーケンシャルにアクセスするための改良を施したB+木やB*木などを使う。

データベースシステムでは、データすべてを表形式で覚え、その表の組合せることで複雑なデータを表現するリレーショナルデータベースを使うことが多い。詳しくは、５年データベースの講義資料を参照。