b树
在计算机科学中，B树（B-tree）是一种树状数据结构，它能够存储数据、对其进行排序并允许以O(log n)的时间复杂度运行进行查找、顺序读取、插入和删除的数据结构，普遍运用在数据库和文件系统。
我们描述一颗B树时需要指定它的阶数，阶数表示了一个结点最多有多少个孩子结点，，一般用字母m表示阶数。
使用B树的主要原因之一是它能够在单个节点中存储大量键，并且通过保持树的高度相对较小来存储大键值。
B树定义如下：
1.每个结点最多有m-1个关键字。
2.根结点至少有两个子女。
3.非根结点至少有Math.ceil(m/2)-1个关键字。
4.每个结点中的关键字都按照从小到大的顺序排列，每个关键字的左子树中的所有关键字都小于它，而右子树中的所有关键字都大于它。
5.所有叶子结点都位于同一层，或者说根结点到每个叶子结点的长度都相同。
搜索
在B树中搜索类似于二叉搜索树中的搜索。 例如，如果在以下B树中搜索数据项：49。 该过程将如下所示：
将数据项49与根节点78进行比较。因为49 <78因此，移动到其左子树。
因为，40 <49 <56，遍历右子树40。49> 45，向右移动。
比较49。找到匹配，则返回。
在B树中搜索取决于树的高度。 搜索算法需要O(log n)时间来搜索B树中的任何元素。
插入
插入在叶节点级别完成。要将项目插入B树，需要遵循以下算法。
遍历B树以找到可插入节点的适当叶节点。
如果叶节点包含少于m-1个键，则按递增顺序插入元素。
否则，如果叶节点包含m-1个键，则按照以下步骤操作。
按元素的递增顺序插入新元素。
将节点拆分为中间的两个节点。
将中值元素推送到其父节点。
如果父节点还包含m-1个键，则按照相同的步骤将其拆分。
删除
还在叶节点处执行删除。 要删除的节点可以是叶节点或内部节点。 需要遵循以下算法才能从B树中删除节点。
找到叶节点。如果叶节点中有多于m/2个键，则从节点中删除所需的键。
如果叶节点不包含m/2个键，则通过从8个或左兄弟中获取元素来完成键。
如果左侧兄弟包含多于m/2个元素，则将其最大元素推送到其父元素，并将插入元素向下移动到删除键的节点。
如果右侧兄弟包含多于m/2个元素，则将其最小元素向上推送到父节点，并将插入元素向下移动到删除键的节点。
如果兄弟节点都不包含多于m/2个元素，则通过连接两个叶节点和父节点的插入元素来创建新的叶节点。
如果父节点的节点少于m/2，那么也应在父节点上应用上述过程。如果要删除的节点是内部节点，则将节点替换为其有序后继或前一个节点。
由于后继或前任将始终位于叶节点上，因此该过程将类似于从叶节点中删除节点。
b+树
B+树是B树的变体，也是一种多路搜索树：
1.其定义基本与B-树同，除了：
2.非叶子结点的子树指针与关键字个数相同；
3.非叶子结点的子树指针P[i]，指向关键字值属于[K[i], K[i+1])的子树（B-树是开区间）；
5.为所有叶子结点增加一个链指针；
6.所有关键字都在叶子结点出现；B+的搜索与B树也基本相同，区别是B+树只有达到叶子结点才命中，B树可以在非空子节点命中。
适合文件索引系统，增删文件（节点）时，效率更高，因为B+树的叶子节点包含所有关键字，并以有序的链表结构存储，这样可很好提高增删效率。
mysql里面的全文索引就是使用的B+树结构。
b*树
是B+树的变体，在B+树的非根和非叶子结点再增加指向兄弟的指针。
B树定义了非叶子结点关键字个数至少为(2/3)M，即块的最低使用率为2/3（代替B+树的1/2）。
B+树的分裂：当一个结点满时，分配一个新的结点，并将原结点中1/2的数据复制到新结点，最后在父结点中增加新结点的指针；B+树的分裂只影响原结点和父结点，而不会影响兄弟结点，所以它不需要指向兄弟的指针。
B*树的分裂：当一个结点满时，如果它的下一个兄弟结点未满，那么将一部分数据移到兄弟结点中，再在原结点插入关键字，最后修改父结点中兄弟结点的关键字（因为兄弟结点的关键字范围改变了）；如果兄弟也满了，则在原结点与兄弟结点之间增加新结点，并各复制1/3的数据到新结点，最后在父结点增加新结点的指针。
参考链接：https://www.2cto.com/net/201808/773535.html
参考链接：https://www.yiibai.com/data_structure/b-tree.html