13518219792
原文链接：面试官问你B树和B+树，就把这篇文章丢给他
创新互联公司主要业务有网站营销策划、成都网站建设、成都做网站、微信公众号开发、小程序设计、HTML5、程序开发等业务。一次合作终身朋友，是我们奉行的宗旨；我们不仅仅把客户当客户，还把客户视为我们的合作伙伴，在开展业务的过程中，公司还积累了丰富的行业经验、营销型网站建设资源和合作伙伴关系资源，并逐渐建立起规范的客户服务和保障体系。
在介绍B+树之前， 先简单的介绍一下B树，这两种数据结构既有相似之处，也有他们的区别，最后，我们也会对比一下这两种数据结构的区别。
B树也称B-树,它是一颗多路平衡查找树。二叉树我想大家都不陌生，其实，B树和后面讲到的B+树也是从最简单的二叉树变换而来的，并没有什么神秘的地方，下面我们来看看B树的定义。
每个节点最多有m-1个关键字（可以存有的键值对）。
根节点最少可以只有1个关键字。
非根节点至少有m/2个关键字。
每个节点中的关键字都按照从小到大的顺序排列，每个关键字的左子树中的所有关键字都小于它，而右子树中的所有关键字都大于它。
所以，根节点的关键字数量范围：1 <= k <= m-1，非根节点的关键字数量范围：m/2 <= k <= m-1。
另外，我们需要注意一个概念，描述一颗B树时需要指定它的阶数，阶数表示了一个节点最多有多少个孩子节点，一般用字母m表示阶数。
我们再举个例子来说明一下上面的概念，比如这里有一个5阶的B树，根节点数量范围：1 <= k <= 4，非根节点数量范围：2 <= k <= 4。
下面，我们通过一个插入的例子，讲解一下B树的插入过程，接着，再讲解一下删除关键字的过程。
插入的时候，我们需要记住一个规则：判断当前结点key的个数是否小于等于m-1，如果满足，直接插入即可，如果不满足，将节点的中间的key将这个节点分为左右两部分，中间的节点放到父节点中即可。
例子：在5阶B树中，结点最多有4个key,最少有2个key（注意：下面的节点统一用一个节点表示key和value）。
插入22时，发现这个节点的关键字已经大于4了，所以需要进行分裂，分裂的规则在上面已经讲了，分裂之后，如下。
分裂，得到下面的。
更过的插入的过程就不多介绍了，相信有这个例子你已经知道怎么进行插入操作了。
B树的删除操作相对于插入操作是相对复杂一些的，但是，你知道记住几种情况，一样可以很轻松的掌握的。
m/2，这种情况只要直接删除即可。
此时发现26所在的节点只有一个元素，小于2个（m/2），这个节点不符合要求，这时候的规则（向兄弟节点借元素）：如果删除叶子节点，如果删除元素后元素个数少于（m/2），并且它的兄弟节点的元素大于（m/2），也就是说兄弟节点的元素比最少值m/2还多，将先将父节点的元素移到该节点，然后将兄弟节点的元素再移动到父节点。这样就满足要求了。
我们看看操作过程就更加明白了。
移动之后，跟兄弟节点合并。
删除就只有上面的几种情况，根据不同的情况进行删除即可。
上面的这些介绍，相信对于B树已经有一定的了解了，接下来的一部分，我们接着讲解B+树，我相信加上B+树的对比，就更加清晰明了了。
B+树其实和B树是非常相似的，我们首先看看相同点。
不同点。
下面我们看一个B+树的例子，感受感受它吧！
对于插入操作很简单，只需要记住一个技巧即可：当节点元素数量大于m-1的时候，按中间元素分裂成左右两部分，中间元素分裂到父节点当做索引存储，但是，本身中间元素还是分裂右边这一部分的。
下面以一颗5阶B+树的插入过程为例，5阶B+树的节点最少2个元素，最多4个元素。
有了这几个例子，相信插入操作没什么问题了，下面接着看看删除操作。
对于删除操作是比B树简单一些的，因为叶子节点有指针的存在，向兄弟节点借元素时，不需要通过父节点了，而是可以直接通过兄弟节移动即可（前提是兄弟节点的元素大于m/2），然后更新父节点的索引；如果兄弟节点的元素不大于m/2（兄弟节点也没有多余的元素），则将当前节点和兄弟节点合并，并且删除父节点中的key，下面我们看看具体的实例。
这样，B+树的删除操作也就完成了，是不是看完之后，觉得非常简单！
B+树相对于B树有一些自己的优势，可以归结为下面几点。
