B木(B-tree)
- m分木
節が最大m個(m≧2)の子を持つ木構造
- B木
m分探索木のうち、以下の条件を満たすもの
- 根は、葉であるか、あるいは2～m個の子をもっている
- 根、葉意外の節は、m/2～m個の子をもつ
- 根からすべての葉までの経路の長さが等しい
例）５階のB木の場合、内部節は3～5個の子を持てる この性質から、木を常にバランスがとれた状態に保つ
※B木ではデータを持つのは葉のみ、内部節はキーのみをもつ
B木の節はm個の子と、m-1個の「境目を表す値」を持つ。
- 「境目を表す値」＝ 右の部分木の最小値
B木の計算量
- 探索：O(log n)
- 挿入：O(log n)
- 削除：O(log n)