B树与LSM树读写和空间放大分析

名词解析：

写放大：用户打算写的数据的大小除以实际写到磁盘上的数据的大小

读放大：查找操作所需要的磁盘IO次数

空间放大：需要使用的空间大小除以实际数据的大小

参数定义：

B：一个数据块上能存的记录数

N：数据库总记录数

测试机器与数据集大小：

内存：64GB

数据：10TB

B树（这里所说的B树都是特指B+树）：

写放大：对每一次写来说，节点分裂的概率是1/B，所以概率很小忽略不计。磁盘的写入单位是块，当写入一条记录时，就需要写入整个块，因此写放大是B。

读放大：B树的深度是O(logBN/B)。在没有缓存内部节点时需要自顶向下遍历树，因而读放大为O(logBN/B)。因为B树只在叶节点存储数据，内部节点比较小，在缓存全部内部节点时，读放大仅为1。

空间放大：B树中节点满了之后继续写会发生写分裂，分裂之后的节点填充率为1/2。可以假设B树中的节点的填充率在1/2到1之间是均匀分布的，因而得出平均填充率3/4。因而空间放大因子是4/3，约为1.3。

限制层中最大大小的LSM Leveled LSM Trees：从第一层往下大小逐层以k倍增长。

合并策略是：当某层的数据和下一层的数据加起来小于等于下一层应该有的大小就进行合并，合并后放到下一层。

写放大：LSM树的层数为O(logkN/B)，每一条数据在一层中被上一层平均合并k/2次（最少合并0次，最多合并k次，取平均为k/2），因此写放大为k/2*O(logkN/B)=O(klogkN/B)，即O(扇出*树深)。

读放大：如果需要在每一层进行二分查找，最底层需要的读次数为logN/B，倒数第二层为logN/(kB)=logN/B-logk，倒数第三层为logN/(k2B)=logN/B-2logk,...第一层为1,去平均为(logN/kB)/2。因此总的读放大为O(logkN/B)*(logN/B)/2=O(logkN/B)*(logN/B))=O((log2N/B)/logk)。在leveldb中从元信息中可以拿到数据分布的的表，直接定位，不需要二分查找，因而读放大就是树深度O(logkN/B)。k=10的情况下，在内存中缓存10TB，1TB，100GB的层都是不可能的，因而在缓存其他层时，其读放大可以为3。

空间放大：在合并的过程中需要读取两层，并且新生成一层。在每层只有一个文件的时候，在应用新的层文件并且删除原来的两层文件之前，需要在磁盘中保存同一数据的两份，因此其空间放大是2。在每层有多个文件的时候，如果最底层有90%的数据，则上面一层最多有10%的数据，在合并的过程中，新生成文件有20%的大小，因此空间放大为1.2。（与论文中得出的结论不同，敬请指正）

按大小分层的LSM Size-tiered LSM Trees：

合并策略：每k层一组，当他们都达到最大大小时，合并成一个新的层，其中每一层使用单一文件实现。

写放大：LSM树中层的组数为O(logkN/B)，一条数据只会被写到一组中一次。因此写放大为O(logkN/B)。

读放大：需要读O(klogkN/B)层，对于每一层使用二分查找的情况读放大为O(k(log2N/B)/logk)。如果每一层有元信息则读放大可以减小到O(klogkN/B)。

空间放大：在合并时需要生成一个新的层，新的层的大小最大是N，因此空间放大是2。（与论文中得出的结论不同，敬请指正）

总结：

B树的读放大和空间放大比较小，但是写放大很大。适合读多的场景，特别是小范围读多的场景，对于大范围读需要多次随机读，性能不佳。

限制层中最大大小的LSM写放大、读放大和空间放大都控制的都比较好。适合读写均匀的场景。对于GET方式的读取，因为其不可变性质，可以使用bloom filter。对于大范围扫描，因为其磁盘块是连续存储的，读取速度也会比较快。

按大小分层的LSM的写放大最小，但是读放大和空间放大很大。适合写多并且对空间放大不敏感的应用场景。

参考文献：A Comparison of Fractal Trees to Log-Structured Merge (LSM) Trees