图解：什么是B+树？(插入删除篇）
大部分教材和分享中都会将 B+树的插入和删除操作一笔带过，但这并不意味着你真的懂了或者说是不重要，因为我觉得有些朋友可能都没有看过 B-树，一句 "B+树的插入和删除操作与 B-树的插入和删除操作类似" 又怎么说的过去，相信你看完这篇 B+树的插入和删除操作一定会有收获，一起加油呀~
B+树的插入操作
在B+树中插入关键字时，需要注意以下几点：
插入的操作全部都在叶子结点上进行，且不能破坏关键字自小而大的顺序；
由于 B+树中各结点中存储的关键字的个数有明确的范围，做插入操作可能会出现结点中关键字个数超过阶数的情况，此时需要将该结点进行 “分裂”；
我们依旧以之前介绍查找操作时使用的图对插入操作进行说明，需要注意的是，B+树的阶数 M = 3 ，且 ⌈M/2⌉ = 2（取上限） 、⌊M/2⌋ = 1（取下限） ：
B+树中做插入关键字的操作，有以下 3 种情况：
1、 若被插入关键字所在的结点，其含有关键字数目小于阶数 M，则直接插入；
比如插入关键字 12 ，插入关键字所在的结点的 [10，15] 包含两个关键字，小于 M ，则直接插入关键字 12 。
2、 若被插入关键字所在的结点，其含有关键字数目等于阶数 M，则需要将该结点分裂为两个结点，一个结点包含 ⌊M/2⌋ ，另一个结点包含 ⌈M/2⌉ 。同时，将⌈M/2⌉的关键字上移至其双亲结点。假设其双亲结点中包含的关键字个数小于 M，则插入操作完成。
插入关键字 95 ，插入关键字所在结点 [85、91、97] 包含 3 个关键字，等于阶数 M ，则将 [85、91、97] 分裂为两个结点 [85、91] 和结点 [97] , 关键字 95 插入到结点 [95、97] 中，并将关键字 91 上移至其双亲结点中，发现其双亲结点 [72、97] 中包含的关键字的个数 2 小于阶数 M ，插入操作完成。
3、在第 2 情况中，如果上移操作导致其双亲结点中关键字个数大于 M，则应继续分裂其双亲结点。
插入关键字 40 ，按照第 2 种情况将结点分裂，并将关键字 37 上移到父结点，发现父结点 [15、37、44、59] 包含的关键字的个数大于 M ，所以将结点 [15、37、44、59] 分裂为两个结点 [15、37] 和结点 [44、59] ，并将关键字 37 上移到父结点中 [37、59、97] . 父结点包含关键字个数没有超过 M ，插入结束。
4、若插入的关键字比当前结点中的最大值还大，破坏了B+树中从根结点到当前结点的所有索引值，此时需要及时修正后，再做其他操作。
插入关键字 100，由于其值比最大值 97 还大，插入之后，从根结点到该结点经过的所有结点中的所有值都要由 97 改为 100。改完之后再做分裂操作。
B+树的删除操作
“对于 B+的删除操作而言，与 B-树类似”，我想你笑了，那我们接着看，哈哈！
在 B+树中删除关键字时，有以下几种情况：
1、 找到存储有该关键字所在的结点时，由于该结点中关键字个数大于⌈M/2⌉，做删除操作不会破坏 B+树，则可以直接删除。
删除关键字 91，包含关键字 91 的结点 [85、91、97] 中关键字的个数 3 大于 ⌈M/2⌉ = 2 ，做删除操作不会破坏 B+树的特性，直接删除。
2、 当删除某结点中最大或者最小的关键字，就会涉及到更改其双亲结点一直到根结点中所有索引值的更改。
以删除整颗 B+树中最大的关键字 97 为例，查找并删除关键字 97 ， 然后向上回溯，将所有关键字 97 替换为次最大的关键字 91 :
3、 当删除该关键字，导致当前结点中关键字个数小于 ⌈M/2⌉，若其兄弟结点中含有多余的关键字，可以从兄弟结点中借关键字完成删除操作。
当删除某个关键字之后，结点中关键字个数小于 ⌈M/2⌉ ，则不符合 B+树的特性，则需要按照 3 he 4 两种情况分别处理。以删除关键字 51 为例，由于其兄弟结点 [21、37、44] 中含有 3 个关键字，所以可以选择借一个关键字 44，同时将双亲结点中的索引值 44 修改 37 ，删除过程如下图所示：
4、 第 3 种情况中，如果其兄弟结点没有多余的关键字，则需要同其兄弟结点进行合并。
为了说明这种情况，我们在第 3 种情况最终得到的 B+树之上进行删除操作。第 3 种情况删除关键字 51 之后得到如下所示 B+树：
我们以删除上面这个 B+树中的关键字 59 说明第 4 种情况，首先查找到关键 59 所在结点 [44、59] ，发现该结点的兄弟结点 [21、37] 包含的关键字的个数 2 等于 ⌈M/2⌉， 所以删除关键字 59 ，并将结点 [21、37] 和 [44] 进行合并 [21、37、44] ，然后向上回溯，将所有关键字 59 替换为次最大的关键字 44 :
5、 当进行合并时，可能会产生因合并使其双亲结点破坏 B+树的结构，需要依照以上规律处理其双亲结点。
删除关键字 63，当删除关键字后，该结点中只剩关键字 72，且其兄弟结点 [85、91] 中只有 2 个关键字，所以将 [72] 和 [85、91] 进行合并，向上回溯，删除结点 [72、91] 当中的关键字 72 ，此时结点中只有关键 91 ，不满足 B+树中结点关键字个数要求，但其兄弟结点 [15、44、59] 中包含的 3 个关键字，所以从其兄弟结点当中借一个关键字 59 , 再对其兄弟结点的父结点中的关键字进行调整，将关键字 59 替换为 44 .
总之，在 B+树中做删除关键字的操作，采取如下的步骤：
删除该关键字，如果不破坏 B+树本身的性质，直接完成删除操作（情况 1）；
如果删除操作导致其该结点中最大（或最小）值改变，则应相应改动其父结点中的索引值（情况 2）；
在删除关键字后，如果导致其结点中关键字个数不足，有两种方法：一种是向兄弟结点去借，另外一种是同兄弟结点合并（情况 3、4 和 5）。（注意这两种方式有时需要更改其父结点中的索引值。）
B+树复杂度分析
B+树 是 B-树的一个升级版本，在存储结构上的变化，由于磁盘页的大小限制，只能读取少量的B-树结点到内存中（因为B-树结点就带有数据，占用更多空间，所以说是 少量）；而B+树就不一样了。因为非叶子结点不带数据，能够一次性读取更多结点进去处理，所以对于同样的数据量， B+树更加 "矮胖"， 性能更好。但是两者在查找、插入和删除等操作的时间复杂度的量级是一致的，均为 。
这个量级是如何得来的呢？我们一起来看看 1970 年计算机的先驱们是如何计算的。
首先假定 的整数（事实上就是树高）， 是一个自然数（也就是B-树当中提到的最小度数，这里不懂的可以回头看看之前的文章 图解：什么是B树（心中有 B树，做人要谦虚）？ ).
一颗最小度为 ，高度为 的 B-树 ，或为空树，或者满足下面三个特性：
从根结点到任意一个叶子结点有着相同的长度 , 也称为树的高度。
除根结点和叶子节点外，每一个内部结点至少有 个孩子结点。根结点要么为叶子，要么至少包含两个孩子。
每个结点至多有 个孩子结点。
设 和 分别表示 B-树中可以最少包含与最多包含的结点数目，则：
其中 ，当 依然成立， 至少包含一个结点，即根结点，之后每一层所包含的结点数目则为 ，其中 表示每一个内部结点最少拥有的孩子结点数。类似的：
则对于一颗 B-树所能包含的结点数目的上下限为：
则对于一颗 B-树所能包含的关键字的最大数目和最小数目分别为 和 :
则可以得到 B-树高度的一个上下限：
这也就是我们所期待的对数级别的时间复杂度。对于上面的这个过程不清楚的可以跳过看下面。
对于一颗结束为 的B-树而言，每一个结点最多可以存储 个关键字，假设总共有 个关键字，树的高度为 ，且这颗树完全填满，则 ，继而得到 ，也就是树的高度为 ，可能有的人又会问，那一个结点中包含 个关键字，这 个关键字只有进行顺序遍历才能知道接着选择哪一个孩子结点，需要 的时间，你说的对也不对，对是因为一个结点内的关键字的遍历确实是需要 的时间复杂度，但是这个遍历是在内存当中进行的，时间一般可以忽略。我们通常更加关注的是磁盘 I/O 的次数，也就是 ，所以 B-树或者 B+树的时间复杂度就是 。
对于 B+树而言，树的高度一般不超过 4 层，就 MySQL 的 InnoDB 存储引擎而言，一个结点默认的存储空间为 16Kb ( 可以通过这个命令查看SHOW GLOBAL STATUS like 'Innodb_page_size'; )， MySQL 的 InnoDB 存储引擎的索引一般用 bigint 存储，占用 8 个 byte，一个索引又会关联一个指向孩子结点的指针，这个指针占用 6 个 byte，也就是说结点中的一个关键字大概要用 14 byte 的空间，而一个结点的默认大小为 16kb ，那么一个结点可以存储关键的个数最多为 , 就相当于阶数 ，那么对于一颗高度为 3 的 B+树而言保守估计可以存储 个关键字，也就是两千多万条记录，其中的 16 为假定每一个叶子结点包含的关键字的个数（由于包含 Data 指针，所以叶子结点可以容纳的关键字的个数会少一些），就这样我想你也看到了 B+树的强大了。3层的 B+树就可以存储两千多万的数据，牛逼不？
哈哈，就到这里了，原创不易，觉得不错，记得给景禹点个 在看 奥！爱你们，祝你们学有所成~~
推荐阅读：
作者：景禹，一个追求极致的共享主义者，想带你一起拥有更美好的生活，化作你的一把伞。