前言

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


B树

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

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

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


插入关键字

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


查找关键字

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


删除关键字

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

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


代码实现

tim-chow的github