9.B树

B树

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

• 一个节点可以存储多个元素，一个节点可以有多个子节点。

• 拥有二叉搜索树的一些性质

• 平衡，每个节点的所有子树高度一致

• 比较矮

m阶B数

• 节点可存储元素数量x

  • 根节点：1≤x≤m-1

  • 非根节点：ceiling(m/2)-1≤x≤m-1

• 节点子节点数 y = x+ 1

  • 根节点：2≤y≤m

  • 非根节点：ceiling(m/2)≤y≤m

六阶B数，非根节点子节点的个数 y : ceiling(6/2) ≤ y ≤ 6，（3，4，5，6）树，3-6树

数据库一般是200-300阶B树

B树与二叉搜索树的关系

n代节点合并，最多有2ⁿ个子节点，最少是2ⁿ阶B树

m阶B树，最多需要log₂m代合并

上溢 overflow

删除

删除：叶子节点直接删除，非叶子节点找到前驱或者后继节点，用前驱或后继节点覆盖需要删除的节点，然后删除掉该前驱或后继节点

下溢：旋转

下溢：合并