Content #
B+Tree 是对读操作优化的存储结构，能够支持高效的范围扫描，叶节点之间保留链接并且按主键有序排列，扫描时避免了耗时的遍历树操作。
下面这张图中展示了一棵高度为 2 的 B+Tree，数据存储在 5 个页表中，每页可存放 4 条记录。略去了叶子节点指向数据的指针以及叶子节点之间的顺序指针。
B+Tree 由内节点（InterNode）和叶节点（LeafNode）两类节点构成，前者仅包含索引信息，后者则携带了指向数据的指针。当插入一个索引值为 70 的记录，由于对应页表的记录已满，需要对 B+Tree 重新排列，变更其父节点所在页表的记录，并调整相邻页表的记录。完成重新分布后的效果如下：
在这个写入过程中存在两个问题：
- 写放大
本来我们仅需要一条写入记录（黄色标注），实际上更新了 3 个页表中的 7 条索引记录，额外的 6 条记录（绿色标注）是为了维护 B+Tree 结构产生的写放大。
为了度量写放大的程度，相关研究中引入了写放大系数（Write Amplification Factor，WAF）这个指标，就是指实际写入磁盘的数据量和应用程序要求写入数据量之比。对于空间放大有类似的度量单位，也就是空间放大系数（Space Amplification Factor, SAF）。
我们这个例子中的 WAF 是 7。
- 存储不连续
虽然新增叶节点会加入到原有叶节点构成的有序链表中，整体在逻辑上是连续的，但是在磁盘存储上，新增页表申请的存储空间与原有页表很可能是不相邻的。这样，在后续包含新增叶节点的查询中，将会出现多段连续读取，磁盘寻址的时间将会增加。
也就是说，虽然 B+Tree 结构是为读取做了优化，但如果进行大量随机写还是会造成存储的碎片化，从而导致写放大和读放大。
填充因子（Factor Fill）是一种常见的优化方法，它的原理就是在页表中预留一些空间，这样不会因为少量的数据写入造成树结构的大幅变动。但填充因子的设置也很难拿捏，过大则无法解决写放大问题；过小会造成页表数量膨胀，增大对磁盘的扫描范围，降低查询性能。