1.B树简介

B树是一种多路平衡搜索树。它由二叉树变换而来的。定义如下：
1.1每个节点最多有m-1个关键字
1.2根节点最少有1个关键字
1.3非根节点至少有m/2个关键字
1.4每个节点的关键字都是按照从小到大的顺序排列，每个关键字的左子树中的关键字都小于它，而右子树中所有关键字都大于它。
1.5所有的叶子节点都处于同一层，或者说根节点到每个叶子节点的长度都相同
1.6每个节点存储有索引与数据。
因此，根节点的关键字数量范围：1<=k<=m-1；非根节点关键字数量范围m/2<=k<=m-1。
注意：描述一颗B树时必须要指明它的阶数(m)，阶数表示一个节点最多有多少个孩子节点。

2.B树插入数据过程

假设5阶B树，则节点最多有4个key，最少有2个key。现要插入6、10、4、14、5、11、15、3、12等数据。
2.1 插入6、10、4、14到根节点，则根节点中数据是4、6、10、14。
2.2 插入5时出现裂变，根节点变成6，左子树节点变成4、5，右子树节点变成10、14。
2.3 接着插入11、15、3三个数据，逐个与根节点比较，比较过程如下：
2.3.1 11与6比较，大于6，则插入6的右子节点，得到数据10、11、14
2.3.2 15与6比较，大于6，则插入6的右子节点，得到数据10、11、14、15
2.3.3 3与6比较，小于6，则插入6的左子节点，得到数据3、4、5
2.3.4 12与6比较，大于6，则插入6的右子节点，得到数据10、11、12、14、15，注意此时又需要裂变了。此时的数据结构如下

根：6
左：3、4、5
右：10、11、12、14、15(需裂变)

很明显，取中间的数据12到根节点，重新得到的平衡树如下

根:6、12
左：3、4、5
中：10、11
右：14、15

裂变的本质是：尽可能使这个树矮，因为矮意味着磁盘I/O次数少。

3.B树删除数据过程

首先查找B树中是否存在需要删除的元素，如果存在，则删除该元素，之后判断该元素是否存在左右孩子节点，如果有，则上移孩子节点中相近元素(左孩子最右边节点或者右孩子最左边节点)到父节点中；如果没有，则直接删除。
假设如上B树中需要删除14、12节点，步骤如下：
3.1 删除14节点，不会对树的平衡有任何影响，所以直接删除了；但是如果接着再删除15节点，就影响树的平衡了，需要重新裂变了。
3.2 删除12节点，12节点左子树有10、11，右子树有15。如果我们将15移上去，得到如下树：

根:6、15
左：3、4、5
右：10、11

我们发现这种树不可能，需要重新裂变；那么我们选择将11移上去，得到如下树：

根:6、11
左：3、4、5
中：10
右：15

我们发现这种树是平衡的，满足要求。

4.B树搜索数据过程

假设我们要搜索节点10，步骤如下：
4.1 10与根节点比较，不等于6，则再跟11比较，发现小于11，那么就会与11的左子树中第一个节点比较，刚好是10，则查询到了。2级查询到数据，则需要操作2次磁盘I/O。从这里我们也可以知道，树越矮，则磁盘操作越少，速度越快。

5.B+树简介

B+树是B树的变种。它与B树的关系如下：
相同点:

1>根节点至少有一个元素
2>非根节点元素范围：m/2<=k<=m-1

不同点：

1>B+树有两种类型节点：内部节点(也称索引节点)与叶子节点。内部节点只存储索引，不存储数据；叶子节点存储数据。
2>每个叶子节点都存有相邻叶子节点的指针，叶子节点本身依关键字有小到大顺序链接。

6.B+树插入数据过程

B+树插入数据与B树插入过程基本相同，不同的是：遇到裂变时，中间key变成根节点，同时中间key要成为右子树的第一个key。
假设5阶B+树，向B+树插入5、8、10、15、16、17、18数据过程如下：
6.1 插入5、8、10、15到根节点，则根节点中索引是5、8、10、15，注意索引中有值。
6.2 再插入16索引，则需要裂变，取索引10作为根节点，10同时要作为右子树第一个索引，得到的数据如下：

根:10
左:5、8
右：10、15、16

6.3 再插入17，不会裂变，插入18时，得到的数据如下：

根:10
左:5、8
右：10、15、16、17、18

此时需要裂变，取中间节点到根节点，得到如下数据：

根:10、16
左:5、8
中:10、15
右:16、17、18

自此结束。
注意：B树与B+树最显著的区别是B+的节点存放索引+数据，B+树内部节点存放索引，叶子节点存储数据。