LSM树 - Log Structured Merge Tree，LSM树并不是一个严格意义上的树状数据结构。目前HBase、LevelDB、RocksDB等 NoSql存储都基于LSM树做的。

LSM树由以下几个重要部分组成，

1. MemTable: 内存中的数据结构，保存最近更新的记录，会按照key进行有序存储。如果保证有序没有严格定义，如跳表或者B+数都可以。 也会有WAL机制保证数据可靠性

2. Immutable MemTable 当MemTable达到一定大小之后，会转化为Immutable Memtable。这个是一种中间状态，就是Memtable到SSTable的中间状态。新的写操作 由新的Memtable处理，应该相当于一种buffer

3. SSTable Sorted String Table，有序键值对的集合，存在磁盘中。一般为了加快对SSTable的读取，会建立索引和布隆过滤器做过滤。

LSM的所有行为都是追加，不会在原有位置做修改，这样的目的是为了顺序写。所以一个key可能有多个版本，有冗余存储的问题。

LSM树有Compact的策略，否则SSTable会不断膨胀。

读取过程：首先从MemTable中查找，不命中会转到Immutable MemTable，若还不命中，跳转到SSTable。从L0一直往下查。 MemTable和SSTable都会维护一个布隆过滤器，提高查找效率。在剩余的SSTable（除L0外），每个SSTable之间都是不交叠的，可以 用二分先定位到SSTable的层级再查找。

写的过程： 如果memetable未达到阈值（默认4MB）则允许写入；如果memtable已达到阈值，但是immutable memtable仍存在，则等待compaction将其 dump完成；memtable已写满，immutable memtable不存在，则将当前的MemTable置成immutable memtable；当然数据会先WAL。

Compaction过程： LSM中一个非常重要的过程就是compaction。随着sstable的不断写入，对一个key的累积数据改变操作增多。sstable就会不断膨胀。 LSM树分成了若干个Level，每层Level都按照key的顺序分成若干个sst file。每个sst file内部的key都是有序的。 Level0保存着最新的数据,L0中不同的文件可能存在相同的key。但是L1和之后的Level不会。

具体合并流程如下：

1. 找到score最高的level

2. 按照一定策略从level中选择一个sst文件进行compact。

3. 获取sst文件的minKey和maxKey

4. 从level+1中选取出于 minKey，maxKey有重叠的sst文件，有重叠的文件则把文件与level中的文件进行合并作为目标文件

5. 对目标文件压缩后放入level+1中。