B-树

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

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

m阶B树的性质（m≥2）

B树 VS 二叉搜索树

搜索

插入

  • 新添加的元素必定是添加到叶子节点

  • 若节点的元素个数超过最大限制，会发生上溢

删除

  • 假如需要删除的元素在叶子节点中，那么直接删除即可
  • 假如需要删除的元素在非叶子节点中
    • 先找到前驱或后继元素，覆盖所需删除元素的值
    • 再把前驱或后继元素删除

非叶子节点的前驱或后继元素，必定在叶子节点中,所以这里的删除前驱或后继元素 ，就是最开始提到的情况: 真正的删除元素都是发生在叶子节点中

  • 删除元素后，元素个数可能会低于最低限制，会发生下溢

hhhhh