4. B+树

B+树其实和B树是非常相似的。
相同点：

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

不同点：

1. B+树有两种类型的节点：内部结点（也称索引结点）和叶子结点。内部节点就是非叶子节点，内部节点不存储数据，只存储索引，数据都存储在叶子节点。
2. 内部结点中的key都按照从小到大的顺序排列，对于内部结点中的一个key，左树中的所有key都小于它，右子树中的key都大于等于它。叶子结点中的记录也按照key的大小排列。
3. 每个叶子结点都存有相邻叶子结点的指针，叶子结点本身依关键字的大小自小而大顺序链接
4. 父节点存有右孩子的第一个元素的索引

插入

1. 插入5，10，15，20

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

3. 接着插入26，30，继续分裂

删除

对于删除操作是比B树简单一些的，因为叶子节点有指针的存在。

1. 向兄弟节点借元素时，不需要通过父节点了，而是可以直接通过兄弟节点移动即可（前提是兄弟节点的元素大于m/2），然后更新父节点的索引。
2. 如果兄弟节点的元素不大于m/2（兄弟节点也没有多余的元素），则将当前节点和兄弟节点合并，并且删除父节点中的key。

初始状态

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

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