数据结构-多路平衡查找树:B树

B树(B-Tree)

B-树就是B树,中间的横线不是减号。B树是一种多路平衡查找树。相比于BST,B树变得更加矮胖,以此来降低磁盘I/O次数。

下图是一颗键值为英语字母的B树,带浅阴影的节点是查找字母R时要检查的节点。

从上图能轻易的看到,一个内结点x若含有n[x]个关键字,那么x将含有n[x]+1个子女。如含有2个关键字D H的内结点有3个子女,而含有3个关键字Q T X的内结点有4个子女。

特点

B树的阶:每个节点最多包含k个孩子,k被称为B树的阶。

对于一个m阶的B树有如下特征:

  • 孩子数量:
    • 根节点至少有两个孩子,至多有m个孩子。
    • 内部节点:[ceil(m/2), m],如3阶B树,内部节点孩子数量范围:2-3个。
    • 叶子节点没有孩子
  • 关键字个数(每个节点中元素的个数):
    • 关键字:key和data
    • 根节点和内部节点:[ceil(m/2) -1, m-1],如3阶B树,根节点和内部节点关键字范围:1-2个。
    • 叶子节点也存储关键字
  • 指针个数(每个节点中指针的个数):
    • 根节点和内部节点:关键字个数+1。
    • 叶子节点不存在指针域
  • 除叶子节点外,所有节点左子树小于右子树
  • 每个节点都存储key和data。


如图是一个3阶b树,每个结点最多有3个孩子;除根结点和叶子节点外,其它每个结点至少有 [ceil(3/2)] = 2个孩子,对于非终端结点,关键字的个数满足: 1 <= n <= 2。

节点关系

B树中节点分为内部节点和叶节点,内部节点也就是非叶节点。

B树的内部节点可以包含2个以上的子节点,在设计时可以预先设计可包含子节点的数量范围,即上界和下界。当向节点插入或删除数据时,也就意味着节点的数量发生了变化,为了维持上界和下界,内部节点可能会被合并或拆分。

B树中每个内部节点都会包含一定数量的键值。这些键值同时也扮演着分割子节点的角色。如:假设某内部节点包含3个子节点,则实际上必须有2个键值:a1和a2;其中a1的左子树上的所有值都要小于a1,在a1和a2之间的子树中的值都大于a1且小于a2,a2的右子树上的所有值都大于a2。

若一个内部节点有2d个键值,那么添加一个键值给该节点将会导致2d+1的数量大于范围上界,则会拆分2d+1数量的节点为2个d数量的节点,并且有一个键值提升为父节点。

类似地,若一个内部节点和它的邻居节点都包含d个键值,那么删除一个键值将会导致此节点拥有d-1个键值,小于范围下界,则会导致与邻居节点合并。合并后的节点包括d-1的数量加上邻居的d的数量和两者的父节点中的1个键值,共为d-1+d+1 = 2d数量的节点。

深度用来描述树中层的数量。B树通过要求所有叶节点保持在相同深度来保持树的平衡。深度通常会随着键值的不断添加而缓慢的增长。

B树的高度

对于辅存做IO读的次数取决于B树的高度。

若B树的某一非叶子节点包含N个关键字,则此非叶子节点含有N+1个孩子节点,所有的叶子节点在第l层。

当B树包含N个关键字时,B树的最大高度为 l-1(因为计算B树高度时,叶节点所在层不计算在内),B树的高度公式即为:l-1=log<ceil(m/2)>((N+1)/2) + 1.

B树的插入

对于高度为h的m阶B树,新节点一般插在第h层。通过检索可以确定关键码应插入的节点位置。然后分两种情况讨论:

  1. 若该节点中关键码个数小于 m-1,则直接插入即可。
  2. 若该节点中关键码个数等于 m-1,则将引起节点的分裂。以中间关键码为界将节点一分为二,产生一个新节点,并把中间关键码插入到父节点(h-1层)中。

重复上述工作,最坏情况一直分裂到根节点,建立一个新的根节点,整个B树增加一层。

B树的删除

首先查找B树中需要删除的元素,若该元素在B树中存在,则将该元素在其节点中进行删除,若删除该元素后,首先判断该元素是否有左右孩子节点,若有,则上移孩子节点中某相近元素(“左孩子最右边的节点”或”右孩子最左边的节点”)到父节点中,然后是移动后的情况;如果没有,则直接删除,移动之后的情况。

删除元素后,移动相应的元素后,若某节点中元素的个数(即关键字的个数)小于[ceil(m/2)-1],则需要看其相邻的兄弟节点是否丰满(节点中元素的个数大于[ceil(m/2)-1]),若丰满,则向父节点借一个元素来满足条件;若相邻的兄弟都刚脱贫,即借了之后其节点数目小于[ceil(m/2)-1],则该节点与其相邻的兄弟进行合并,以此来满足条件。

对于一个5阶B树(树中最多含有5个孩子,关键字最大为 5-1=4个,最小为 [ceil(5/2)-1] = 2个,即节点内元素个数小于2个就合并,大于4个就分裂)。

总结

B树的阶,B树的关键字,B树的高度,B树的最大孩子个数,B树的最小孩子个数,关键字(即节点中元素的个数)和节点孩子个数之间的联系,围绕B树的特性的插入和删除,节点合并和分裂。

B树的本质:平衡多叉树+有序数组。

参考

0%