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