B树（多路平衡查找树）

1. 满足以下性质：
   1.每个结点至多m棵子树，至多m-1个关键字
   2.若根结点不是终端结点，至少有两根子树
   3.除根节点外，所有非叶结点至少有m/2下取整课子树，即至少含有m/2下取整-1个关键字
   4.所有叶结点都在同一层次（每个节点的子树高度一致），叶节点不携带信息，类似于查找判定树的失败节点，实际上这些点不存在，指向这些节点的指针为空
   一定是平衡的！，且关键字是排序的
2. 高度：
   高度不包括查找失败的叶子结点，就像上面所说，叶子结点实际上算是不存在的
   最小高度：
   
   最大高度：
   
3. 插入
   根本原则：除根节点之外，所有节点的关键字个数是xx~xx，且每个结点内部关键字有序
   情况一：
   若插入导致关键字书超过上限：
   从中间位置分裂成两个部分，右边部分放在新节点中，左边部分放在源节点中，中点位置插入源节点的父节点；新元素一定是插入到最底层的终端节点，用查找来确定插入位置
   
   
   情况二：
   若导致父节点的关键字也超过上限：
   
   
4. 删除：
   情况一：
   若被删除的关键字在终端节点：
   删除后关键字个数未低于下限，直接删除；
   低于下限：
   右兄弟够借，用当前节点的后继，后继的后继依次顶替空缺；
   左兄弟够借，用当前节点的前驱，前驱的前驱依次顶替空缺；
   左右兄弟都不够借，与父节点内的关键字+左兄弟或者右兄弟（所以会产生不同的B树）进行合并，（父节点也要下来当儿子），若导致父节点关键字低于下限，需要继续合并（父结点的父结点下来当儿子）。
   情况二：
   若删除的关键字在非终端节点：
   一定可以转化为终端结点删除；
   用直接前驱或者直接后继来替代被删除的关键字，随后删除这个直接前驱或者直接后继。

B+树

1. 满足以下性质