第十二章 B树

B-Tree (B-树) Balance-Tree

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

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

• 假设一个节点存储的元素个数是x
  • 根节点：1<= x <= m-1
  • 非根节点：ceiling(m/2) -1 <= x <= m-1
  • 如果有子节点，子节点的个数 y = x+1
  • 根节点的子节点个数：2<= y <=m
  • 非根节点的子节点个数：ceiling(m/2) <= y <= m
  • 当 m=3，2 <= y <= 3，因此称为（2，3）树、2-3树
  • 当 m=4，2 <= y <= 4，因此称为（2，4）树、2-3-4树
  • 当 m=5，3 <= y <= 5，因此称为（3，5）树
  • 当 m=6，3 <= y <= 6，因此称为（3，6）树
  • 当 m=7，4 <= y <= 7，因此称为（4，7）树
  • 如果 m=2，那么B树就是普通的二叉搜索树
  • 数据库中一般是200-300阶树

B树与二叉搜索树

B树添加元素

B树删除节点