小码哥《恋上数据结构与算法》笔记(十):B树

1,975 阅读2分钟

我的Github地址

小码哥《恋上数据结构与算法》笔记

极客时间《iOS开发高手课》笔记

iOS大厂面试高频算法题总结

iOS面试资料汇总

一、B树性质

1、初识B树

  • B树是一种平衡的多路搜索树,多用于文件系统,数据库的实现。
  • B树特点:
    • 一个节点可以存储超过2个元素,可以拥有超过2个子节点。
    • 拥有二叉树的一些性质。
    • 平衡,每个节点的所有子树高度一致。
    • 比较矮。

2、m阶B树的性质(m >= 2)

  • 假设一个节点存储的元素个数为x
    • 根节点个数:1 <= x <= m-1,三阶B树根节点数大于等于1并且小于等于2
    • 非根节点:(m / 2)(向下取整) - 1 <= x <= m - 1
    • 如果有子节点,子节点个数 y = x + 1
      • 根节点:2 <= y <= m
      • 非根节点:(m / 2)(向下取整) <= y <= m

3、B树 VS 二叉搜索树

  • 二叉搜索树的节点合并,可以成为B树
  • 多代(父和子)节点合并,可以获得一个超级节点(类似3阶B树中的1833节点,2330节点)。
    • 2代合并的超级节点,最多拥有4个子节点(至少是4阶B树)。
    • 3代合并的超级节点,最多拥有8个子节点(至少是8阶B树)。
    • n代合并的超级节点,最多拥有2^n个子节点(至少是2^n阶B树)。
  • 1833合并,2330合并,2021合并,4547合并,5052合并。即将一个B树变为二叉搜索树

二、B树的操作

1、搜索

  • 先在节点内部从小到大搜索元素。
  • 如果命中,搜索结束。
  • 如果未命中,再去对应的子节点中搜索元素,重复步骤1
  • 假设搜索72,首先在根节点做比较,72大于40,所以接着在根节点右子树搜索,72大于60小于80,继续在6080之间的子树寻找,因为72大于70,所以需要继续往70右子树寻找,但是右子树为空,所以得出结论72不在该B树上。

2、添加

  • 新添加的元素必定是添加到叶子节点
  • 假设插入55,首先在根节点做比较,55大于40,所以接着在根节点右子树搜索,55小于60,继续在60左子树寻找,55大于50,所以将55插入在节点50的右侧。
  • 假设插入95,首先在根节点做比较,95大于40,所以接着在根节点右子树搜索,95大于80,继续在80右子树寻找,95大于90小于100,所以将95插入在节点90100的中间。

3、上溢

  • 假设再插入98呢?(假设这是一颗4阶B树
    • 最右下角的叶子节点的元素个数将超过限制。
    • 这种现象可以称之为:上溢(overflow)

4、上溢的解决

  • 假设5阶B树
  • 上溢节点的元素个数必然等于m(5)
  • 假设上溢节点最中间元素的位置为k(3)
  • k位置的元素向上与父节点合并
  • [0,k-1][k+1,m-1]位置的元素分裂成2子节点,这2个子节点的元素个数,必然都不会低于最低限制(m / 2(向下取整) - 1)
  • 一次分裂完毕后,有可能导致父节点上溢,依然按照上述方法解决。
  • 最极端的情况,有可能一致分裂到根节点
  • 添加元素导致的上溢,是唯一一种可能导致B树长高的操作。

5、添加导致上溢的例子

  • 插入98
  • 98大于根节点,继续往根节点右子树比较,98大于6080,继续往80右子树比较,98大于9095,小于100,所以将98插入在95100中间。
  • 插入98之后,90 95 98 100节点溢出,需要上溢,将中间元素95或98向上与父节点合并,将90,98,100节点分裂成2个子节点。
  • 插入52
  • 插入54

6、删除

  • 假如需要删除的元素在叶子节点中,那么直接删除即可。
  • 删除30
  • 假如需要删除的元素在非叶子节点中。
    • 先找到前驱或后继元素,覆盖所需删除元素的值。
    • 再把前驱或后继元素删除。
  • 删除60
  • 60的前驱为55,将5554和55节点中删除,并将55覆盖60
  • 非叶子节点的前驱或后继元素,必定在叶子节点中。
    • 所以这里的删除前驱或后继元素,就是最开始提到的情况:删除的元素在叶子节点中。
    • 真正的删除元素都发生在叶子节点中。

7、下溢

  • 假设一颗5阶B树,删除22
  • 叶子节点被删除一个元素后,元素个数可能会低于最低限制(>= m/2(向下取整) - 1)
  • 这种现象称为:下溢(underflow)

8、下溢的解决

  • 下溢节点的元素数量必然等于(m/2(向下取整) - 2)
  • 如果下溢节点临近的兄弟节点,有至少m/2(向下取整)个元素,可以向其借一个元素。
  • 绿色节点在删除一个元素后,节点元素个数低于最低限制(>= m/2(向下取整) - 1)
    • 为了使树继续满足B树的要求,需要对绿色节点进行下溢操作。
    • 将父节点的元素b插入到下溢节点的0位置(最小位置)。
    • 用兄弟节点的元素a(最大的元素)替代父节点的元素b
    • 这种操作其实就是:旋转
    • 注意子节点d也需要调整。

  • 如果下溢节点临近的兄弟节点,只有(>= m/2(向下取整) - 1)个元素。
    • 将父节点的元素b挪下来跟左右子节点进行合并
    • 合并后的节点元素个数等于m/2(向下取整) + m/2(向下取整) - 2,不超过m-1
    • 这个操作可能会导致父节点下溢,依然按照上述方法解决,下溢现象可能会一直往上传播。
  • 添加元素导致的下溢,是唯一一种可能导致B树变矮的操作。