1、概念

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

1.1、m阶B数的性质

假设一个节点存储的元素个数为x
根节点：1xm-1
非根节点：-1xm-1
如果有子节点，子节点个数y=x+1
根节点：2ym
非根节点： ym

4阶B树

1.2、B树VS二叉搜索树

B树和二叉搜索树在逻辑上等价的
多代节点合并可以获得一个超级节点
n代合并的超级节点，最多拥有个子节点（至少是阶B树）
m阶B树，最多需要代合并

1.3、搜索

跟二叉搜索树的搜索类似
1、先在节点内部从小到大开始搜索元素
2、如果命中，搜索结束
3、如果未命中，再去对应的子节点中搜索元素，重复步骤1

1.4、添加

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

1.5、在添加过程中可能会出现上溢的情况

m阶B树上溢的节点个数必然为m
1、假设上溢的位置为k，将k的元素向上与父节点合并
2、将[0,k]和[k+1,m-1]位置的元素分裂成2个子节点，这两个子节点的个数，必然都不会低于最低限制 -1
3、一次分裂完毕后可能会导致父节点上溢，依然按照上述方法解决，最极端的情况，可能一直分裂到根节点。
如下为5阶B树插入34元素的分裂过程

添加34

1.6、假如需要删除的元素在非叶子节点中

1、先找到前驱或后继元素，覆盖所需删除元素的值
2、再把前驱或后继元素删除

1.7、删除-下溢

叶子节点被删掉一个元素后，元素个数可能会低于最低限制（ -1）
这种现象被称为下溢
下溢节点的元素数量必然等于 -2
如果下溢节点临近的兄弟节点，有至少个元素，可以向下借一个元素