B树

一、定义

┌ a-1┐ 表示a-1向上取整，└a-1┘表示a-1向下取整

B树（Balance Tree）是一种平衡的多路搜索树，用于文件系统、数据库的实现。对于N阶B树，子节点个数最多为N，即子节点最多的个数为5的B树是一个5阶B树。

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

二、B树的性质

对于m阶B树(m>=2)，假设一个节点存储的元素的个数为x

1. 根节点的个数为：1 <= x <= m - 1
2. 非根节点的个数为：┌m/2┐ -1 <= x <= m - 1
3. 如果有子节点，子节点的个数：y = x+1，非根节点：┌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)树、3-4-5树。

B树和二叉搜索树，在逻辑上是等价的。

• 二叉搜索树多代节点合并，可以获得一个超级节点。

  2代合并的超级节点最多拥有4个子节点（至少是4阶B树）

  3代合并的超级节点最多拥有8个子节点（至少是8阶B树）

  n代合并的超级节点最多拥有2^n个子节点（至少是2^n阶B树）

• m阶B树，最多需要log2m代合并

B树新添加的元素必定是添加到叶子节点。

新添加的叶子节点的元素个数超过界限，则表示上溢。上溢节点的元素个数必定等于m（m阶B树）。

真正被删除的节点一定是叶子节点。（非叶子节点，替换前驱节点或后继节点。然后删除）

叶子节点被删除掉一个元素后，元素个数可能会低于最低限制。这种情况称之为下溢。下溢节点的元素个数必定等于┌m/2┐ -2

如果下溢节点临近的兄弟节点，有至少┌m/2┐个元素，可以向其借一个元素。（下溢节点的父节点进行旋转）

如果下溢节点的兄弟节点都是┌m/2┐-1个元素，将父节点元素挪下来，与两个左右子节点合并。合并以后的个数为：┌m/2┐ + ┌m/2┐ -2，不超过m-1。满足B树的性质