B树

1.简介

B+树是一种自平衡树，其插入和删除的算法保证了数据的有序性。

B+树是高效的，其查找、写入、删除的复杂度为$O(logn)$，其数据有序性在一定程度上保证了磁盘的顺序I/O，因此适合用于磁盘中组织数据。

B+树由两部分组成：

• Leaf Node：在B+树中唯一携带数据，且位于最底层的节点。其通过silbling pointer与相邻的Leaf Node组成双向链表，保证顺序扫描的高效性。
• Inner Node：除了Leaf Node的都是Inner Node，类似操作系统的多级页表，其唯一作用就是索引，不携带数据。

若一个B+树是M路的，Inner Node拥有k个key，它需要满足$M/2-1<=k<=M-1$,且拥有$k+1$个非空子节点。

无论是Leaf Node还是Inner Node，其包含的节点都根据key进行了排序。其中Inner Node中一个键值对的含义是，值指向下一层、第一个拥有大于等于自身键的键的page。

至于第k+1个键值对的键是空的，位于键值对的第一个位置，其值指向第二个键值对的左边的page。

当插入或者删除导致了Inner Node不满足上述条件，则会触发分裂或者合并。

2.CURD

查找：

查找以典型的方式进行，类似于多叉查找树。起始于根节点，自顶向下遍历树，直到找到叶节点。

由于节点内部的键值对是有序的，常通过二分查找来键值对。

插入：

1. 首先，查找要插入其中的叶节点的位置。接着把值插入这个节点中。
2. 如果叶节点没有超出数量限制，则结束。
3. 如果叶节点超出了数量限制，则该叶节点分裂出一个新的节点。其中原来的节点保留$\lceil n/2 \rceil$个节点，剩下的存放于新节点中。由于新的节点需要被父节点指向，因此父节点要插入一个新的键值对，其中键为新节点的第一个键称之为middle key，值为指向新节点的值。如果父节点因为插入也超出了数量限制，则也要进行分裂。

Leaf Node分裂时为其父节点插入middle key，是不用删除这个键值对的，就好像将该middle key "复制"给了父节点一样；但Inner Node分裂时，自身是要删除这个middle key的，就好像将该middle key "交付"给了父节点一样。

删除

1. 首先，查找要删除的值。接着从包含它的节点中删除这个值。
2. 如果叶节点没有少于数量限制，则结束。
3. 否则可以进行以下操作：
4. 可以从其相邻节点得到一个或多个键值对而不会使其相邻节点不满足数量限制。此时，在更改父节点和两个相邻节点的键值对后结束。
5. 否则，与其兄弟节点合并，并将父节点的middle key删除。若父节点不满足数量限制，则向上递归处理。

3.总结

B+树是搜索树的一种，与常见的搜索树来看：

• 平衡二叉树：只有二路，因此树的深度更大，也不支持顺序扫描。同时磁盘是基于page读取的，每次读取一个平衡二叉树的节点时，可能只有里面的很小一部分数据是有用的。
• B树：B树的每个节点可以存储多个关键字，将节点大小设置为page的大小就可以充分利用磁盘的预读功能。表现出来的就是B树拥有多路，树的深度更低。但是B树的顺序扫描是基于中序遍历的，这意味着需要在树上做很多次跳转，算法的实现也更麻烦。

B+树集成了它们的优点，也解决了几个痛点：

• 磁盘预读，树的深度：即一个节点中存储多个信息，表现出的是多路。将节点大小设置为page的大小就可以充分利用磁盘的预读功能，同时树的深度更低。

• 顺序扫描：由于数据都在叶子节点中，直接找到顺序扫描的起点，然后顺序走到终点即可，算法实现更简单。

• 叶子节点的深度相同：意味着更加平稳的操作，可以想象成削峰填谷，但在发生磁盘I/O时峰值的损耗会被放的更大。

另外B树也好B+树也好，根或者上面几层因为被反复query，所以这几块基本都在内存中，不会出现读磁盘IO，一般已启动的时候，就会主动换入内存。

4.设计选择

4.1.Node size

对于速度较慢的磁盘来说，大的节点可以保证更多的顺序读写，从而提高效率。

• HDD：～1mb
• SSD：～10kb
• 内存：～512b

大的节点缺点在于B+树发生merge和redistribute的耗时更长。

4.2.Merge Thershold

由于B+树的一大损耗集中在merge和redistribute，一种常见的做法是放宽规则，从而减少merge和redistribute的次数。

这种结果带来的是B+树的略微不平衡，因此需要隔一段时间进行B+树的重构。

4.3.Bulk Insert

基于已有数据的快速构建或重构B+树，即利用Leaf Node自底向上构建Inner Node。