B-树的性质及插入和删除操作
B-树
B-树是一种平衡的多路查找树，它在文件系统中很有用。一棵
m
m
m阶的B-树，或为空树，或为满足下列特性的
m
m
m叉树：
树中每个结点至多有
m
m
m棵子树若根节点不是叶子结点，则至少有2棵子树除根之外的所有非终端结点至少有
⌈
m
/
2
⌉
⌈m/2⌉
⌈m/2⌉棵子树所有非叶子结点包含下列信息数据：
(
n
,
A
0
,
K
1
,
A
1
,
⋯
,
K
n
,
A
n
)
(n,A_0,K_1,A_1,\cdots,K_n,A_n)
(n,A0,K1,A1,⋯,Kn,An)
K
i
(
i
=
1
,
⋯
,
n
)
K_i(i=1,\cdots,n)
Ki(i=1,⋯,n)为关键字，且
K
i
<
K
i
+
1
(
i
=
1
,
⋯
,
n
−
1
)
K_i Ki A i ( i = 0 , ⋯ , n ) A_i(i=0,\cdots,n) Ai(i=0,⋯,n)为指向子树根节点的指针。 n ( ⌈ m / 2 ⌉ − 1 ≤ n ≤ m − 1 ) n(⌈m/2⌉-1\le n \le m-1) n(⌈m/2⌉−1≤n≤m−1)为关键字的个数。 所有叶子结点都出现在同一层次上，并且不带信息。 B-树的插入 B-树的生成也是从空树其，逐个插入关键字所得。因为B-树结点中的关键字个数必须大于等于 ⌈ m / 2 ⌉ − 1 ⌈m/2⌉-1 ⌈m/2⌉−1，所以，每次插入一个关键字不是在树中添加一个叶子结点，而是首先在最底层的某个非叶子结点中添加一个关键字： 若该结点的关键字个数不超过 m − 1 m-1 m−1，则直接插入。若该结点的关键字个数等于 m − 1 m-1 m−1，则插入后需要对此结点进行分裂。 对如图(a)所示的3阶B-树，依次插入30，26，85。图解过程如下所示： 插入30：从结点a开始查找，确定30应该插入节点d中。因为，d结点中关键字个数不超过2，所以，直接将30插入其中。结果如图(b)所示： 插入26：从结点a开始查找，确定26应该插入节点d中。因为，d结点中关键字个数为2，所以，在将26插入d结点后，需要将d分裂。结果如图©所示： 插入85：从结点a开始查找，确定85应该插入节点g中。因为，g结点中关键字个数为2，所以，在将85插入g结点后，需要将g分裂。而当分裂出的70插入e中时，其关键字个数大于2，也需要分裂。最终结果如图(d)所示： B-树的删除 在B-树上删除一个关键字，则首先应该找到关键字所在结点，并从中删除。以下图(a)为例： 其情况分为两种： 若删除的结点不是最下层的非终端结点 K i K_i Ki，则可以用指针 A i A_i Ai所指的子树中（值较大的子树）的最小关键字替代 K i K_i Ki，并将用来替代的值删除。 示例：从图(a)中删除45，选取45右侧分支中的最小值50用以替换45，同时删除50并做调整，其结果如下所示： 若删除的结点是最下层的非终端结点，则可分为三种情况。 被删除关键字所在结点中的关键字数目大于 ⌈ m / 2 ⌉ − 1 ⌈m/2⌉-1 ⌈m/2⌉−1，则只需要从该结点中删除该关键字，其余部分保持不变。被删除关键字所在结点中的关键字数目等于 ⌈ m / 2 ⌉ − 1 ⌈m/2⌉-1 ⌈m/2⌉−1，而与该结点相邻的兄弟（先左后右）结点中的关键字数目大于 ⌈ m / 2 ⌉ − 1 ⌈m/2⌉-1 ⌈m/2⌉−1，则需要将兄弟结点中的最大值（或最小值）上移至双亲结点中，而将双亲结点中小于（或大于）且紧靠上移关键字的关键字下移至被删除关键字所在结点中。被删除关键字所在结点和其相邻的兄弟结点中的关键字数目均等于 ⌈ m / 2 ⌉ − 1 ⌈m/2⌉-1 ⌈m/2⌉−1。则在删除此节点后，将其与左兄弟（或右兄弟）和紧邻的双亲结点中的关键字进行合并为新的结点。 对2中所述的三种情况，我们以图(a)为例，从图(a)依次删除12、50、53。 删除12：因为12所在结点c关键字数目大于1，所以直接删除12，其结果如图(b)所示： 删除50：50所在结点f关键字数目为1，但其右兄弟g关键字数目大于1，所以f在删除50后可以向g借一个。将原先紧邻的双亲结点中的关键字53移动至f，将g中的最小关键字上移至双亲中。其最终结果如图©所示： 删除53：53所在结点f仅有一个关键字，且其仅有的右兄弟g也仅有一个关键字，所以在删除53后，将空结点与且紧邻的双亲结点关键字61和右兄弟合并为一个新的结点。其最终结果如图(d)所示：
发表评论