B树

前言

B树的英文名是B-Tree,在中文译名中,有的去掉了中划线,叫做B树;有的保留了中划线,叫做B-树。因此B树、B-树是一个概念。而B+树是B树的一个变种,所以B+树是另外一种树。


B树

B树是多路平衡树。一棵m阶的B树需要满足如下的5个性质:

  • 每个节点最多有m-1关键字
  • 根节点最少有一个关键字
  • 除根节点外,每个节点最少有向上取整(m/2)-1关键字
  • 所有的叶子节点都出现在同一层
  • 节点的孩子的数量比关键字数量多1。故每个节点形如:(P0, K0, P1, ..., Pi, Ki, Pi+1, ..., Kn-1, Pn)。其中,向上取整(m/2)-1 <= n <= m-1,Pi所指向的子树中所有的节点都不大于Ki,Pi+1所指向的子树中所有的节点都不小于Ki,Ki不大于Ki+1

接下来讨论下,一棵有n个关键字的m阶B树的最大深度和最小深度:

  • 当根节点只有1个关键字,其他节点都只有向上取整(m/2)-1个关键字的时候,B树的深度是最大的:
    设树的深度是h,所以左右子树的深度都是h-1,
    设j = 向上取整(m/2) - 1,
    那么左子树和右子树的关键字数量都是:
    j + (j+1)×j + (j+1)2×j + ... + (j+1)h-2×j
    根据等比数列的求和公式,得到:
    左子树和右子树的关键字数量都是
    j×(1-(j+1)h-1)/(1-(j+1)) --->
    (j+1)h-1 - 1
    也就是
    2×((j+1)h-1 - 1) + 1 = n --->
    (j+1)h-1 = (n+1)/2 --->
    h = log向上取整(m/2)((n+1)/2) + 1

  • 当每个节点都有m-1个元素的时候,B树的深度是最低的:
    设j = m-1,树的深度为h
    则j + (j+1)×j + ... + (j+1)h-1×j = n
    根据等比数列的求和公式:
    j×((1-(j+1)h)/(1-(j+1))) = n --->
    h = log向上取整(m/2)(n+1)

B树的深度直接影响了插入节点、查找节点、删除节点的时间复杂度。


插入关键字

跟二叉查找树类似,B树的插入也发生在叶子节点。当插入关键字的时候,如果导致节点的关键字的数量突破m-1的限制,就需要将该节点从中间进行分裂。其中,left节点包含[0...m/2-1]关键字子序列,right节点包含[m/2+1, ..., m-1]关键字子序列。然后将m/2位置的关键字插入到该节点的父节点,之后按照相同的方式处理父节点,一直到其父节点满足关键字个数的限制,或者到达根节点,根节点分裂之后,会导致B树的高度增加1
博主认为,编写代码的麻烦点在于处理孩子指针、以及父指针的指向


查找关键字

B树的查找是一个交叉查找的过程。可以参考这篇文档中的描述和示例。


删除关键字

B树的插入涉及到节点的分裂,而B树的删除则涉及到节点的合并。与二叉查找树类似,删除也发生在叶子节点。

  • 如果要删除的关键字在叶子节点,那么直接删除它。
  • 如果要删除的关键字不在叶子节点,假设该关键字在节点中的索引是index,那么可以使用节点的第index个孩子指针所指向的子树的最右面的节点R1的最后一个关键字K1替代要删除的关键字,然后删除节点R1的关键字K1;或者使用节点的第index+1个孩子指针所指向的子树的最左面的节点R2的第一个关键字K2替代要删除的关键字,然后删除R2的关键字K2。本质上就是中序遍历的前驱和后继

如果该叶子节点是根节点,那么无需做任何处理,直接结束皆可。 否则,如果关键字数量小于向上取整(m/2)-1,那么存在三种情况:

  • 左兄弟非空,且左兄弟的关键字数量大于向上取整(m/2)-1,那么把左兄弟的最后一个关键字借过来,在借的过程中,需要经过父节点的中转,并且在借的过程中,还会把左兄弟的最后一个孩子指针借过来
  • 右兄弟非空,且右兄弟的关键字数量大于向上取整(m/2)-1,那么把右兄弟的第一个关键字借过来,在借的过程中,需要经过父节点的中转,并且在借的过程中,还会把右兄弟的第一个孩子指针借过来
  • 无法从左右兄弟借关键字(也就是左兄弟为空、右兄弟的关键字数量等于向上取整(m/2)-1 或 右兄弟有空、左兄弟的关键字数量等于向上取整(m/2)-1 或 两者都不为空,但是关键字数量都等于向上取整(m/2)-1),此时需要将该节点和其非空的兄弟节点、以及父节点中两者之间的那个关键字,进行三方合并,合并的过程中,需要处理好相关节点的孩子指针、及其父指针的指向。之后按照相同的方式处理该节点的父节点,一直到其父节点的关键字数量满足B树的要求,或者达到根节点,根节点在参与合并之后,可能会导致树的高度减少1

代码实现

tim-chow的github

感谢浏览tim chow的作品!

如果您喜欢,可以分享到: 更多

如果您有任何疑问或想要与tim chow进行交流

可点此给tim chow发信

如有问题,也可在下面留言: