目录
1.来由
2.定义
2.1内部结点
2.2外部结点（失败结点）
2.3阶
3.性质
3.1平衡
3.2有序
3.3多路
4.查找
4.1成功
4.2失败
5.插入
4.1不用调整
4.2需要调整
4.3多次调整
4.4根节点溢出
6.构建
7.删除
7.1不用调整
7.2出现下溢出
7.3兄弟不够借
7.4父结点下溢出
7.5根节点下溢出
1.来由
二叉搜索树及其平衡优化版本的AVL树和红黑树都可以是数据的查找，插入，删除以O(log n)的效率进行；
但是上述的数据结构进行操作时必须事先将要维护的数据读入内存，这导致数据极大时不可能完全读入内存，这就需要不断的从外存中读入数据；
要知道CPU和磁盘之间的速度差异超级大，要是依然使用上述数据结构时，读一个结点就要访问磁盘一次，数据量越是庞大，二叉搜索树就越高，访问磁盘次数增加，导致效率及其低下；
而B树就应运而生，它可以极致的降低树高来一次减少访问磁盘的次数，从而提高效率。
其也可以唤作“多叉平衡搜索树”。
2.定义
2.1内部结点
2.2外部结点（失败结点）
2.3阶
M阶的B树的结点最多有M个分支。
3.性质
3.1平衡
所有叶子结点都在同一层。
3.2有序
首先，结点内有序；
再者，任意一元素的左子树都小于他，任意一元素的右子树都大于他；
3.3多路
既有上限，也有下限。
| 对于M阶B树的结点： | ||
| 最多 | 有M个分支，M-1个元素； | |
| 最少 | 根节点： | 2个分支，一个元素； |
| 其他结点： | [M/2]个分支，[M/2]-1个元素； | |
4.查找
4.1成功
4.2失败
5.插入
无论是几阶，方法都一样，先用查找的方式找到插入的位置（一定在叶节点），最后再看是否要进行调整。
| 1. | 先查找到插入的位置进行插入(插入位置一定在叶结点) |
| 2. | 如果没有上溢出，无需调整 |
| 3. | 否则中间元素[m/2]上移,两边分裂 |
| 4. | 直到没有上溢出为止 |
4.1不用调整
没有超出元素个数的上限，不需要调整。
4.2需要调整
4.3多次调整
4.4根节点溢出
6.构建
7.删除
| 删除非叶结点 | 删除非叶结点上的数都会转化为删除叶结点上的数； | ||
| 删除叶节点 | 没有下溢出 | 无需调整 | |
| 下溢出 | 兄弟够借 | 父下来，兄上去 | |
| 兄弟不够借【合并，可能导致父结点下溢出】 | 父下移动到左，然后并过去 | ||
7.1不用调整
用叶子结点中的元素的前驱或者后继来替换：
7.2出现下溢出
出现下溢出，问左右兄弟借一个：
父下来，兄上去：
7.3兄弟不够借
父亲下移到左，然后右并过来。
或者：
7.4父结点下溢出
7.5根节点下溢出
)
