1、B树

插入

下面我们通过构造一棵2-3树来演示它的增删过程，假定初始数据为：[1, 7, 4, 9, 15, 13, 6, 5, 8, 10, 3, 12, 14, 2, 11]现在树为空，要把1插入进去只需要构建一个2结点即可，如下所示：

接下来插入元素7，只要把当前结点升级为3结点即可，如下所示：

接下来插入4，可以发现根结点已经是3结点了，因为必须是平衡的，所以只能把根结点拆开，变为3个2结点，如下所示：

插入9时，因为9比4大，所以插入到右侧，而7所在结点可以升级为3结点，所以插入结果如下所示：

接下来要插入15，因为9所在结点已经是3结点，但是它的父结点4是2结点，所以可以把4所在结点升级，因为3结点必须有三个孩子，所以7和9所在结点需要拆分，如下所示：

接下来插入13和6时，对应节点都可以升级，所以插入结果如下：

接下来插入元素5时，发现6所在结点已经是3结点，而父结点，也就是根结点也是3结点了，这时只能再次拆分。首先，5、6、7中间的数是6，我们把它提出来，它应该位于4和9中间，如下所示：

因为3结点只能有两个元素，所以根结点也必须拆分，结果如下：

可以发现，根结点拆分后使得树的高度增加了。接下来插入8，10，3也是重复步骤，结果如下：

至此，再插入元素12、14、2时也变得十分简单了，结果如下：

最后插入11，可以发现它在10和12之间，而父结点也是3结点，所以10和12要拆分，9和13也要拆分，11应该和6一起升级为3结点，结果如下：

注意：由于m=3，所以除了根节点意外，非叶子节点至少有[3/2]-1=1个关键字，最多有3-1=2个关键字

删除

现在，我们已经建立了一棵2-3树，我们按照插入顺序，再演示删除的过程。首先删除元素1，因为1是2结点，删除后会影响平衡，但是我们发现它的父结点是一个3结点，所以可以把父结点拆开，2和3合并成一个3结点，结果如下：

现在，要删除7，因为7是叶节点也是3结点，直接删除就可以，结果如下：

删除结点4，因为它的左孩子是3结点，只要把它拆开就可以了，结果如下：

删除9时比较复杂，因为它的左右孩子都是2结点，首先把它的两个孩子合并为3结点并代替它，结果如下：

此时树是不平衡的，此时发现左侧3和6可以合并为3结点，结果如下：

接下来删除15，直接删除即可，结果如下：

删除13也比较复杂，首先需要把它的两个孩子合并，然后以11为根结点，做类似右旋的操作，具体做法是6的右孩子成为11的左孩子，然后6成为11的父结点，这和AVL树等的右旋操作是一致的，结果如下：

接下来要删除的元素6是根结点，做法是先找到它的前驱（第一个比它小的元素）5代替它，此时2、3结点需要合并，合并后左右子树不再平衡，所以还需要5和11合并，结果如下：

其余的删除操作其实和前面的都类似，这里不再演示了，感兴趣的可以自己试一试，很快就可以发现规律。

查找

查找比较简单，从根节点开始使用二分查找

2、B+树

插入

B+ 树的特点是能够保持数据稳定有序，元素自底向上插入。

• 插入5，10，15，20

• 插入25，此时元素数量大于4个了，分裂

• 接着插入26，30，继续分裂

删除

对于删除操作是比B树简单一些的，因为叶子节点有指针的存在，向兄弟节点借元素时，不需要通过父节点了，而是可以直接通过兄弟节移动即可（前提是兄弟节点的元素大于m/2=2），然后更新父节点的索引；如果兄弟节点的元素不大于m/2（兄弟节点也没有多余的元素），则将当前节点和兄弟节点合并，并且删除父节点中的key，下面我们看看具体的实例。

• 初始状态

• 删除10，删除后，不满足要求，发现左边兄弟节点有多余的元素，所以去借元素，最后，修改父节点索引

• 删除元素5，发现不满足要求，并且发现左右兄弟节点都没有多余的元素，所以，可以选择和兄弟节点合并，最后修改父节点索引

• 发现父节点索引也不满足条件，所以，需要做跟上面一步一样的操作

查找

1. 在单元素查询的时候，B+树会自顶向下逐层查找节点，最终找到匹配的叶子节点。
2. B+树的范围查询则要简单的多，首先自顶向下查找范围的下限，然后只需要在叶子节点所在的链表上做遍历即可。