首先纠正下：B树也叫B-tree(B-树)【B-不可以读B减树 应该是B-tree】，所以B树和B-tree，B-树是同一个东西，只是不用的叫法 本文统一叫B-树
回归正题，先各自介绍下B树和B+树
B-树：平衡多路查找树，一颗度为m的B-树称为m阶B-树。一个节点有k个孩子时，必有k-1个关键字才能将子树中所有关键字划分为k个子集。B-树中所有孩子节点最大值称为B-树的阶，通常用m表示。从查找效率考虑，一般要求m>=3。
B-树满足一下要求：
1.树中的每个节点最多含有k个孩子，即满足m/2≤k≥m
2.除了根节点和叶子节点外，其他每个节点至少有m/2个孩子
3.根节点至少有两个孩子
4.所有的子节点都出现在同一层
5.每个节点中的元素从小到大排序
6.中间节点有k-1个关键字和k个孩子
B-树的基本操作
1.查询
如上是一个三阶B-树
假设我们要查询8是否在B-树中
1.从根节点出发，发现根节点关键字是9,8＜9往树的左边走，进入节点（2,6）
2.发现节点（2,6）有两个关键字，其中 8＞6，往树的右边走，进入（8）节点
3.发现（8）节点有关键字8，返回
说明下，在B-树中查找节点是在磁盘上进行的
在节点中查找关键字是将节点中的信息读到内存中，在利用顺序查找或者二分法查找
在内存中的效率要高与磁盘的效率
B-树的插入
1.通过上面的查找算法找到插入的位置
如果在B-树中找到关键字则直接返回，否会报错
2.判断查找到的节点上面的关键字是否满足n≤m-1，不满足就要对节点进行分裂
3.分裂的方法是：产生一个新的节点，把原节点上的关键字和要插入的关键字进行排序，然后从中间关键字分成两部分，左边部分的关键字放在原节点中，右边的关键字放在新的节点中，中间节点放到父节点中，如果父节点还是不满足条件，就继续分裂
下面我们来举例说明，首先假设这个B-树的阶为：3。树的初始化时如下：
首先，我需要插入一个关键字：30，可以得到如下的结果：
再插入26，得到如下的结果：
OK，此时如图所示，在插入的那个终端结点中，它的关键字数已经超过了m-1=2，所以我们需要对结点进分裂，所以我们先对关键字排序，得到：26 30 37 ，所以它的左部分为（不包括中间值）：26，中间值为：30，右部为：37，左部放在原来的结点，右部放入新的结点，而中间值则插入到父结点，并且父结点会产生一个新的指针，指向新的结点的位置，如下图所示：
OK，然后我们继续插入新的关键字：85，得到如下图结果：
正如图所示，我需要对刚才插入的那个结点进行“分裂”操作，操作方式和之前的一样，得到的结果如下：
哦，当我们分裂完后，突然发现之前的那个结点的父亲结点的度为4了，说明它的关键字数超过了m-1，所以需要对其父结点进行“分裂”操作，得到如下的结果：
好，我们继续插入一个新的关键字：7，得到如下结果：
同样，需要对新的结点进行分裂操作，得到如下的结果：
到了这里，我就需要继续对我们的父亲结点进行分裂操作，因为它的关键字数超过了：m-1.
哦，终于遇到这种情况了，我们的根结点出现了关键子数量超过m-1的情况了，这个时候我们需要对父亲结点进行分列操作，但是根结点没父亲啊，所以我们需要重新创建根结点了。
好了，到了这里我们也知道怎么进行B-树的插入操作。
B-树的删除操作
B-树的删除操作同样是分为两个步骤：
- 利用前述的B-树的查找算法找出该关键字所在的结点。然后根据 k（需要删除的关键字）所在结点是否为叶子结点有不同的处理方法。如果没有找到，则直接返回。
- 若该结点为非叶结点，且被删关键字为该结点中第i个关键字key[i]，则可从指针son[i]所指的子树中找出最小关键字Y，代替key[i]的位置，然后在叶结点中删去Y。
如果是叶子结点的话，需要分为下面三种情况进行删除。
- 如果被删关键字所在结点的原关键字个数n>=[m/2] ( 上取整），说明删去该关键字后该结点仍满足B-树的定义。这种情况最为简单，只需删除对应的关键字：k和指针：A 即可。
- 如果被删关键字所在结点的关键字个数n等于( 上取整）[ m/2 ]-1，说明删去该关键字后该结点将不满足B-树的定义，需要调整。
调整过程为：如果其左右兄弟结点中有“多余”的关键字,即与该结点相邻的右兄弟(或左兄弟)结点中的关键字数目大于( 上取整）[m/2]-1。则可将右兄弟(或左兄弟)结点中最小关键字(或最大的关键字)上移至双亲结点。而将双亲结点中小（大）于该上移关键字的关键字下移至被删关键字所在结点中。
- 被删关键字所在结点和其相邻的兄弟结点中的关键字数目均等于（上取整）[m/2]-1。假设该结点有右兄弟，且其右兄弟结点地址由双亲结点中的指针Ai所指，则在删去关键字之后，它所在结点中剩余的关键字和指针，加上双亲结点中的关键字Ki一起，合并到 Ai所指兄弟结点中(若没有右兄弟，则合并至左兄弟结点中)。
下面，我们给出删除叶子结点的三种情况：
第一种：关键字的数不小于（上取整）[m/2]，如下图删除关键字：12
删除12后的结果如下，只是简单的删除关键字12和其对应的指针。
第二种：关键字个数n等于( 上取整）[ m/2 ]-1，而且该结点相邻的右兄弟(或左兄弟)结点中的关键字数目大于( 上取整）[m/2]-1。
如上图，所示，我们需要删除50这个关键字，所以我们需要把50的右兄弟中最小的关键字：61上移到其父结点，然后替换小于61的关键字53的位置，53则放至50的结点中。然后，我们可以得到如下的结果：
第三种：关键字个数n等于( 上取整）[ m/2 ]-1，而且被删关键字所在结点和其相邻的兄弟结点中的关键字数目均等于（上取整）[m/2]-1
如上图所示，我们需要删除53，那么我们就要把53所在的结点其他关键字（这里没有其他关键字了）和父亲结点的61这个关键字一起合并到70这个关键字所占的结点。得到如下所示的结果：
Ok，我已经分别对上述的四种删除的情况都做了举例，大家如果还有什么不清楚的，可以看看代码，估计就可以明白了
；
B+树
B+树是B-树的变体，也是一种多路搜索树：
1.其定义基本与B-树同，除了：
2.非叶子结点的子树指针与关键字个数相同；
3.非叶子结点的子树指针P[i]，指向关键字值属于[K[i], K[i+1])的子树
（B-树是开区间）；
5.为所有叶子结点增加一个链指针；
6.所有关键字都在叶子结点出现；
如：（M=3）
B+的搜索与B-树也基本相同，区别是B+树只有达到叶子结点才命中（B-树可以在
非叶子结点命中），其性能也等价于在关键字全集做一次二分查找；
B+的特性：
1.所有关键字都出现在叶子结点的链表中（稠密索引），且链表中的关键字恰好
是有序的；
2.不可能在非叶子结点命中；
3.非叶子结点相当于是叶子结点的索引（稀疏索引），叶子结点相当于是存储
（关键字）数据的数据层；
4.更适合文件索引系统；
B树*
是B+树的变体，在B+树的非根和非叶子结点再增加指向兄弟的指针；
B树定义了非叶子结点关键字个数至少为(2/3)M，即块的最低使用率为2/3
（代替B+树的1/2）；
B+树的分裂：当一个结点满时，分配一个新的结点，并将原结点中1/2的数据
复制到新结点，最后在父结点中增加新结点的指针；B+树的分裂只影响原结点和父
结点，而不会影响兄弟结点，所以它不需要指向兄弟的指针；
B*树的分裂：当一个结点满时，如果它的下一个兄弟结点未满，那么将一部分
数据移到兄弟结点中，再在原结点插入关键字，最后修改父结点中兄弟结点的关键字
（因为兄弟结点的关键字范围改变了）；如果兄弟也满了，则在原结点与兄弟结点之
间增加新结点，并各复制1/3的数据到新结点，最后在父结点增加新结点的指针；
所以，B*树分配新结点的概率比B+树要低，空间使用率更高；
小结
B-树：多路搜索树，每个结点存储M/2到M个关键字，非叶子结点存储指向关键
字范围的子结点；
所有关键字在整颗树中出现，且只出现一次，非叶子结点可以命中；
B+树：在B-树基础上，为叶子结点增加链表指针，所有关键字都在叶子结点
中出现，非叶子结点作为叶子结点的索引；B+树总是到叶子结点才命中；
B*树：在B+树基础上，为非叶子结点也增加链表指针，将结点的最低利用率
从1/2提高到2/3；
