探索/B木 - nkym_memo @ ウィキ

B木(B-tree)

• m分木 節が最大m個(m≧2)の子を持つ木構造

• B木 m分探索木のうち、以下の条件を満たすもの

1. 根は、葉であるか、あるいは2〜m個の子をもっている
2. 根、葉意外の節は、m/2〜m個の子をもつ
3. 根からすべての葉までの経路の長さが等しい

例）５階のB木の場合、内部節は3〜5個の子を持てる
　　　この性質から、木を常にバランスがとれた状態に保つ

※B木ではデータを持つのは葉のみ、内部節はキーのみをもつ B木の節はm個の子と、m-1個の「境目を表す値」を持つ。

• 「境目を表す値」＝ 右の部分木の最小値

B木の計算量

• 探索：O(log n)
• 挿入：O(log n)
• 削除：O(log n)