B树

1、概述

B树是一种平衡的多路搜索树，多用于文件系统、数据库的实现。

3阶B树.png
4阶B树.png
5阶B树.png
B树的特点：

• 1、一个节点可以存储超过2个元素，可以拥有超过2个子节点。
• 2、拥有二叉搜索树的性质。
• 3、平衡，每个节点的所有子树高度一致。
• 4、比较矮。

2、m阶B树的性质（m>=2）

2.1、元素个数和子节点个数

• 1、假设一个节点存储的元素个数为x
  • 根节点：1 <= x <= m-1
  • 非根节点：ceil(m/2)-1 <= x <= m-1
• 2、如果有子节点，那么子节点的个数y = x + 1
  - 根节点：2 <= y <= m
  - 非根节点：ceil(m/2) <= y <= m
  比如 m = 3，2 <= y <= 3，因此可以称为（2,3）树。
  比如 m= 4，2 <= y <= 4，因此可以称为（2,4）树。
  比如 m=5，3 <= y <= 5，因此可以称为（3,5）树。
  比如 m=6, 3 <= y <= 6，因此可以称为（3,6）树。
  比如 m=7，4 <= y <= 7，因此可以称为（4,7）树。

3、B树 VS 二叉搜索树

• 1、B树和二叉搜索树逻辑上是等价的。

  
  二叉搜索树.png
  

  和二叉搜索树等价的B树

  
  image.png
• 2、多代合并
• 2代合并：将上图二叉搜索树中的节点18和节点33合并或者将节点18、节点12、节点33合并就表示2代合并。
  2代合并（将多个节点合成一个拥有多个元素的节点）后的超级节点，最多有4个子节点。（至少是4阶B树）
• 3代合并：将二叉搜索树中节点18、 节点33 、节点48合并成超级节点，最多有8个子节点。（至少是8阶B树）
• n代合并：n代合并的超级节点，最多有2ⁿ个子节点。（至少是n阶B树）
• m阶B树，最多需要log2(m)代合并。

4、搜索

B树的搜索和二叉搜索树的搜索类似。

image.png

• 1、先从节点内部从小到大进行搜索。
• 2、如果命中则返回。
• 3、如果未命中，则去对应的子节点中进行搜索，先从节点内部从小到大进行搜索。
  比如搜索52，先和40进行比较，发现大于40，然后去右子节点中搜索，发现52小于60，则去左子节点中进行搜索，发现52大于50，则在节点内部向右搜索，找到52返回。

4、添加

• 新添加的元素必定是叶子节点（二叉搜索树也是如此）。
  image.png
  示例一：在上述B树中插入55，过程如下

和40比较，大于40，然后和右子树节点元素比较，小于60，则和其左子元素进行比较，大于50，将元素插入到50的右边。结果如下图

image.png
示例二：插入95，过程同上，直接上图
image.png
示例三：插入98
image.png
如果这是一颗4阶B树的话，在插入98之后，右下角的节点的元素个数等于4，不满足ceil(m/2)-1<= x <= m-1，这种情况称为上溢。

添加导致上溢的解决

下图为5阶B树的一部分

image.png

• 上溢节点的元素个数必定等于m（元素个数最大等于m-1）。
• 假设上溢节点最中间元素的位置k

• 将k位置的元素向上与父节点合并。
• 将上溢节点[0,k-1]和[k+1,m-1]分成两个子节点。作为k位置元素的左右子节点。（不用担心这两个子节点的个数小于ceil(m/2)-1）。

分裂完成图如下：

image.png

• 一次分裂完成，有可能导致父节点上溢，依然按照上述方法解决。最极端情况可能要一直分裂到根节点。
  假设上图已经分裂到了根节点

• 取出上溢根节点中间元素40，将其作为新的根节点，假设位置为k
• 将[0,k-1]、[k=1,m-1]分裂成2个字节点，作为根节点的左右子节点

结果如下图

image.png

添加练习

下图是一个4阶B树

image.png

• 插入98

  
  image.png

• 插入 52

  
  image.png

• 插入 54

  
  image.png

5、删除节点

5.1、删除叶子节点

如果删除的是叶子节点，那么直接删除即可。

image.png

比如删除30

image.png

5.2、删除非叶子节点

• 如果删除的是非叶子节点

1. 先找到前驱或后继元素，覆盖所要删除的元素。

2. 再把前驱或后继元素删除。

   
   image.png
   

   比如删除60

找前驱节点和二叉树相同，node.left.right.right.....
60的前驱元素为55，用55覆盖60
由于55是在叶子节点中，直接删除即可

image.png
非叶子节点的前驱元素或后继元素，一定在叶子节点中。注意是非叶子节点的前驱或后继。
所以删除非叶子节点，最终要删除的元素依然在叶子节点中。

5.3、删除导致的下溢

看下图中的5阶B树

image.png
删除元素22。
叶子节点中元素删除可能会导致节点中的元素个数小于ceil(m/2)-1，这种情况就称为下溢。

5.4、下溢的解决

旋转操作

• 下溢节点的元素必然等于ceil(m/2)-2
• 如果下溢节点临近的兄弟节点中的元素个数至少有ceil(m/2)个，可以向兄弟节点借一个元素。

• 将父节点中的b元素插入到下溢节点的0的位置，即最小位置。
  用兄弟节点的最大元素a替代父节点的元素b。
  这种操作其实是**旋转 **。
  上面操作是右旋操作，所以原先a元素的右子节点d变成了b元素的左子节点。
  image.png
• 下面看下左旋操作
  image.png
  删除左子节点元素，会下溢，将b元素插入到下溢节点的最大位置，用兄弟节点的最小元素a替代父节点元素b。

合并操作

• 如果下溢节点临近的兄弟节点元素，只有ceil(m/2)-1个元素。

将父节点的元素b挪下来和左右子节点进行合并。
合并后的元素个数=ceil(m/2)+ceil(m/2)-2，不超过m-1。
这样操作可能会造成父节点下溢，依然按照上述方法解决，下溢现象可能会一直向上传播。

练习

下图是一棵5阶B树

image.png
删除元素22

1. 叶子节点元素个数为1，小于ceil(m/2)-1。
   2.由于临近兄弟节点的元素个数ceil(m/2)-1，所以不能从兄弟节点中接元素。只能将父节点中的元素20挪下来和其左右子节点合并成一个节点。
   3.挪下来之后发现父节点元素个数小于ceil(m/2)-1。则需要将根节点30挪下来和其左右子节点进行合并。

image.png

6、4阶B树

学习4阶B树是为了更好的理解红黑树，这也是本文的目的。
4阶B树的性质：

• 1、所有节点能存储的元素的个数：1 <= x <= 3
• 2、所有非叶子节点的节点的个数： 2 <= y <= 4

6.1、添加

元素从1添加到22，组成一个4阶B树。

• 1、首先在根节点中添加1、2、3,3个元素，当添加4时，会发生上溢，取出中间位置元素2，放入新的根节点中，分裂出[1]和[3,4]来作为2的左右子节点。

  
  image.png

• 2、在3、4所在节点中添加5、6，又会发生上溢，取出中间元素4和父节点合并，分裂出[3]和[5,6]作为4的左右子节点。

  
  image.png

• 3、在5、6所在节点中添加7、8，又会上溢，取出中间元素6和父节点合并，分裂出[5]和[7,8]作为6的左右子节点。

  
  image.png

• 4、在子节点7、8中加入9、 10会发生上溢，取出中间元素8和父节点合并，分裂出[7]和[9,10]作为8的左右子节点，第一次分裂完成后，根节点会发生上溢。取出中间元素4作为新的根节点，[2]和[6,8]作为根节点的左右子节点。

  
  image.png

• 5、其他添加过程类似，最终结果如下

  
  image.png

6.2、删除

从1删除到22

• 1、删除叶子节点1，直接删除，导致下溢，临近的兄弟节点元素个数为ceil(m/2)-1，无法从兄弟节点借元素，只能将父节点元素2下移和3进行组合，这样父节点2也会下溢，将父节点4下移和6进行组合，父节点依然会下溢，此时可以从兄弟节点借元素12，进行左旋操作，结果如下
  image.png

• 2、删除元素2并不会下溢，直接删除即可。删除元素3会造成下溢，将父节点元素4挪下来和左右子节点进行合并即可。

  
  image.png

• 3、删除元素4不会造成下溢，直接删除即可。删除5操作下溢，将父元素6向下和左右子节点进行合并，这样父节点依然下溢，将父元素8向下和左右子节点合并，父元素依然下溢，将根节点12向下和左右子节点合并

  
  image.png
• 4、继续删除情况类似不再赘述。