演示地址：
https://dichchankinh.com/~galles/visualization/BPlusTree.html

What is a B+-tree?

如果值是排序的，那么所有的查询都可以很快被执行，但这种想法不切实际
这需要对每个插入、删除行，重写整个表
这使得我们想象用树结构来存储，比如平衡二叉搜索树，如红黑树这样的，但是他们对磁盘场景不合适
因为磁盘都是一次读取一个数据块，比如 512字节、或者4K这样的，二叉搜索树的节点因子太小了，因此需要寻找各方核实的磁盘块的数据结构

因此有了B+-树，其中每个节点最多存储d个对子节点的引用，最多存储d−1个键
每个引用被当做两个节点key的 中间，它指向了值在两个key之间的子树
下面是一个很小的树，用4作为d的值

从动画来看，如果是顺插入，如：1、2、3、4、5。。。这样的
则每次分裂都会出现在最右边的叶子节点上 这里实际上可以作为一个优化点

Insertion algorithm

下降到合适的叶子节点上

  • 如果节点有空间，则插入 key/reference 对
  • 如果节点满了
    • 则分裂成两个节点，并将key均匀的分布在两个节点上
    • 如果这个节点是叶节点，从两个节点中的第二个节点中获取最小值的拷贝，重复这个插入算法，将拷贝的值插入到父节点中
    • 如果这个节点是非叶节点，在分裂过程中排除中间值，然后重复这个插入算法，将排除的值插入到父节点

插入过程是递归的，可能会一直递归到 root，叶子节点分裂，然后递归往上，中间节点也不断分裂
最后到 root，也分裂，此时树高度 + 1

Initial:

Insert 20:

Insert 13:

Insert 15:

Insert 10:

Insert 11:

Insert 12:

Deletion algorithm

下降key所在的叶结点

  • 从节点上删除指定的key和关联的引用
  • 如果节点有足够空间使得kye和引用满足不变量，则停止
  • 如果当前节点key太少不满足不变量，但是同一层级的前后兄弟节点拥有更多节点，则重新分布这些节点的key，并修复这些节点的父节点，也就是修复分割点指针，这里只需要改变父节点的key即可，不需要插入/删除
  • 如果节点不满足不变量，前后的兄弟节点刚刚好满足最小的不变量，则将当前节点跟兄弟节点合并
  • 同上继续，如果当前是中间节点，需要将父节点的split key也合并进来
  • 继续，无论何种情况，都需要重复删除算法，从父节点上移除之前分割合并节点的split-key
  • 除非父节点是root，并且删除的是root的最后一个key，此时合并的节点会变成新的root，之后整个树会比之前矮了一层

删除过程可能是递归的，一直到 root，叶子节点跟兄弟节点合并，父节点的split key删除，此时父节点可能就变成空了
于是中间节点再跟其兄弟节点合并，从其父节点上删除split-key，这个过程也是递归的，直到 root，而root最后一个split-key也会被删除
于是整个树的高度 - 1

Initial:

Delete 13:

Delete 15:

Delete 1:

Reference