面试官问你B树和B+树，就把这篇文章丢给他

接着删除28，删除叶子节点，删除后不满足要求，所以，我们需要考虑向兄弟节点借元素，但是，兄弟节点也没有多的节点(2个)，借不了，怎么办呢?如果遇到这种情况，首先，还是将先将父节点的元素移到该节点，然后，将当前节点及它的兄弟节点中的key合并，形成一个新的节点。

移动之后，跟兄弟节点合并。

删除就只有上面的几种情况，根据不同的情况进行删除即可。

上面的这些介绍，相信对于B树已经有一定的了解了，接下来的一部分，我们接着讲解B+树，我相信加上B+树的对比，就更加清晰明了了。

2 B+树

2.1 B+树概述

B+树其实和B树是非常相似的，我们首先看看相同点。

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

不同点。

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

下面我们看一个B+树的例子，感受感受它吧!

2.2 插入操作

对于插入操作很简单，只需要记住一个技巧即可：当节点元素数量大于m-1的时候，按中间元素分裂成左右两部分，中间元素分裂到父节点当做索引存储，但是，本身中间元素还是分裂右边这一部分的。

下面以一颗5阶B+树的插入过程为例，5阶B+树的节点最少2个元素，最多4个元素。

插入5，10，15，20

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

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

有了这几个例子，相信插入操作没什么问题了，下面接着看看删除操作。

2.3 删除操作

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

初始状态

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

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

（编辑：威海站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!