ホーム » スタッフ » 斉藤徹 » B木とデータベース

2015年11月
« 10月   12月 »
1234567
891011121314
15161718192021
22232425262728
2930  

最近の投稿(電子情報)

アーカイブ

カテゴリー

B木とデータベース

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

B木

B木はデータベースに利用されているデータ構造であり、 位数をNとした場合、1ノード内には、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個を越える場合には、 追加後のデータ列の中央値を、上位ノードに移動させ、そのノードは中央値の前後の2つのノードに分割を行う。

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

データベースシステム

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

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

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