LSM-tree(Log Structured-Merge Tree)的理解

0.术语：

WAL （write ahead log） 是一个追加写日志，用来做简单的流水记录和备份。

LSM-tree (Log Structured-Merge Tree), 被称为谷歌三驾马车之一，也是一种追加写的日志文件，但是相比粗暴的 WAL, 他将日志分割成本多段，并且每一段都做了查询索引（每一段的查询性能是 Ologn ）。

SStables (Sorted Strings Table) 可以看成是一张map表，但是他的查询依赖树形索引，查询的复杂度是 Ologn， 他把 key-values 写入一张表，然后再给这张表的key排序，再将排序的索引表塞入到数组尾部，就形成了一个 map结构。
如下图：

1.LSM-tree，的另一个名字叫 bigtable

我觉得更准确的说，是一个长长的数组，数组的元素是一个 key-value 对子。

1.1写入的时候：

往存放数组信息的文件尾部追加元素，并为其建立一个顺序索引（索引可以方便后续快速通过key定位元素）。

当数组追加到一定程度后（比如10M），文件放不下了，就重新新建文件，为该文件创建新的数组索引。

1.2 读取的时候：

读取的时候，就是一个一个的去找文件，假如有k个文件，每个文件有n个元素，那么数组的总长度就是 k*n ， 查询的复杂度就是 k * O(logn)。

1.3 优化方案：

为了避免文件数量 k 越来越多，后台会定时的将小文件合并成大文件，即，把小文件的元素合并后，对其建立一个更大的sstable索引。

1.4 其他优化方案：

1）对sstable文件进行分段压缩，提高带宽利用率。

2) 采用LRU等算饭对 sstable 页内存进行管理，提高缓存访问性能。

3）bloom filter, 搜索key的时候跳过一定不包括该key的文件，加速搜索

4) 选择合适的时间进行文件合并，避免影响读性能。