B树和B+树

一棵m阶B树，或者是空树，或者满足如下特性

1. 树中每个节点最多有m棵子树，且至多有m-1个关键字

2.若根节点不是叶子节点，那么至少两棵子树，至少一个关键字

3.除了根节点以外的节点，每个非叶节点至少有m/2向上取整棵子树

4.所有叶子节点（在B树中视为外部结点）都在同一个层面上

5.各个结点内关键字按照升序或者降序排列

B树所有结点都包含信息

B树的插入，如果一个结点插入后关键字个数为m，那就需要进行分裂，如果影响到了根节点，会使得B树高度加一

分裂的具体过程，将中间的数提到上面即可，然后两边结点进行分裂

最多需要3h+1次IO操作（影响到根节点）

B树的删除，如果一个结点删除后关键字个数小于最少个数，那么就需要进行合并

删除的步骤：

        1. 直接删除关键字（如果删除后没有破坏B树的性质）

        2. 破坏了，兄弟够借，就是将兄弟的一个元素放到父亲，然后父节点的一个元素降落下来

        3.兄弟不够借，那就将父亲的一个结点和自己的兄弟合并起来

在B+树中

1.每个关键字对应一棵子树

2.每个结点的关键字范围是m/2向上取整<=n<=m

3.叶子结点包含全部关键字，叶子结点包含信息，非叶子结点索引只包含对应子树最大关键字和指向该子树的指针

B+树的非叶子结点仅起到索引作用，查找成功需要查找到叶子结点，即每次查找长度都相同（保证查找公平性）

B+树支持顺序查找，所有叶子结点类似于一个链表结构

B树和B+树都能够有效支持随机查找