B+ 树是一个多叉树排序树，其每个节点中可能包含多个 key。主要是用来对 OLTB 的数据库来进行索引。对于 insert, delete 操作需要调整树的结构保证这棵树的平衡性，使其所有的叶子节点的深度都是一样的。与此同时需要让每个节点有一定数量的 key 不能过多，也不能过少。 (todo 补充B+树的意义)。
1 B+ 树的性质
- insert delete 操作需要保证这棵树的平衡性。
- 除根节点外的每个节点至少保证 50% 空间被 key 占用。
- 对于查询操作，只需要访问树的高度个节点。
- 假设每个节点有 m 个 key， 对于非根节点
, 其中
是 B+ 树的参数，叫做树的 order 用来定义节点的容量。对于根节点
.
2 B+ 节点的 format
B+ 树有两种节点，中间节点和叶子节点，共同点是他们都包含了 key，不同点是，中间节点包含了指向子树的指针。**叶子节点没有指向子树的指针, 但是包含了 key 所对应的 record 或者是指向 record 的指针。并且叶子节点有指向其 相邻的叶子节点的指针(用来遍历 B+ 树)。
非叶子节点有 个 key 和
个指针
指向子节点。所有的 key 都是以什序排列
, 其中
指针指向的子树的所有的 key 都小于
,
不存在。其他指针
指向的子树的 key 的值大于等于
。下图就是一个
B+ 树的例子。
当然叶子节点也可以作为根节点，下图就是只插入三个 key 时 B+ tree 的样子。
注意:本文中的后续举例说明的 B+ 树的 d 默认为 2。
3 插入操作
B+ 树插入的 entry 一般包含了一个 key 与一个 val。
首先找到应该插入的叶子节点，并将 <key,val> 插入。
如果插入后的叶子节点的 ，需要将将节点分裂(split)为 d 与 d+1 两个节点，并且将右边节点的 lowKey（最小的key）插入到父亲节点。
split 需要分三种情况讨论:
1）被 split 的节点没有父亲节点，即根节点为叶子节点。需要创建一个 中间节点作为根节点，并且将 split 的 pivot 插入到这个新的根节点，其两个指针分别指向 split 出来的两个新的叶子节点。
如下图，是一个 d=2 的 B+ 树，继续插入一个<8:4> 的pair:
树将变为下面的样子:
- 如果有父亲节点且父亲节点没有满，被split 出来新的节点 pointer 和 split 的 pivot 插入父亲节点。如下图向上图中的 B+ 树中连续插入 <10,5>和 <12,6> 两个 entry将得到下图的结果。
3）如果父亲节点已经插满，父亲节点也需要分裂递归向上插入 split 出来的 node 与 pivot
如果向上图插入<17,4> 这个 entry 会导致节点分裂，并且 pivot 为 key = 15。此时其父节点中上插入 key=15, 以及 pointer 指向被分裂出来的 node 。而在父亲节点插入的新 <key,pointer> 会导致父亲节点进行分裂，并且同样在 key = 15 处分裂。此时由于父亲节点没有父亲节点了，创建一个新的 root 节点。如下图：
⚠️ 这里需要注意:
split 中间节点操作与 split 叶子节点有少许的不同，叶子节点会将 pivot 插入父亲节点，并且保留这个 pivot。而对于中间节点来说，这个pivot 在插入父亲节点后，在当前节点中会被移除掉。
4 删除操作
当删除某一个 key 后，可能会导致叶子节点 需要改变树的结构以满足 B+ 树的定义。这里涉及到两种可能的操作，使得 B+ 树满足定义。他们为: 重排(redistribute) 和 合并 (merge) 。
删除key的操作是通过递归实现。对从根节点到key所在的叶子节点递归调用删除操作。如果子树的删除操作不会导致点该节点中 key 的数量过小即 就直接返回。反之需要对该节点进行 redistribute 或者 merge。
首先尝试 redistribute 即分别向左右 sibling (同一个parent 下面的节点) 一个 key 让当前节点满足 B+树的要求。可以 lend 的 sibling 需满足 。如果找不到这样的 sibling 则说明要么没有 sibling 要么 sibling (
) 。则此时可以尝试 merge。
下面将删除操作分别在叶子节点和中间节点中运用进行讨论，即删除后节点的 。
4.1 叶子节点
4.1.1 redistribute
4.1.1.1 向左兄弟借一个key
如果当前节点不是其父亲节点的最左的儿子，并且其左边的兄弟的 key 的数量 ，向其左兄弟借一个 key(左兄弟的最大的key)， 更新当前节点的父亲节点指向当前节点所对应的key。例如对上图的B+树中删除 <20,4> 这个值，其所在的节点会向其左兄弟借 <17,4>这个 entry 并将父亲节点中的 key 从 20 改为 17。
4.1.1.2 向右兄弟借一个 key
如果当前节点不是其父亲节点的最右边的儿子，并且其右边的兄弟的 key 的数量 ，向其右兄弟借一个 key(左兄弟的最小的key)，更新父亲节点指向右兄弟的 pionter 所对应的 key。例如如果删除上图中的 <21,4> 这个 key，这个节点将会向右兄弟借 <22,4> 这个key 父亲节点中的 22 将更新为 25.结果如下图所示:
4.1.2 merge
4.1.2.1 merge 到左兄弟
如果当前节点有左兄弟，并且左兄弟的 key 的数量 ，将当前节点上的key copy 到左兄弟，删除当前节点，并且在父亲节点将当前节点的 pointer 以及 key 删掉。
例如将上图中 删除 21， 所在的节将 merge 其左兄弟，父亲节点的keys 将删除 18 以及 当前node 的 pointer，最后parent只剩下 23,25，如下图。
4.1.2.2 merge 右兄弟
如果不能merge到左兄弟(当前节点为 parent 最左边的儿子) merge 其右兄弟。 在父亲节点中将右兄弟的 pointer 以及key删除掉。如果将 4.1.1.3 中的第一张图的 <16,4> 删除，将会导致其节点 merge 右边的兄弟，其父亲节点将变为 [23,25].
4.2 中间节点
上面的部分只讨论了叶子节点出现 redistribute 和 merge的情况。在某些情况下这些操作将会导致中间节点的 key的数量不满足 B+ 树的要求。此时需要将中间节点进行 redistribute 或者merge。例如上图中如果删除 25 将会导致叶子节点的merge，其父亲节点将会只有一个 key。这将不能满足B+树的限制。
4.2.1 redistribute
4.2.1.1 向左兄弟借一个 key
由于中间节点的每一个 entry 是 <key,pointer> 的组合，如果直接将左兄弟的最大的key以及它所代表pointer copy 过来会导致当前节点少了一个 key， 此时需要将父亲节点所对应的 key copy 到中间。并且更新父亲节点中，指向当前节点的 pointer 所对应的 key为借过来的 key。例如，将上图中的 17 删除掉，将会导致 [20,22]这个节点的变为 [22], 需要向左边的兄弟借一个 10 的key过来，并且将父亲节点的 15 copy 下来，最终变为 [10,15,22]，并更新父亲节点的 key。如下图所示:
4.2.1.2 向右边兄弟借一个 key
同理，需要将右兄弟的在父亲节点中pointer 说对应的 key copy 下来，并且更新父亲节点的 key。稍微有点区别的是，右边兄弟的第一个儿子的指针是不包含 key 的，所以当前节点只需要将指针直接拿过来，并删除掉 right silbing 最小的那个key。
如图，如果将图中的 10 删除，会导致 [5，10] 这个节点变为 [5] 并向右边的兄弟借一个pointer，并且父亲节点中key被更为 17。
4.2.2 merge
merge 的操作和 redistribute 的操作类似，redistribute 是只borrow 一个 key， 而merge 是将所有的 key 都 borrow 过来。稍有一点区别就是 borrow 是 update 父亲节点中的 key, 而 merge 是直接删除，可以看作是 split 的逆过程。
4.2.2.1 merge to left
如上图如果删除 18 [24,30] 这个节点将变为 [30], 会把当前节点 merge 到左边的 [6,12] 这个节点, 最后变成 [6,12,18,30] 这个节点，如下图所示。
4.2.2.1 merge right
如果删除 15 会将右边的节点 merge 过来 当前节点变为[6,18,24,30]，如下图所示。
4.2.2.2 root 变为 空
如何递归删除到根节点时()，并且两个子节点发生 merge，这样会导致根节点的key 的数量为零，此时就需要删除根节点。
例如删除下图中的 9 这个key 会让两个子节点 merge。
删除后的B+树如下图:
