参考：
https://blog.csdn.net/zxpoiu/article/details/116190330
https://kernelmaker.github.io/Btree_LSM_FTI
https://zhuanlan.zhihu.com/p/141186118
基础概念
读放大（read amplification）：一次读取操作需要访问磁盘的次数，主要由compaction策略引入。可以引入cache和bloom filter优化。
写放大（write amplification）：一次写操作带来的数据落盘的次数。在LSM-Tree中可由某个key数据在磁盘上存储的数量这个指标体现，主要是由compaction策略引入的。
空间放大（space amplification）：实际空间占用/理论数据量，LSM-Tree的架构导致空间放大必然存在
临时空间：compaction任务需要临时的空间来完成多个sstable的合并。
run：借用wiki中的解释:
The on-disk data is organized into sorted runs of data. Each run contains data sorted by the index key. A run can be represented on disk as a single file, or alternatively as a collection of files with non-overlapping key ranges. To perform a query on a particular key to get its associated value, one must search in the Level 0 tree and each run.可见，每一个run都是有序的数据块。
Size-tired compaction strategy(STCS)/Tiered
结构
每层有固定数量的文件（SSTable），相邻层之间的文件大小呈倍数关系。对于同一层的SSTable，范围有可能有重叠。
假设数据集大小为N，放大因子为k，最小层一个文件大小为B， 最大层有k个大小为N/k个文件，倒数第二层有k个大小为N/kk个文件…那么一共有O((log N/B)/(log k))层。
compaction（写入）
- memtable达到阈值之后刷入下一层（落盘）作为一个sstable文件。
- 每层有多个sstable，当sstable达到一定数量之后，将当前层所有sstable进行compaction并刷入下一层，作为下一层的一个sstable。
读取
点查询
- 首先读取memtable，查询不到则逐层扫描sstable。
- 对于某层的的查询，由于同一层的多个sstable是有可能范围重叠的，所以要从新到旧的遍历每一个sstable，如果sstable范围与查询条件重合，则加载对应的sstable到内存中二分查找，查找到对应的数据记录，即可结束搜索，返回结果。
范围查询
- 首先读取memtable，并扫描所有层的sstable。
- 对于某层的的查询，遍历每一个sstable，如果sstable范围与查询条件重合，则加载对应的sstable到内存中二分查找，查找查询范围内的数据。
- 合并memtable和每一个sstable查找到的结果，并进行去重，返回结果。
总结
- 写放大：写放大比较低，同一个record，在每一层只会写一次，所以写放大等于层数，即O((log N/B)/(log k))。
- 读放大：每层都有多个sstable，且每个sstable中的数据可以重叠，所以点读操作需要由上到下遍历每一个sstable，读放大较严重。更不要提range查询肯定要合并每一层的每一个run的查询结果，读放大更严重。每一层读k个文件，一共O((log N/B)/(log k))层，故一共需要读O(k(log N/B)/(log k))个文件，不同于Leveld LSM Tree，一个文件不只是一个block B，而是有很多blocks，近似O(N/B)个，在文件内部二分查找找到对应的block需要O(log N/B)，故整体需要O(k(log N/B)(log N/B)/(log k))次I/O，即读放大为O(k(log N/B)(log N/B)/(log k))
- 空间放大：由于每层有多个sstable，每个sstable都可能含有重叠数据，所以空间放大较为严重。
- 临时空间：每层的多个sstable需要先合并，才能写入下层，因此有可能导致临时空间较大。耗时也较长
综上，STCS的写放大较低，读放大、空间放大、和临时空间都较高，适合write-intensive workload。
leveled compaction
结构
每层的文件（SSTable）的大小是固定的，相邻层之间的文件数量呈倍数关系，对于同一层的SSTable，范围没有重叠。
假设数据集大小为N，放大因子为k，最小层一个文件大小为B，每层文件的单个文件大小相同都为B，不过每层文件个数不同， 最大层有N/B个文件，倒数第二层有N/Bk个文件…，一共有O((log N/B)/(log k))层。
compaction（写入）
- 每层有多个sstable，当sstable达到一定数量之后，选择某个sstable与下一层的所有sstable进行merge compaction。
- 由于同一层的sstable范围不重叠，某个sstable与下一层进行merger compaction时，只需要选择下一层中相关的sstable进行操作即可。
读取
点查询
- 首先读取memtable，查询不到则逐层扫描sstable。
- 对于某层的的查询，由于同一层的多个sstable是不重叠的，可以直接对所有sstable进行二分查找，查找到对应的数据记录，即可结束搜索，返回结果。
范围查询
- 首先读取memtable，并扫描所有层的sstable。
- 对于某层的的查询，直接对所有sstable进行二分查找，查找查询范围内的数据。
- 合并memtable和每一个sstable查找到的结果，并进行去重，返回结果。
总结
- 写放大：由于leveled compaction上层与下层merge的过程有可能涉及到上下层所有的数据，可能造成下层sstable全量重写，导致写入放大。同一个record，会在本层写k次之后才会被compact到下一层，也就是说每次层会放大k，所以写放大为O(k(log N/B)/(log k))
- 读放大：由于每一层的sstable都是范围不重叠且有序的，所以可以直接在一层进行二分查找。依次在每一层进行二分查找，直到在最后一层找到，即： R = (log N/B) + (log N/Bk) + (log N/Bkk) + … + 1 = (log N/B) + (log N/B) - (log k) + (log N/B) - 2(log k) +… + 1 会有R次I/O，故读放大为R，即O((log N/B)*(log N/B)/(log k))。
- 空间放大：由于每层的多个sstable范围不重叠，所以空间放大较低。
- 临时空间：由于每层可以分为多个partition(sstable)，因此可以节约部分临时空间，即一次只需要处理上层的一个sstable和下一层的sstable，循环多次即可完成compaction。
综上，leveled compaction的写放大较高，读放大、空间放大、和临时空间都较低，适合read-intensive workload。