tips：
- 度数：在数中，每个节点的子节点（子树）的个数就称为该节点的度
- 阶数：阶定义为一个节点的子节点数目的最大值。
B树的定义
B树为一种平衡的多分树，对于一个m阶的B树，他必须满足条件：
- 如果根不是叶节点，则根至少有两个子节点
- 每个节点最多只有m个子节点
- 除根节点外，每个节点元素个数k>=(m/2[向下取整])
- 非叶子节点包含k+1个子节点
- 树的高度一致，所有叶子都出现在同一深度上
下面定义了一颗正确的三阶B树：
- 根节点有两个子节点
- 最少子节点的非叶子节点[12]拥有两个子节点，2>=⌈3/2⌉=(1.5)
- [3,6]的子节点有3个，[12]的子节点有两个。
- 树左右高度一致。
B树插入删除操作
插入
针对m阶高度h的B树，插入一个元素时，首先在B树中是否存在，如果不存在，即在叶子结点处结束，然后在叶子结点中插入该新的元素。
- 若该节点元素个数小于m-1,直接插入
- 若该节点个数等于m-1,引起节点分裂；以该节点中间元素为分解，取中间元素（偶数个数，中间两个随机选取）插入到父节点中；
- 重复上面动作，直到所有节点符合B树的规则；最坏的情况一直分裂到根节点，生成新的根节点，高度增加1；
定义一个5阶B树：
- 2<=根节点子节点个数<=5
- 3<=内节点子节点个数<=5
- 1<=根节点元素个数<=4
- 2<=非根节点元素个数<=4
插入元素8,后引起分裂，中间元素[7]成为父节点
插入元素[5],[11],[17]
插入元素[13]，引起分裂，[13]上移父节点
插入[6],[13],[20],[23]
插入[26]，引起分裂，中间元素[20]上移父节点
陆续插入[4],[16],[18],[24],[25]
插入[19],分裂后[17]上移后发现，父节点中空间也满了，继续分裂将中间节点向父节点的父节点移动，把[13]上移，成为新的根节点
删除
对B树删除已存在元素后，判断节点删除后是否符合B树要求，
若删除的是非叶节点，先合并该非叶节点的子节点元素，再判断合并后的元素个数是否小于m，否则分裂。
若删除的是叶节点中的元素，要先判断删除后的是否符合元素个数k>=(m/2[向下取整])，否则再判断其拥有最多元素的兄弟结点元素-1是否还符合B树结构，若符合则上移兄弟节点的最相近元素(“左兄弟最右边的元素”或“右兄弟最左边的元素”)到父节点中。然后向父借一个最相近元素（“上移兄弟为左借左，为右借右”），否则向左右兄弟合并。
依次删除下图5阶B树的节点[8]，[20],[18],[5]
删除元素[8]
删除元素[20],在非叶结点中，在其右孩子中选出最小元素上移到原[20]的位置中。并且右孩子节点中的元素依旧符合B树结构。
删除[18]，删除后，发现原节点只有一个[19]，不符合B树结构，判断左右兄弟节点-1后的情况，发现右兄弟符合，即将（右兄弟的最左元素）上移到父节点中，再将父节点中的相近元素下移。
删除元素[5],删除后发现，左右兄弟节点元素-1后都不符合，只能选一兄弟合并，合并后如下图
合并后发现，父节点元素不符合B树结构，发现父节点的兄弟元素-1后也不符合，再将父节点与其兄弟合并。
B+树定义
- 与B树相比，m阶B+树的非叶节点的子节点为m，比B树多一
- 每个中间节点元素不保存数据，只做索引
- 子节点中的元素包含了直接父节点元素
- 由于子节点包含了父节点的元素，所以所有叶子节点的元素就等于该树全部元素
- 叶子节点之间增加了横向指针，自小到大顺序连接起来
B+树插入删除操作
插入
往下图的3阶B+树中插入9
首先查找9应插入的叶节点，插入发现没有破坏B+树的性质，插入完毕。
往下图的3阶B+树中插入20
首先查找20应插入的叶节点，插入：
发现第二个叶子节点已经破坏了B+树的性质，则分解成[20,21],[37,44]两个，并把21往父节点移。
发现父节点也破坏了B+树的性质，则把父节点再分解成[15,21],[44,59],并把21往父节点移。
往下图的3阶B+树插入100
首先查找100应插入的节点，插入
修改其所有父节点的的键值为100（只有插入比当前树的最大数大的数时要做此步骤）
拆分节点
删除
删除下图3阶B+树的关键字91
首先找到91所在的节点，删除，没有破坏B+树的性质，完毕
删除下图3阶B+树的关键字97
首先找到97所在的叶子节点，删除，然后修改该节点的所有父节点的关键字为91（只有删除树中最大的关键字需要做此步骤）
删除下图3阶B+树的关键字51
首先找到51所在的叶子节点，删除
破坏了B+树的性质，向该节点的兄弟节点（左节点或右节点）借节点44，并修改相应键值。
删除下图3阶B+树的关键字59
首先找到59所在的叶子节点
破坏B+树的性质，尝试借节点，无效（因为左兄弟节点被借也会破坏B+树的性质），合并第二、第三叶节点，并调整键值
删除下图3阶B+树的关键字63
首先找到63所在的叶节点，删除
合并第四、第五节点并调整键值
第二层的第二个节点不满足B+树的性质，从第二层的第一个节点借59并调整键值
B树和B+树在磁盘上的应用
