1.B+树的定义
1.
由于B树的规则较为繁琐，比如孩子的数量比关键字的数量多一个，这就导致我们在实现代码时，需要不断的注意下标之间的关系，这就有点麻烦，同时在实际数据库底层使用数据结构来作为磁盘中数据的存储管理时，发现B树并没有那么的使用，于是在B树的基础上延申出了B+树，变的更加实用。
2.
B+树结点的关键字数量与孩子的数量一致，每个关键字只会对应有一个孩子，关键字是孩子中存储的所有key中最小的，这就有点类似于书籍的目录，目录上每行都会标注一个页码，比如第一行是书记的序言，后面标注一个3，下一行是第一回xxxx后面标注一个25，下下行是第二回xxxx后面标注一个50，那么3到25页之间的内容就是序言，25到50的内容就是第一回，而B+树的结点就十分类似于书籍的目录，每个关键字下面的孩子存的值都比关键字大。同时B+树的叶子节点之间用指针串联成了一个单链表。所有的关键字和其对应的映射值，都存储在叶子结点中，而非叶子结点只存储能够找到叶子结点的索引值。
从下图就可以看出B+树其实就是一个多层索引的多叉平衡搜索树，所有的关键字和其对应的value值都会存储在叶子结点中，而非叶子结点只存储用于找到叶子结点的索引值，所以在B+树当中，所有关键字都插入到了叶子结点当中。
当然下面的叶子结点没有关键字对应的value值，可以将他看作一个只存储K的B+树，只要我们能实现存储K的B+树，也就能够实现存储KV的B+树，无非就是将key换成pair键值对嘛。
2.B+树的插入
1.
在实现B+树的代码时，因为B+树的结点孩子数量和关键字数量相同，所以一个M路的B+树结点最多能够存储M个结点，但是在实现上与B树思想类似，我们希望能够将target先插入到结点之后，再进行分裂，所以B+树的结点也会为关键字数组多开一个空间，也就是M+1的大小，孩子的空间与关键字空间保持一致，也是开M+1的大小。
（1）在插入节点时，B+树的第一步就与B树不同了，因为B树的所有结点都可以存储关键字和value值，所以当B树为空进行插入时，只需要创建一个根节点，然后将第一个值插入进去即可，但B+树是将索引和关键字分开了，非叶子结点只存储索引，叶子结点才去存储关键字，所以当B+树为空进行插入时，需要创建出两个结点，一个作根用来存储索引，一个作叶子用来存储关键码，只不过在我下面画的图中，53第一次既作关键码又作了索引。
（2）同时B+树结点的分裂规则也与B树结点不同，当B+树结点满了之后，则需要拷贝一半的值给兄弟结点，然后把兄弟结点中存储的最小关键字，也就是keys数组的第一个值插入到父节点中，同时把bro结点作为孩子插入到父节点的孩子数组中。B+树的结点分裂实现起来其实是要比B树结点分裂容易的，因为不需要过多的关注keys和childs之间的下标关系。
（3）B+树的分裂虽然比B树实现起来要简单，但B+树的插入要比B树多考虑一种情况，由于B+树非叶子节点存储的是索引，所以有一种特殊的情况就是当在最左边最下面的叶子节点插入一个小于当前叶子结点中所有关键字的target目标值时，要多做一个向上迭代更新非叶子节点存储索引值的操作，这种情况在实现向叶子节点插入target时，要特殊处理一下。
（4）由于B+树的所有叶子结点要串成一个单链表，所以当创建出新的叶子结点时，还要多进行一个链接指针的操作，保证所有的叶子结点在一个链表中，B+树中除了包含根节点之外，另外包含的一个data指针就是叶子节点单链表的伪头部节点。
2.
在真正实现代码时，还是老规矩，不要硬刚的写，因为容易漏掉某些特殊情况和细节，一定要对照着上面的图，保证把所有情况考虑到位了，然后再开始写，我个人写这种复杂代码时的习惯就是多给点注释，时时刻刻提醒自己写到哪一步了，下一步该写什么。
Insert算法流程为：(1) 先判断B+树是否为空，如果为空，则我们创建两个B+树节点，一个作根一个作叶子，把插入的第一个值插入到根和叶子当中。(2) 插入第二个值时，B+树就不为空了，此时要先做target值在B+树中的搜索，如果值已经存在，则返回target所在的叶子节点的指针与target的下标位置，如果值不存在，则返回target如果要插入，则应该插入的叶子节点的指针和target如果要插入，则应该插入在叶子节点当中的哪个下标位置。(3) Search返回之后，如果target存在，则直接返回false。如果target不存在，则根据插入排序的思想将target插入到相应的叶子节点中，插入这里还需要分两种情况，一种是将target插入到叶子节点的头部位置，这种情况下，插入完成之后，还需要向上迭代更新父节点存储的索引值，另一种普通情况就是插入到叶子节点的非头部位置，这种情况下直接根据插入排序的思想进行插入即可。(4) 插入节点之后，下一步则判断叶子节点是否满了，如果没满则Insert算法结束，返回true即可，如果满了则需要进行分裂，将一半的值拷贝给兄弟节点，然后向父节点插入兄弟节点的最小关键字，以及将兄弟节点插入到父节点的childs数组中作为孩子，这里的插入依旧是按照插入排序思想走的，先挪动后插入，在挪动的时候，不仅仅要挪动父节点的关键字，还要挪动关键字相应的孩子，最终把bro节点和他的第一个关键字插入到父节点的正确位置上。这算是判断完叶子节点是否满了，接下来还需要向上继续进行迭代，判断插入bro节点后的父节点是否也满了，所以在while循环内部的最后一行，做一个指针迭代的工作即可。
Search算法流程：(1) 在搜索一个值时，肯定是先从根节点开始查找，查找肯定只有找到和没找到这两种情况，我们先来说找得到的这种情况，从0下标开始遍历根节点的keys数组，如果下标位置的值小于等于target，则向后i++，直到当前i位置的值大于target时，则说明target应该在i-1下标的child内，此时cur指针迭代到下一层，也就是赋值为cur->_childs[i - 1]，下一层的判断依旧如此，直到cur迭代到nullptr为止，而在迭代的过程中，还需要一个pre节点来保存cur的前一个位置，这样当cur迭代到nullptr时，pre保存的刚好就是B+树的叶子节点，Search直接返回pre与当前的i下标即可。这里需要注意的一个很容易忽略的问题是，如果在非叶子节点我们就找到了target，我们其实最好是不要直接返回的，而是应该继续向下跳，返回叶子节点中的target下标和叶子节点指针，为什么这么搞呢？如果你只希望Search提供判断查找一个值是否存在的功能，那么在向下搜索的过程中，提前找到target（比如target就是一个索引值，那刚好就可以在非叶子节点找到）可以直接返回，如果你想通过Search来查找到某个target之后，并对其进行修改，那提前返回非叶子节点就不行了，因为修改值必须要修改叶子节点，你修改的是关键字啊，而非叶子节点存储的只是索引啊，所以最好不要直接返回非叶子节点。（2）另一种查找情况就是没找到，没找到这里其实可以细分为三种情况，第一种是查找的值小于B+树根节点的第一个索引值，这种情况其实就是所谓的更新非叶子节点存储索引值的情况了，这种情况我们就让cur不断向每层非叶子节点的第一个孩子处进行迭代，最终返回第一个叶子节点和0下标索引，对于这种情况Insert在插入target之后要向上迭代更新父节点的索引值。第二种情况就是常规情况，target可以插入到叶子节点的中间位置，即非首节点的其他有效位置处(包括最后一个有效下标位置)。第三种情况就是target大于keys数组中的所有值，target应该尾插到叶子节点中。
3.
我在实现过程中出现的问题：（1）在写Search的实现时，跳出for循环有两种情况，一种是break跳出，另一种是i++跳出的循环，对于i++跳出循环的这种情况我给忽略掉了，这种情况其实对应的就是target大于keys数组中所有的关键字的情况。（2）分裂节点时，如果pos和bro是叶子节点则需要把_next指针链接起来，但如何判断此时的pos是否为叶子节点呢？这也是在实现一半的时候发现存在这样一个问题，所以我给struct BPlusTreeNode的定义中加了一个标志位_IsLeaf，如果是叶子节点，我们才会在分裂节点的时候把pos和bro链接起来，如果是非叶子节点进行分裂时，并不会将两者链接起来（3）在向父节点插入bro的第一个关键字时，因为当时画的例图所有的bro刚好都是插入到父节点的尾巴上面，所以我在实现时也只是将bro尾插到了par节点当中，这样做其实是完全错误的，必须按照插入排序的思想来将bro插入到par中，即先挪动后插入。
3.B*树的定义
1.
B *树是在B+树上做出微调后形成的数据结构，调整如下：
(1) 在非叶子节点之间增加了兄弟指针
(2) B *树最少允许存储3分之2M个节点，代替了B+树的最少1/2个结点，最多允许存储M个节点，当B *树的结点满了之后，他会先判断他的兄弟结点是否满了，如果没满，则将自己的一部分数据拷贝到兄弟结点，然后再将target插入到叶子结点（称为pos）中，如果兄弟也满了，则创建新的中间结点，将pos的后半部分的1/3和bro的前半部分的1/3拷贝到中间结点中，然后再将新创建的中间节点作为孩子链接到par结点中。
通过上述的规则可以看出B *树结点存储关键字的下限是2/3×M，并且只有当pos和bro同时满的时候，两者才会进行分裂，产生新节点的概率也尽可能的降低了，所以总结一下，B *树相比B+树来说空间利用率会更高一些。
4.B树系列总结
1.
在实际使用中，B树和B+树的使用率是最高的，而B *树用的是最少的，B *树和B+树相比只是空间利用率更高了，但在磁盘中空间是管够的啊，所以B *树实际中并不那么实用，因为磁盘根本不缺空间。
B树和B+树对比的话，B树的所有结点都可以存储key和data，而B+树只有叶子结点才会存储key和data，非叶子结点只存储作为索引的key，所以B+树的叶子结点空间占用更大一些，而非叶子结点空间占用更少一些，同时B+树的叶子结点用指针链接成了一个带头单链表，对于数据库中存储表信息所使用的数据结构，大部分其实用的都是B+树，而不是B树，主要由于B树有以下几个优点：（1）B树的非叶子结点空间占用更少，在文件读取时，能够加载到内存中的非叶子节点相比B树来说会更多一些。（2）B+树所有的data都存在于单链表组织的叶子结点中，所以遍历起来很方便，对于去检查找来说会更优一些，确定某个作为起点的叶子结点后，则可以依次向后遍历到目的叶子节点。而B树相比B+树有什么优点呢？B+树如果要查找某个值进行返回，则必须迭代到叶子节点进行返回，而B树如果在非叶子节点就查找到的话，则可以提前返回。不过这一点优势也几乎为0，因为B+树和B树的高度都非常的低，提前返回可能就快了一点吧。
2.
在实际取出数据库中某个数据到内存时，会先把磁盘上B树或B+树组织的数据读取出来一部分，然后将其加载到内存中，在内存中，如果要在节点中查找某个目标值时，我们肯定要访问节点的keys数组，其实访问keys数组我们可以不用一个一个关键字的遍历，因为现在这个数组已经加载到内存了，并且数组存储的值还是有序的，所以我们可以直接使用二分查找，确定好target所在的下标位置后，再次进行磁盘IO，target所在的孩子节点读取出来，所以用B树或B+树来存储管理磁盘上的数据效率是很高的
3.
B树可以看作是有序数组+平衡搜索树，而B+树可以看做成有序数组+平衡搜索树+单链表，B*树可以看作一棵节点存储的更加丰满，空间利用率更高的B+树。