本文版权归作者所有，欢迎转载，但未经作者同意必须保留此段声明，且在文章页面明显位置给出原文连接，否则保留追究法律责任的权利。
转载自夜明的孤行灯
B+树使用广泛，而它最大的性能问题是会产生大量的随机IO，随着新数据的插入，叶子节点会慢慢分裂，逻辑上连续的叶子节点在物理上往往不连续，甚至分离的很远，但做范围查询时，会产生大量读随机IO。
LSM树最早是HBASE引入的，最初目的就是为了克服B+树的弱点。LSM树本质上就是在读写之间取得平衡，和B+树相比，它牺牲了部分读性能，用来大幅提高写性能。本质上就是把树拆开，拆成一个一个小树，当树足够大了再写入，当然读取的时候就需要访问多个树了。在写入硬盘后，也会在一定时机下，处理已经写入的树，进行再次合并。
LSB树会有一个WAL，因为内存中的数据有丢失风险，所以先写日志，当内存中对应的树刷盘以后删除对应日志就行了。
LSB树一般有三个放大点需要关注
- 写放大： 磁盘数据的写入量 / 用户写入的数据量
- 读放大： 磁盘数据的读入量 / 用户实际要读取的数据量
- 空间放大：磁盘空间占用 / 有效的用户数据量
其中写放大往往是最严重的，对它的计算和分析也相对较多。
写放大是最有意思的，根据LSM的原文，作者提到层与层之间的扇出系数(size ratio)是常量时，写放大最优。FaceBook的文档中有获得最优写放大倍数具体的计算方式，详细推导参见：http://smalldatum.blogspot.com/2018/12/lsm-math-how-many-levels-minimizes.html
本文版权归作者所有，欢迎转载，但未经作者同意必须保留此段声明，且在文章页面明显位置给出原文连接，否则保留追究法律责任的权利。
转载自夜明的孤行灯