B+树是在B树的基础上实现的。

所谓m阶B-树，即m路平衡搜索树（m>=2）,也叫(ceil(m/2),m)-树，其有以下特点(设n为关键码,即n+1为分支数)：

1.除根以外的节点满足：n+1>=ceil(m/2)|n+1<=m;

2.非空的B-树,根节点满足：n+1>=2|n+1<=m(即最小为一个关键码)。

3.外部节点同属于底层，深度一致（即各节点分支状态相同，要么都不存在，要么都存在）。

4、外部节点远大于B树高度。

B+树在B-树的基础上添加了一个链表联接各个外部节点，每个叶子节点同时保存了关键码对应的记录，同时内部节点转化为了索引，而不再具有数据的功能,在实现上即内部节点保存的索引和关键码类型一样，叶子节点保存插入的关键码及完整的数据，再通过链表相连。

实现：

实现参考下面这个文章：

https://www.jianshu.com/p/71700a464e97

如果学过B-树的看完我下面的说明就可以手撸B+树了,不知道B-树的看完无法实现B+树。 注：不要只看链接的文章，那个文章细节没补充完整，那个文章只作为参考。

查找：所有树类数据结构的删除和插入功能都是基于查找实现的，由于内部节点不具有数据的功能，所以查找只能查叶子节点；那么自然有2中方式，一个是通过双向（或单向）链表查找，无疑对于单个的查找线性结构一般为O（logn）,而通过索引查找，由于B-树多分枝的关系，是远大于O（logn）。通过索引查找，即从树根一直查到叶子节点，然后记录恰当位置和命中节点。注：索引划分2个分枝，一般取右边为大于等于，左边小于。

插入:这里仅仅设定只能插入互异值，相同值由于上溢时发生索引2边都是相同值导致索引反而不在具有索引的性质，要插入相同值可以参考散列表的方法，建一个公共表或者每个叶子节点加一个表，反正建表是可以解决的。首先通过查找判断是否存在，存在则结束，不存在，则在叶子节点适当位置，插入节点，然后检测是否发生上溢。

如果分支数大于m，则：

1、对于非叶子节点的上溢和B-树一致（注：内部节点没有记录只有索引和孩子分支，叶子节点才有记录,千万不要把数据往内部节点放）

2、对于叶子节点的上溢则略有不同，当上溢时，对于floor(m/2)位置处的关键码提出来作为父节点的索引，在适当位置插入，同时这个关键码保留到分裂节点的右边，以保持索引的功能，然后还要维护链表的关系。

其它细节与B-树一致。

删除：和插入差不多，找到命中节点，没找到则返回。删除命中节点的关键码及记录和孩子分支后，做下溢检测，如下溢：

1、非叶子节点，与B-树一致。

2、叶子节点，则略有不同，因B-树是一颗完全二叉树，合并的时候我们一般优先同左兄弟合并，然后才考虑右兄弟，首先考虑借的情况：

（1）对于向左借，借一个最大的关键码插入作为最小关键码，为了维护索引关系，把最小关键码替换掉父节点的对应关键码；

（2）对于向右借，借一个最小关键码作为最大关键码，为了维护索引关系，把父节点中的对应关键码替换为右兄弟的最小码。

（3）如果不能借，则合并，与B-树不同的是不用把关键码下拉合并，因其为索引，合并后会有一个多余分支，删除掉一个，然后注意维护链表关系。

其它细节与B-树一致。

判断是否是叶子节点：因叶子节点有链表，可以通过链表last&&next判断，也可以根据B-树性质判断，即检测第一个孩子是否存在，不存在则为叶子节点。

代码：

这里是我放在github上实现数据结构教材里的一些算法c++代码，直接打开的就是B+树的实现：

https://github.com/iampby/algorithm_practice/tree/B+Tree