【数据结构】B树，B+树，B*树

一、B树

1.B树的定义

1.
在内存中搜索效率高的数据结构有AVL树，红黑树，哈希表等，但这是在内存中，如果在外部存储设备中呢？比如数据量非常的大，以致于内存中无法存的下这么多数据，从而只能将大部分的数据存储到磁盘上，那如果要在磁盘上进行查找呢？我们还用内查找效率高的这些数据结构吗？
由于大部分数据都在磁盘上，所以如果要查找某个数据，则只能先通过文件读取，将数据读取到内存中，然后在内存里面进行该数据的检索，如果存储结构是二叉搜索树，AVL树，红黑树，那树的高度是会比较大的，假设有10亿个数据，那么高度就将近30层，如果每层都做一次文件读取，那效率会非常的低，因为磁盘的访问速度和内存相比差距很大，算法导论上给出的数据，两者的访问速度相差大约10w倍，而且30层的高度，那总体下来的运行时间就是内存访问速度的300w倍，那search算法的效率瓶颈就全部压到了磁盘读取上，所以内查找优秀的这几个数据结构也不适用，有人说那哈希表呢？哈希表其实也不行，同时哈希表本身还有表空间的占用，数据量过大的情况下，内存用哈希表也是存不下的，同时哈希冲突厉害的情况下，还需要用红黑树来代替链表作哈希桶，高度依旧是很高的，所以内查找的这些数据结构都不适用于磁盘上数据的查找，此时就有大佬想到了新的数据结构，B树。

2.
在上面分析的过程中，可以看到内查找的数据结构不适用主要问题就是高度太高，那么能否设计一个类似树的查找结构，但这棵树很低呢？而我们的B树就是专门用来外查找的数据结构，他的高度很低，主要是因为他的分支足够的大，之前内查找的那些数据结构才二叉，而在一些数据库中，他们所使用的B树分支数量通常都会设置的很大，有的可以达到1024，也就是说，一个结点的孩子，最多可以到1024个，那对于10亿个数据，这颗B树的高度差不多就是3，也就是说，最多只需要对磁盘进行3次IO就可以找到特定的某个结点内存储的数据了，这样的效率就非常的高了。
（插个题外话：有人可能会觉得3和30次差别不是很大啊，那可能你是站在内存的角度来看待这两个数字，对于内存来说，3和30次肯定没有什么差别，无非就是10ns和300ns的区别而已，连1μs还没有达到呢，但对于外存来说差别就巨大了，外存的速度都是毫秒级别的了，你再扩大30倍，又提升一个数量级，所以这个倍数大不大，取决于基数大不大，3和30虽然差10倍，感觉上不大是因为你没有一个确定的基数来衡量这个差距，如果是1块钱，那可能什么都干不了，如果是10块钱，那就能吃一碗面，你赶紧好像也无所谓，但如果是100w，可能在二线城市你买不下来一套房，但如果是1000w，你在西安，杭州这样的城市都能买三套房了，你这回觉得差别还小吗？所以一定不要站在内存的角度来看3和30的差别，要站在磁盘的角度来看。）
所以B树本质上是一棵多叉平衡搜索树，通过放大分支数量来达到降低高度的目的。实际的B树结点中存储的关键字也不再是单个的关键字了，而是和分支数量有关，一个结点中最大可以存储到分支数量个关键字，拿分支数量为1024来说，一个B树结点就能够存储1024个关键字，有人可能会说，在文件读取时，读到一个B树结点后，再连续一直读1024个关键字，这样时间消耗不也是很大吗？其实这就与磁盘的物理结构有关了，磁盘IO的时间消耗主要在磁头的定位上，只要确定好数据所在的页之后，向后连续存取数据就完全电子化了，速度会非常的快。

3.
下面关于B树结点的定义这部分内容，不再放出算法导论上抽象的描述，而是用我本人的理解来阐述，让枯燥的定义变得更像白话一些。
B树的分支数量用M来表示，每个分支结点包括一个存储key关键字的数组，和一个存储结点指针的child数组，要求关键字的数量必须保证在M/2-1到M-1之间，同时M/2要向上取整，拿M为3来举例，拿一个结点的关键字数量范围就是1到2之间，因为3/2向上取整之后是2，再减去1，下限就是1。而孩子的数量必须始终保证比关键字的数量多1个，用公式来表示的话，孩子数量范围就是M/2到M之间，M/2依旧向上取整。B树结点剩下的定义就和二叉搜索树一样了，在任意一个B树结点内部，关键字数组中任意一个key的左孩子下存储的所有关键字都比key小，右孩子下存储的所有关键字都比key大。同时所有的叶子结点都得在同一层，这一点是为了让B树自始至终都是平衡的一棵树，这样对于查找任何的关键字，最坏情况下都是高度次，而不会说由于某一个分支过长而导致搜索效率继续恶化，当然这条规则是结点插入的过程来保证的，不能算是B树结点的定义，硬要算的话，那就是B树叶子结点的定义。
以上就是关于B树结点的定义，这里在总结一下：(1) 孩子的数量永远要比关键字的数量多一个，这条规则适用于所有的非叶子结点，不适用于叶子结点，因为叶子结点根本就没有孩子，他的孩子是nullptr (2) B树结点中关键字或孩子的数量是一个范围值，有上限和下限。(3) 所有叶子结点都在同一层

2.B树的插入

1.
通过上述的结点定义可以发现，一个非叶子结点关键字数量最多就是M-1，孩子数量最多是M，但这是理论层面的，真正实现时，会为每个结点的孩子和关键字各多开一个空间，变成关键字数量最多是M，孩子数量最多是M+1，这么做的主要原因是为了让多出来的target关键字先插入到结点里面，然后再去分裂。如果不这么做的话，实现起来就比较恶心了，拿M为4来举例，你开3个关键字的空间，因为最多可以存储M-1个关键字嘛，那现在要往结点里面插入一个target值，那你就得判断这个target插入到哪个下标位置上，然后还得用个tmp来暂存一下被挤出来的值，然后再开一个兄弟节点来存储这个被挤出来的tmp存储的值，这样实现起来有一点麻烦，最好的方式就是开4个关键字的空间，先把target放进来，然后此时不满足B树结点的条件了，那我们再开始进行结点的分裂，这样就不需要搞什么tmp来存储被挤出来的值，会方便很多。

2.
拿一个数组53, 139, 75, 49, 145, 36, 50, 47, 101来模拟B树插入过程中，结点的变化，我们假设B树的M为3，那么每个结点的关键字数组空间就是3，孩子数组空间就是4，当存储的key数量达到3时，该节点就不符合规则了，此时就需要分裂，因为按照结点定义规定，M为3的结点最多只能存储2个关键字。
下面是结点插入过程的图，后面写代码时，为了防止漏掉细节，就会对应着下面这个图进行实现，这里多提一嘴，写任何关于算法，数据结构实现的代码，最好都要配套着图，否则很容易漏掉细节，从而产生bug。牢记：算法千万条，画图第一条，画图不规范，求职两行泪。

3.
算法流程为：
先在B树中进行搜索，如果找到了k，则返回k所在的结点与k的下标位置，如果没有找到k，则返回k如果要插入的话，应该插入的结点位置，以及插入到_keys数组中的哪个下标位置。
find搜索结束后，判断k值是否存在，如果存在则返回false，算法结束。
如果不存在则根据插入排序思想将k插入到结点当中，插入结束后，则判断结点是否满了，如果满，则需要进行分裂操作，将一半的值拷贝给兄弟结点，再将中位数提取到父节点，然后再向上迭代，判断父节点是否满了，如果满，则也需要进行分裂，所以判断满进行分裂这部分代码是一个while循环，不断的将pos向上迭代，直到结点不满，符合B树结点定义为止，while结束后返回true即可。
整体算法的实现难度在于细节的把握，比如拷贝key和child时下标的控制，以及父节点如果为空，则还需要特殊处理。
说说我在实现时，出现的问题吧：（1）比如在Find函数中，对于跳出for循环有两种情况，一种是cur向左跳之后的break，一种是i++越界后的跳出循环，这种情况cur要往右边迭代，当时把第二种跳出循环的情况给漏掉了。（2）结点分裂后提取中位数到父节点时，要挪动父节点中存储的key和child，那就需要遍历父节点的keys数组，从后向前遍历的过程中要保证下标i得大于0，while循环要多加个i>0的条件，我当时忽略了这一点，这也就导致了越界访问，因为i已经减到-1了。

3.B树的中序遍历

1.
B树的中序遍历结果刚好是有序的，所以要想验证写的B树对不对，只要走一遍中序遍历，看看结果是否有序即可判断出代码的正确性。
如何实现B树的中序遍历呢？遍历根节点的keys数组，先去递归访问左孩子结点，访问完回溯上来之后再打印0下标的关键字，然后再递归访问下一个关键字的左孩子结点，回溯上来之后再打印下一个关键字，最后一个关键字的左孩子回溯上来之后，输出完最后一个关键字，你会发现最后剩的这个关键字的右孩子还没有被访问呢，那就再递归访问一下他的右孩子即可。

下面代码写了两种_dfs版本，两种均可，一种是root不会递归到nullptr结点，一种是root会递归到nullptr结点

二、B+树和B*树

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+树。

三、B树与B+树的应用

1.
B树和B+树其实通常都用来做索引，做数据库在查找数据时的索引，在MYSQL中，索引属于存储引擎的概念，不同的存储引擎所使用的索引结构也不同，下面我们只谈论最常见的两种存储引擎，分别是InnoDB和MyISAM。

2.
MyISAM的索引结构是一颗B+Tree，data域保存数据记录的地址。因此，MyISAM中索引检索的算法为首先按照B+Tree搜索算法搜索索引，如果指定的Key存在，则取出其data域的值，然后以data域的值为地址，读取相应数据记录。这种索引文件和数据文件分离的索引结构称为非聚簇索引。

3.
InnoDB的索引结构也采用的是B+Tree，InnoDB的索引文件本身就是数据文件，叶子节点的data不在存储数据文件的地址，而是改为直接存储数据，而这样的索引结构也称为聚簇索引，正好与MyISAM相对。除此之外，InnoDB的辅助索引data域存储的是相应记录主键的值而不是地址,所有辅助索引都引用主键作为data域。
所以，聚簇索引这种实现方式使得按主键的搜索十分高效，但是辅助索引搜索需要检索两遍索引：首先检索辅助索引获得主键，然后用主键到主索引中检索获得记录。