B-树，就是B树，B树的原英文名是B-tree,所以很多翻译为B-树,就会很多人误以为B-树是一种树、B树是另外一种树。其实，B-tree就是B树。
B树是一种多叉平衡查找树，我们之前所介绍的红黑树是二叉查找树结构，B树由于是多叉结构，对于元素数量非常多的情况下，树的深度不会像二叉结构那么大，可以保证查询效率。
B树的性质（m阶的B树）
- 树中每个结点最多含有m个孩子（m>=2）；
- 除根结点和叶子结点外，其它每个结点至少有[ceil(m / 2)]个孩子（其中ceil(x)是一个取上限的函数）；
- 根结点至少有2个孩子（除非B树只包含一个结点：根结点）；
- 所有叶子结点都出现在同一层，叶子结点不包含任何关键字信息(可以看做是外部结点或查询失败的结点，指向这些结点的指针都为null)；（注：叶子节点只是没有孩子和指向孩子的指针，这些节点也存在，也有元素。类似红黑树中，每一个NULL指针即当做叶子结点，只是没画出来而已）。
- 每个非终端结点中包含有n个关键字信息： (n，P0，K1，P1，K2，P2，......，Kn，Pn)。其中：
a) Ki (i=1...n)为关键字，且关键字按顺序升序排序K(i-1)< Ki。
b) Pi为指向子树根的结点，且指针P(i-1)指向子树种所有结点的关键字均小于Ki，但都大于K(i-1)。
c) 关键字的个数n必须满足： [ceil(m / 2)-1]<= n <= m-1。比如有j个孩子的非叶结点恰好有j-1个关键码。
B树的插入
根据B树的性质，一个m阶的B树需要满足：
- 树中每个结点含有最多含有m个孩子，即m满足：ceil(m/2)<=m<=m。
- 除根结点和叶子结点外，其它每个结点至少有[ceil(m / 2)]个孩子（其中ceil(x)是一个取上限的函数）；
- 除根结点之外的结点的关键字的个数n必须满足： [ceil(m / 2)-1]<= n <= m-1（叶子结点也必须满足此条关于关键字数的性质）。
针对一棵高度为h的m阶B树，插入一个元素时，首先在B树中是否存在，如果不存在，一般在叶子结点中插入该新的元素，此时分3种情况：
如果叶子结点空间足够，即该结点的关键字数小于m-1，则直接插入在叶子结点的左边或右边；
如果空间满了以致没有足够的空间去添加新的元素，即该结点的关键字数已经有了m个，则需要将该结点进行“分裂”，将一半数量的关键字元素分裂到新的其相邻右结点中，中间关键字元素上移到父结点中，而且当结点中关键元素向右移动了，相关的指针也需要向右移。
此外，如果在上述中间关键字上移到父结点的过程中，导致根结点空间满了，那么根结点也要进行分裂操作，这样原来的根结点中的中间关键字元素向上移动到新的根结点中，因此导致树的高度增加一层。
插入以下字符字母到一棵空的5阶B 树中：C N G A H E K Q M F W L T Z D P R X Y S
分析： 根据上面的性质总结，5阶的B树，非根节点关键字个数n满足2<=n<=4,每个节点最多含有5个孩子，除根节点叶子节点之外，其他节点至少3个孩子。
-
关键字个数最大4，先取前4个插入到相同的节点中。
1.jpg -
插入H，因为步骤一后空间不够，就需要将中间关键字元素上移到父结点中，树增加一层
2.jpg -
在步骤二的图中，可以继续插入E,K,Q三个节点，继续插就得分裂
3.jpg -
插入M将进行分裂，M刚好是中间元素，直接上移到父节点中，HK、NQ分开为两个节点
4.jpg -
如步骤四的图中可以继续插入F,W,L,T
5.jpg -
在步骤五之后，插入Z就得进行分裂，T上移到父节点
6.jpg -
如步骤六的图中插入D,进行分裂，D上移到父节点中，然后插入后续的P,R,X,Y节点没有分裂
7.jpg -
插入最后一个S，含有N,P,Q,R的节点需要分裂，Q上移，导致父节点D,G,M,T也满了，也需要进行分裂，继续将中间元素M上移，产生新的节点，树高度再加一层。
8.jpg
B树的删除
首先查找B树中要删除的元素，若元素存在，则进行删除。删除该元素后，需要判断该元素是否有左右孩子节点
- 如果有，则上移孩子节点中的相近元素(左孩子中最右边的节点或者右孩子中最左边的节点)到父节点中去，移动之后的情况。
- 如果没有，直接删除，移动之后的情况。
删除元素，然后进行元素移动之后，如果节点关键字数目不满足条件(小于ceil(m/2)-1),则需要看其相邻的兄弟节点是否丰满(关键字个数大于ceil(m/2)-1)
- 如果丰满，则向父节点借一个元素来满足
- 如果其相邻兄弟都刚脱贫，即借了之后其结点数目小于ceil(m/2)-1，则该结点与其相邻的某一兄弟结点进行“合并”成一个结点，以此来满足条件。
对刚刚插入的树进行删除操作，依次删除H,T,R,E
-
删除H,在叶子节点H,K,L中，删除后还剩两个关键字，能够满足不小于ceil(m/2)-1=2，进行简单的删除元素后面的元素向前移动即可。
d1.jpg -
删除T,QT节点不满足关键字要求，需要上移孩子节点中相近元素W
d2.jpg -
删除R,删除后RS节点只剩一个关键字，根据上面的分析，兄弟节点丰满，就向父节点借一个W,同时X需要上移到父节点中去。
d3.jpg -
删除E,删除后EF节点只剩一个关键字，根据上面分析，兄弟节点刚脱贫，则需要跟相邻兄弟节点合并，D在两个需要合并的节点之间，所以需要下移到之前的AC节点中，将仅剩的F进行合并，形成ACDF节点
d4.jpg
但是我们发现中间有一个节点只包含一个关键字，并且该节点非根节点，这个就需要进行修改。接下来进行分析：如果相邻兄弟节点丰满，可以从父节点中进行借一个元素，但是我们右边的QX节点并不丰满，所以只能下移M节点，减少树的高度。最终图如下：
d5.jpg
B+树
B树的一种变形树，m阶的B+树和m阶的B树区别：
- 所有叶子节点包含全部关键字信息，及指向含有这些关键字记录的指针，且叶子节点中关键字进行有序链接
- 非叶子结点相当于是叶子结点的索引（稀疏索引），叶子结点相当于是存储（关键字）数据的数据层；
B+树比B树更适合操作系统的文件索引和数据库索引的原因：
- B+树的磁盘读写代价更低，B+树的内部节点没有指向关键字具体信息的指针，因此内部节点相对B树更小。如果把所有同一内部节点的关键字放在同一块磁盘中，盘块所能容纳的关键字数量也就越多，一次性读入内存中的需要查找的关键字也就越多，相对IO读写次数降低
举个例子，假设磁盘中的一个盘块容纳16bytes，而一个关键字2bytes，一个关键字具体信息指针2bytes。一棵9阶B-tree(一个结点最多8个关键字)的内部结点需要2个盘块。而B+
树内部结点只需要1个盘快。当需要把内部结点读入内存中的时候，B 树就比B+ 树多一次盘块查找时间(在磁盘中就是盘片旋转的时间)。
- B+树的查询效率更加稳定
由于非终结点并不是最终指向文件内容的结点，而只是叶子结点中关键字的索引。所以任何关键字的查找必须走一条从根结点到叶子结点的路。所有关键字查询的路径长度相同，导致每一个数据的查询效率相当。
总而言之，B树在提高了磁盘IO性能的同时并没有解决元素遍历的效率低下的问题。正是为了解决这个问题，B+树应运而生。B+树只要遍历叶子节点就可以实现整棵树的遍历，支持基于范围的查询，而B树不支持range-query这样的操作（或者说效率太低）。
B树*
B*树是B+树的变体，在B+树的非根和非叶子结点再增加指向兄弟的指针；
B+树的分裂：当一个结点满时，分配一个新的结点，并将原结点中1/2的数据复制到新结点，最后在父结点中增加新结点的指针；B+树的分裂只影响原结点和父结点，而不会影响兄弟结点，所以它不需要指向兄弟的指针。
B*树的分裂：当一个结点满时，如果它的下一个兄弟结点未满，那么将一部分数据移到兄弟结点中，再在原结点插入关键字，最后修改父结点中兄弟结点的关键字（因为兄弟结点的关键字范围改变了）；如果兄弟也满了，则在原结点与兄弟结点之间增加新结点，并各复制1/3的数据到新结点，最后在父结点增加新结点的指针。
总结
B-树：多路搜索树，每个结点存储M/2到M个关键字，非叶子结点存储指向关键字范围的子结点；所有关键字在整颗树中出现，且只出现一次，非叶子结点可以命中；
B+树：在B-树基础上，为叶子结点增加链表指针，所有关键字都在叶子结点 中出现，非叶子结点作为叶子结点的索引；B+树总是到叶子结点才命中；
B*树：在B+树基础上，为非叶子结点也增加链表指针，将结点的最低利用率从1/2提高到2/3；
借鉴于July大神的分析
