B+树实现
B+ 树，具有矮胖的特点，这使得可以仅需要少数几次节点查找就能锁定到数据，因此，常用于磁盘索引
对于HDD来说，当数据不连续时，需要进行多次寻址，这是HDD读取的主要瓶颈，因此在读取数据时应该尽量少的进行寻址，而B+矮胖的特点，仅需要少数寻找就能找到数据的位置，一次读取数据和相邻的数据，根据局部性原理，这一次读往往就获得了后续需要的数据
另一方面，也是由于B+树的这个特性，每次写入都会写入一个完整的叶子节点，这个特性在用户进行小数据写入时会造成严重的写放大。在这种场景，应该使用另一种数据结构 LSM Tree
对于SSD来说，B+树Update In Place的特点会导致SSD磨损严重，减少这个影响需要依赖Flash芯片固件的磨损均衡等算法。但是，对于读多写少的场景B+树比LSM Tree有更好的表现，因为LSM Tree可能会读多层导致读放大
和 B- 树的比较
B-树和B+树类似，都具有矮胖的特点，不同点是B-树的索引节点同时还存放着数据，这个特性在HDD上使用的结果是，读性能会出现波动，同时在进行范围查找时需要进行中序遍历，导致频繁的寻址操作
但在内存中使用时，B-树比B+树（以及其他平衡树， 如：AVL）更具有优势，一方面是，数据在索引节点，相对B+树可以减少节点跳跃，另一方面是，节点有多个数据，相比于其他平衡树，能更好的利用局部性原理
实现
首先需要给B+树下定义，假设B+树的阶M = 3，那么
- 对于叶子节点，最多保持
M - 1个键
- 对于索引节点，最多保持
M - 1个键，和M个叶子节点的指针
- 对于根节点
- 当仅为1层时，根节点即叶子节点
- 当大于1层时，根节点至少包含两个索引节点，至多包含
M个索引节点
- 当仅为1层时，根节点即叶子节点
- 节点间使用指针连接起来，按照键值升序排列
- 索引节点至少包含两个子节点
- 在索引节点中第一个子节点的最大值严格小于第一个键值，
left < parent ≤ right，以此类推
- 索引操作的时间复杂度均为
O(log(n))其中对数的底为B+树的阶
从上面的定义可以发现，B+树中有两中类型的节点：索引节点、叶子节点，同时根节点会在两种节点之间转换
查找
这是B+树中最关键的操作，这里的查找实现为binary search以达到规定的时间复杂度，查找操作应用于插入和删除，因此实现为lower bound
- 如果找到，则返回给定键在节点中的下标
- 如果没有找到，那么下标表示键的插入位置
索引节点的查找稍有不同，索引节点是根据键来查找子节点的指针，由于B+树的特性（第2点），如果找到的下标为pos，那么子节点的指针的下标应该是 pos + 1，否则pos即为子节点指针的下标
根据B+树的性质，通常在实现时索引节点和叶子节点会共用一部分数据，比如：键、左右兄弟的指针、节点类型等
我们这里定义两种节点的结构如下
struct node {
int type; // node type
int count; // key count for leaf node, child count for index node
node *prev, *next; // siblings
node *parent; // root node has null parent
};
struct leaf_node {
node info;
int key[M];
int val[M];
};
struct index_node {
node info;
int key[M];
node *child[M+1];
};
查找首先从根节点开始，步骤如下
我们假设查找返回一个元组(found, pos) 其中found表示是否找到，pos表示插入位置，那么对于索引节点来说，如果found为true那么插入的节点位于 cur->child[pos+1]
插入
插入的第一步也是查找，找到将要进行插入的叶子节点，然后进行插入。为了维护B+树的性质，插入过程中会出现将现有节点分裂成两个，每个节点各持有一半的数据，比如，旧节点持有 ⌊M/2⌋，新节点持有⌈M/2⌉个节点，以下是插入时需要考虑的各种情况
- 如果当前叶子节点的键数量小于一半，直接插入即可
- 如果键数量超过了一半，那么需要进行分裂，
⌊M/2⌋处的键需要插入到父节点 - 在
1.或2.中，如果破坏了left < parent ≤ right的性质，需要向上递归修改父节点的值，直到根节点
- 在
2.中，如果父节点插入新的键后数量超过了一半，那么父节点也进行分裂，直到根节点，如果根节点进行了分裂，那么需要设置新的根节点，这意味着树的高度增加了一
为了简化实现，这里可以规定，分裂的节点总是旧节点的右节点，对于叶子节点只需要简单的拷贝一半的数据到右节点，然后判断3.和4.即可，如下图
对于索引节点也是类似，但需要注意，在结构定义时key[M]、child[M+1]这里键和子节点指针均增加了1，这里使用额外的空间使得分裂操作之前可以先将新的key和child插入到原节点中，然后再分成两个节点。
这简化了分裂的操作，如果不这样的话，需要分别处理key和child的下标，他们相差了一，这样做的伪代码看起来是：
new_node[0].key = old_node[count-2].key;
new_node[0].child = old_node[count-1].child;
insert(new_node, key, child);
在分裂后，需要递归的地向上层进行插入操作，这里的终止条件是： 1. 父节点键数量小于一半 2. 两个子节点都没有父节点，这时需要新建一个节点成为两个子节点的父节点 伪代码如下：
fixup(lhs, rhs, key) {
if (!lhs->parent && !rhs->parent) {
new parent;
parent->count = 2;
parent->key[0] = key;
parent->child[0] = lhs;
parent->child[1] = rhs;
lhs->parent = parent;
rhs->parent = parent;
root = parent;
} else {
rhs->parent = lhs->parent;
insert_to_index_node(rhs->parent, rhs, key);
}
}
删除
删除的第一步同样是查找，找到键所在的叶子节点，再继续在叶子节点上查找要删除的键，如果找到则进行删除，这个操作可能会破坏B+树的性质，因此需要注意以下几点
- 如果叶子节点键的数量超过了一半（
⌈M/2⌉），那么直接删除即可 - 在
1.中，如果删除的键是叶子节点的第一个，那么需要更新对应的父节点的键，以保证顺序left < parent ≤ right
- 如果叶子节点键的数量小于一半（
⌈M/2⌉），那么需要向左右兄弟节点的某个借一个节点
- 如果当前节点是最左边的，那么向右节点借
- 如果当前节点是最右边的，那么向左节点借
- 如果当前节点有左右兄弟，那么从其中键多的借
- 如果当前节点是最左边的，那么向右节点借
- 如果在
3.中无法满足借的条件（即被借节点借出后键的数量小于一半），那么将当前节点和被借的节点合并，此外，还需要关注2.的情况
- 在
4.中合并后，需要在父节点中删除已合并的节点，递归向上直到根节点，如果根节点被删除，那么更新根节点为子节点
对于叶子节点的删除，可以找到要删除键在叶子节点中的下标，但对于索引节点来说，要删除的键可能根本不存在与索引节点，那么如何找到索引节点中要删除的下标呢？
一个直观的想法是，在节点的结构中维护一个指针，用于表示当前节点在父节点中的下标，这么做的代价是，任何增删操作都需要更新这个指针
另一个想法是，要找到键所在的叶子节点，那么必然有一条路径从根节点到要删除节点在叶子节点中的下标，要么记录这个路径，这样做的代价是，需要维护一个额外的结构；要么及时查找，这样做的代价是性能不如前二者，但实现简单，伪代码如下
int index_in_parent(parent, key) {
auto [found, pos] = bsearch(parent->key, key);
if (!found)
pos -= 1;
return pos;
}
这里的重点是pos -= 1，前面提到binary search在没找到时，对于索引节点，实际上是返回child的插入下标，那么对应key的索引是pos - 1
举例来说，在parent中如果key的下标是0，那么对应的child的下标则是pos + 1即1，而索引为0的child对应的key则是pos - 1即-1，表示是父节点左兄弟的最后一个key，这也就意味着最左边节点只能从右兄弟借，或者和右兄弟合并，那么右兄弟在父节点中的下标就是pos + 1即1。这样，在父节点中删除下标为0处的键就转换为删除下标为1的键
最后
B+树相比于B-树和常见的平衡二叉树来说更适合磁盘存储，通常作为数据库和文件系统中的索引，不过在磁盘结构中，B+树的节点通常按页分配，比如16K大小，页的大小和磁盘中B+树结构的大小决定了能存放键的数量
如果你要自己实现B+树，可以参考这个网站 https://www.cs.usfca.edu/~galles/visualization/BPlusTree.html 需要注意的是，这个实现允许插入相同的key，也可以参考这里的实现 bptree