数据结构之B树

一、B树的基本概念

B树是一种多叉树,被广泛应用于数据库索引中。它也是一种特殊的搜索树,和搜索树最大的不同在于它的每个节点都包含了n个关键字和n+1个指向子节点的指针。它的表现形式为:

B树

B树的特点:

  1. 假设x.key为当前节点中的关键字,x.child.key是子节点中的关键字,那么它们之间存在以下关系:
    x.child.key <= x.key1 <= x.child2.key <= x.key2 <= x.child3.key <= ... <= x.keyn
  2. 每个节点的关键字个数都有上界和下界,上下界用B树的最小度数t ≥ 2来表示。
  3. 除了根节点以外,每个节点必须有t - 1个关键字,除了根节点以外,每个节点都有t个孩子。
  4. 每个节点最多有2t - 1个关键字,最多有2t个孩子。当一个节点恰好有2t - 1个关键字时,称该节点是满的。
  5. t = 2的时候B树最简单,每个内部节点有2、3或者3个孩子,也被称作2-3-4树。
  6. t值越大,B的高度就越小。

为什么B树广泛应用于索引中

因为磁盘读取的最小单位是扇区,每个扇区是512字节。操作系统读取磁盘的最小单位是块,一个块包含了若干个扇区(一般一个块是4096字节,包含8个扇区)。如果和红黑树或其他二叉搜索树一样,每个节点只保存一个数据,那么磁盘读取的效率就相当低了。如果需要读取多个数据,就要执行多次磁盘IO操作才能完成任务了,而磁盘IO在系统中属于较为耗时的操作,因此多次IO势必导致效率大大降低。

B树就是为了改进这一问题而衍生出来的,B树的节点一般设置为磁盘的块大小,也就是4K,里面包含了多个数据节点的内容,这样一次IO就能读到多个数据内容。并且由于B树也具有搜索树的性质,因此很快就能定位到数据内容。

二、B树操作

B树的主要操作有两个:分裂和合并。因为B树的每个节点包含关键字的数量为[t - 1, 2t - 1],当节点的关键字数量超出后,就要对节点进行分裂操作,分裂操作会导致B树高度增加。当节点关键字被删除,数量不满足条件时就要合并两个节点,合并节点会导致B树高度下降。

3.1 增加节点

以一个度为4的B树为例,插入S后,B树节点的关键字数量变成了7,需要进行分裂。

B树分裂

此时对节点的分裂过程为:

  1. 新生成节点,将S右边的关键字和子节点移到新节点中。
  2. S左边的关键字和子节点保存在当前节点。
  3. S节点往上提,放到父节点中的合适位置。
  4. 如果S节点上提导致父节点的数量也超出了,还需要继续对父节点进行分裂。
注意:每次上提到父亲节点的关键字都是被分裂节点的中间关键字。

分裂示例

以下是度为3的B树分裂的过程,每个节点最多有5个关键字,最少2个关键字。

初始时的B树:

B树分裂-1

插入B,这只是一个简单的对叶节点插入的过程,插入后不会影响其他节点,B树的条件也还满足,直接插入就行:

B树分裂-2

插入Q,因为插入Q后会导致RSTUV节点关键字超出,因此要分裂这个节点。T节点作为中间节点放到父节点中(也可以把S提到父节点,T放在UV节点):

B树分裂-3

插入L,它被放到JK节点之后,也是一个简单的叶节点插入。但是因为根节点的关键字满了,所以对根节点分裂,此时将P提出来作为根节点,树的高度加1:

B树分裂-4

插入F,放在ABCDE节点之后,插入后将导致节点分裂,节点C提到父节点:

B树分裂-5

2.3 删除节点

在B树中删除节点,将会引发节点的合并。相对于增加节点来说,删除节点的远比增加节点要复杂。

以上面的B树为例,初始状态为:

删除节点-1

删除关键字F,作为叶子节点,删除F后并没有影响到B树的性质,直接删除即可。得到以下B树:

删除关键字F

删除关键字M,因为M所处的节点是内部节点,删除M后会导致NO关键字所在的节点没有父节点。此时需要把M的前驱关键字L替换掉M,然后删掉L

也可以把M的后继关键字N替换上来,但是M替换后会导致子节点不满足关键字数量条件。

删除节点M

删除关键字GG所处的节点也是内部节点,删除后会导致DE或者JK所处的节点没有父节点,此时也需要和上面删除M一样在子节点中找到前驱或者后继替换上来。但是这里不同的是,两个子节点都是只有t - 1个关键字,再从中拿掉一个关键字后会导致子节点关键字数量不满足。此时就需要合并两个子节点,然后直接删除G节点:

删除节点G

删除关键字D,D所处的节点是叶子节点,可以和删除节点F一样,直接删除。但是这里也有一个不同的点是,父节点和父节点的兄弟节点此时都只有t - 1个节点,此时除了删除节点D以外,还要合并父亲节点,此时树的高度减一:

删除节点D.png

删除关键字BB所在的节点关键字数量是t - 1,删除B后会导致节点的最小关键字数量不满足条件。因此要从父节点或者兄弟节点借一个关键字。此时就分为两种情况:

  1. 如果兄弟节点的关键字个数也是t - 1,那么直接和兄弟节点合并,从父节点提取一个关键字下来(下面删除C时候的场景)。
  2. 如果兄弟节点的关键字个数大于t - 1(目前就是这个情况,兄弟节点有3个关键字),此时就从父节点借一个关键字C替换掉B,借掉C后,就相当于删除了一个内置节点的元素,所以父亲节点要从它后继节点中找一个关键字补上,也就是E。最终的结果就是用C覆盖B,再用E覆盖原来C的位置,再删除E

删除关键字B

删除节点C,此时的情况就是上面的第一种情况了,兄弟节点的关键字个数是t - 1,要合并两个节点,得到:

删除关键字C

最后修改:2020 年 01 月 12 日
喜欢就给我点赞吧