ホーム » スタッフ » 斉藤徹 » B木の説明

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

最近の投稿(電子情報)

アーカイブ

カテゴリー

B木の説明

2分木の応用ということで、式の表現などの説明を行ったが、 3項演算子などがでてくると、2本の木という枠からはずれてくる。 この延長として、B木の解説を行う。

B木の基本は、N-1個のデータd[]と、N個のポインタp[]から成り、 di-1と、diの間の値は、i番目の枝piの先に保存する方法。(以下の図はWikipediaより引用)

// BTreeの宣言の例
#define SIZE 5
struct BTree {
int  size ;                  // 1つのノード内のデータ数
int  data[ SIZE - 1 ] ;      // ノード内のデータ
struct BTree* next[ SIZE ] ; // 次のBTreeへのポインタ
} ;

実際のプログラムの概念を説明し、実コードは示さなかったが、 ノード内の検索などを説明する。

B木は、広く利用されており、データベースエンジンでは、B木を拡張した、 B+ などを利用している。

データベースの説明の延長として、最近普及しているOracle,MySQL,PostgreSQLなどの 事例を紹介したり、Linux+Apache+MySQL+PHP(LAMP)などの用語を簡単に紹介する。