0%

数据结构 - B树

阅读本文之前,建议先了解二叉树相关知识

B树

B树也是一颗“有序”的树,因此他的查找,编辑操作也是对数时间复杂度,与二叉查找树不同的是,B树的节点可以有多个孩子节点,从几个到几千个,所以相同的节点数,B树的的高度会比二叉查找树小很多。

B树的一些基本概念定义:

红黑树中的NIL叶子节点是有意义的,B树种的NIL叶子节点没什么意义,因此下文中,统一将最底层,无子节点的节点称之为叶子节点。

  • B树所有节点中,子节点个数最大的值,我们称之为B树的阶,用m表示;
  • 每个节点最多有m棵子树;
  • 除根节点和叶子节点以外,其他每个分支节点至少有$ceil(m/2)$棵子树;
  • 如果一棵B树不止包含一个节点(根节点)的话,则根节点至少有两棵子树;
  • B树的所有叶子节点都在同一层上;
  • 每个非叶子节点,包含有n个关键字和n+1个节点,假设$k_i$表示第i个关键字,$p_i$表示第i个节点,则:
    • $ki<k{i+1}$;
    • $pi$为根节点的子树上的所有关键字大于$k{i-1}$,小于$k_i$。

用如下一个例子来说明:

1

  • 上图为一棵3阶的B树;
  • 每个节点最多只有3课子树;
  • 除了根节点和叶子节点,其他节点都至少有$ceil(m/2) = 2$个子节点;
  • 所有叶子节点都在同一层;
  • 同一个节点内的关键字,从小到大排序,例如G节点;G节点上的所有关键字,都小于C节点中的63,同时大于A节点的50。

查找

B树的查找操作比较简单,跟二叉查找树是一个原理,实际操作中,只是将二叉查找树的左右子节点,替换成一个关键字数组而已,这里不做过多描述。

插入

由于一棵m阶的B树,会有$[ceil(m/2), m]$个子节点,则就会有$[ceil(m/2)-1, m-1]$个关键字,插入时主要依据这个规则,来判断是否插入到当前节点,父节点,还是说构造一个新节点,插入规则如下:

  • 查找带插入值应该插入的节点;
  • 若该节点的关键字数量为$m-1$,则插入新关键字之后,将节点拆分,取出中间的一个关键字,准备放入父节点中;
  • 若父节点不存在,则新建一个节点存放当前值,左右子节点分别为上一步分离开的左右子节点;
  • 若父节点存在,则将相当于往父节点中插入一个提取出来的值,递归上述步骤。

还是来举个栗子,假设要在一棵四阶B树种插入序列:33 50 75 88 24 16 70 92 73 90 18 99

  • 因为是四阶B树,所以依次插入33,50,75之后,B树如下:

    1

  • 继续插入88,插入之后如下左图:

    1

    此时节点有4个关键字,违背了关键字范围的规则,因此从数组中间进行拆分节点,将50关键字拆出来,因为当前节点没有父节点,因此将50关键字作为一个独立的节点,将拆开之后的左右两个节点作为50关键字节点的左右子节点,如右图。

  • 继续插入24,16,70之后,B树如下:

    1

  • 继续插入92,插入之后如下左图:

    1

    此时右下节点再次不满足关键字范围的规则,同理,拆分节点,将75关键字提取出来,此时节点有父节点,因此直接将75关键字放入父节点当中,然后将拆开之后的两个节点作为子节点接入父节点中,如右图。

  • 继续插入73,90,18之后,如下图(中间拆分步骤即是上述步骤,不再重复):

    1

  • 此时插入最后一个99,如下左图:

    1

    插入之后,右下节点不满足规则,则按照上述步骤,提取90关键字到父节点;然后父节点关键字也不再满足规则,继续拆分,提取50关键字,此时父节点不存在,则单独创建一个节点,存放50关键字。

B树的插入操作,始终都是将值先插入到叶子节点,然后判断节点关键字是否过多,如过多则分裂当前节点,并挤出一个节点添加到父节点中,再递归判断父节点的情况。如果一直递归到根节点,则相当于将根节点分裂,然后新增一个根节点,从而使得整棵树增加了一层。

删除

B树的删除,有两种情况:

  • 待删除的值在叶子节点上;
  • 待删除的值不在叶子节点上。

针对第二种情况,B树也可以使用类似二叉查找树的前驱/后继节点的方式,在叶子节点中找到一个替换的值,用来替换当前值,然后相当于删除叶子节点中的值,从而将第二种情况转化成第一种情况。

删除一个叶子节点中的值,有如下几种情况:

  • 删除之后的关键字个数任然满足规则,则删除之后不做任何处理;
  • 删除之后关键字的个数小于最小值
    • 向左边或者右边节点取一个关键字,前提是左右节点少一个关键字之后仍然满足规则;
    • 将父节点中相关的关键字和左边或者右边节点合并成一个节点,这样会导致父节点少了一个关键字,则需要递归继续判断。

继续举个栗子,假设有如下一棵五阶(关键字范围为$[2,4]$)B树:

1

  • 删除76关键字

    删除之后节点只有1个关键字,因此需要调整。这时首先看左右两边的兄弟节点,是否有关键字可以取过来:

    • 左侧节点只有2个关键字,如果取走一个就不满足要求;
    • 右侧节点有4个关键字,可以取走一个。

    但是这里不能直接取过来放在原来76的位置,这样就破坏了跟父节点的有序性,要通过类似“旋转”的方式,将取出来的值放到父节点中,然后将父节点中的值拿下来,如图:

1

  • 删除96关键字

    因为96关键字没有在叶子节点上,所以我们找到他的后继关键字98,替换掉96,而去掉98之后,节点还有2个关键字,满足规则,因此无需做其他调整:

1

  • 删除75关键字

    删除75关键字的过程,会比较麻烦一点,75关键字所在节点的左右兄弟节点均没有多余的关键字可以提供,因此只能采用合并的方式:

    • 将75关键字删掉,此时节点只剩下77一个关键字;
    • 合并左侧节点(右侧也可以),因此取出父节点中,左边的关键字74;
    • 将左侧节点的64,70,父节点的74,剩余关键字77,共同合并成一个新节点,挂在原父节点下面

    此时解决了删除75导致的原节点关键字不满足范围规则的问题,但此时父节点又只有1个关键字了,因此需要递归:

    • 左侧兄弟节点没有多余关键字可以提供,因此采取合并的方式;

      如有,则情形与删除76关键字相同,但是注意取关键字的同时要将关键字对应的子节点一同取过来。

    • 采用上述合并的方式,将父节点,当前节点,和左侧兄弟节点合并成一个新的节点。

1

B+树

B+树是有B树演变而来的一种树,他与B树主要有如下区别:

  • 非叶子节点中的关键字仅仅具有索引左右,所有关键字在叶子节点中会再次出现;
  • 所有的叶子节点也构成一个有序的链表。

另外还有一个有点分歧的区别 ,有的文章提到B+树的关键字个数等于子节点个数(绝大部分中文博客),但是有的定义中,关键字数量为节点数量减1(B+ Tree的wiki,国外部分文章)。由于B+树的非叶子节点仅仅只存储关键字作为索引,所以这种定义的区别,主要是在索引过程中会有一些if判断上的区别,对于整个数据结构影响并不大,我们这里采用wiki中的定义,关键字个数为节点数量减1。

举个具体的栗子:

1

  • 非叶子节点出现的关键字,最终在叶子节点中会再次有序的出现;
  • 所有叶子节点首尾相连,构成一个链表。

插入

B+树的插入逻辑与B树相同,需要注意一点是,遇到要拆分的情况时,中间关键字不是移动到父节点中,而是复制一份到父节点中,即是被拆分节点依然保留中间关键字。详细流程就不再赘述了。

删除

同上,删除操作原理也相同,需要注意的是:

  • 待删除的节点如果在非叶子节点和叶子节点中均存在,则要删除两个地方,并且用新的前驱/后继节点替换原索引节点;
  • 合并的时候,需要将父节点与当前节点相同的值删除一份;

区别

从纯数据结构来说 ,B+树和B树的区别不大,B+树甚至比B树还冗余了部分关键字,所以同样多的关键字,B+树占用的体积会更大。

而从实际应用来说,二者区别就很大了。B树和B+树主要运用在各种存储中,实际运用的过程中,关键字一般是作为某条数据记录的索引,因此与索引一同存储的还有指向这条数据记录的指针,类似K-V结构,K为关键字,V为指向数据的指针(例如数据库中,某一列为索引,即是关键字,整行数据为数据记录,找到关键字之后,通过数据指针,拿到整行数据),如下图:

1

基于上述实际应用中,二者有如下的区别:

  • B树的每个节点都会存储关键字,数据指针,而B+树在在非叶子节点只存储关键字,在是所有叶子节点存储数据指针;

  • 同样大小(占用存储大小,比如1K)的一个非叶子节点,B+树因为不存储数据信息,所以能够存储更多的关键字;

  • 同样多的关键字,B+树因为非叶子节点能够存储更多的关键字,所以查询效率也会高一些;

    一次性载入到内存中的待查询的关键字多一些,这样使得I/O查询的次数也就更少一些。

  • B+树的所有叶子节点构成一个有序的链表,所以如果是范围查询,B+树找到起始位置之后,直接遍历链表即可,而B树需要进行中序遍历,效率会低一些。

最后

了解了B树,B+树之后,我们再来想想,有了平衡的二叉树之后,为什么还需要多叉树呢?

这里主要是考虑磁盘I/O相关的技术,使用多叉树能够更高效的进行磁盘I/O操作,引用一段内容:

磁盘中有两个机械运动的部分,分别是盘片旋转和磁臂移动。盘片旋转就是我们市面上所提到的多少转每分钟,而磁盘移动则是在盘片旋转到指定位置以后,移动磁臂后开始进行数据的读写。那么这就存在一个定位到磁盘中的块的过程,而定位是磁盘的存取中花费时间比较大的一块,毕竟机械运动花费的时候要远远大于电子运动的时间。当大规模数据存储到磁盘中的时候,显然定位是一个非常花费时间的过程,但是我们可以通过B树进行优化,提高磁盘读取时定位的效率。

为什么B类树可以进行优化呢?我们可以根据B类树的特点,构造一个多阶的B类树,然后在尽量多的在结点上存储相关的信息,保证层数尽量的少,在B树中可以检查多个子结点,由于在一棵树中检查任意一个结点都需要一次磁盘访问,所以B树避免了大量的磁盘访问;而且B类树是平衡树,每个结点到叶子结点的高度都是相同,这也保证了每个查询是稳定的,查询的时间复杂度是$O(log_2N)$。

总的来说就是利用平衡树的优势,保证了查询的稳定性和加快了查询的速度。

参考



-=全文完=-