B- 树
一棵 m(m≥3) 阶的 B- 树是满
足如下性质的 m 叉树:
(1) 每个结点至少包含下列数据域:
(n , P
0
, K
l
, P
1
, K
2
,…, K
i
, P
i
)
n 为关键字总数
K
i
(1≤i≤n) 是关键字,关键字序列递增有序: K
1
<K
2
<…
<K
i
。
P
i
(0≤i≤n) 是孩子指针。对于叶结点,每个 P
i
为空指针。
keys(P
0
)<K
1
<keys(P
1
)<K
2
<…<K
i
<keys(P
i
)
(2) 所有叶子是在同一层上,叶子的层数为树的高度 h 。
(3) 每个非根结点中所包含的关键字个数 j 满足:
(4) 若树非空,则根至少有 1 个关键字,故若根不是叶子,则
它至少有 2 棵子树。根至多有 m-1 个关键字,故至多有 m 棵
子树。
这是一个 的节点类
型
!
"#
$%
&' ($)M+2);
!&!($)M
+1);
&*"#&+&
,
,
第 2 页 / 共 19 页
/ 2 1 1m n m