Top / B木

B木

目次 †

B木 †

　B木（B-tree）とは、バランス木の一種である。葉だけが値を持ち、葉以外の節は値を持たずキーだけを持っている。キーは、ポインタで示す値やその子の持つ値の範囲を示すものである。

　多分木に一定の制約条件を付けて、AVL木と同じようにデータの追加・削除に伴なう、木のアンバランスを避けたデータ構造として使われる。

B木の制約条件 †

• 各節点（葉以外）の子の数は、最大m個である。
• 各節点（葉以外）の子の数は、最小↑m/2↑である。ここで「↑○↑」は○の小数第1位を切り上げて整数化した値を意味する。ただし、根の子の数は最小2個である。
• 根から葉までの深さは、どの葉についても等しい。

B木とデータ構造 †

　B木は葉以外の節点には、データ検索のためのキーとポインタだけを入れて、データは葉だけに入れるという方法がよく取られる。例えば、ファイル編成の一種であるVSAM（仮想記憶編成ファイル）、データベースの索引構造などでよく利用されている。

参考文献 †

• 『ソフトウェア開発技術者　午前対策（基礎編）　テキスト』
• 『ソフトウェア開発技術者試験対策　コンピュータサイエンス補足資料＋午後演習問題』