Log Structure Merge Tree。LSM树实际上并不是一棵树，不像硬盘上的B+树、内存里的红黑树。 LSM树实际上是一种存储结构，被HBase、LevelDB、RocksDB、Influxdb这些NoSQL存储广泛采用。

特点：写效率超级高。 以日志的方式进行追加，而mysql需要先检索再修改。LSM树节省了检索操作。

优点：使用日志方式、顺序IO，提升写性能。 缺点：数据冗余。 改进：数据合并。

简明介绍

一切存储皆是KV存储，mysql的B+树本身也是KV存储。 LSM树是一种不同于B+树的存储结构。LSM树是一个文件树。查询时只需要从新到旧遍历LSM树即可找到value。 LSM树的树节点可以使用B+树来实现。

LSM树不应该被视为B+树索引的竞品，而应该视为B+树等单文件索引的管理器。

多个日志文件如何进行合并？

数据分类

WAL：write append log，写日志 内存数据memTable SSTable（磁盘数据）（Sorted String Table）有序键值对集合 redo日志

MemTable

MemTable是在内存中的数据结构，用于保存最近更新的数据，会按照Key有序地组织这些数据，LSM树对于具体如何组织有序地组织数据并没有明确的数据结构定义，例如Hbase使跳跃表来保证内存中key的有序。

因为数据暂时保存在内存中，内存并不是可靠存储，如果断电会丢失数据，因此通常会通过WAL(Write-ahead logging，预写式日志)的方式来保证数据的可靠性。

Immutable MemTable

当 MemTable达到一定大小后，会转化成Immutable MemTable。Immutable MemTable是将MemTable变为SSTable的一种中间状态。写操作由新的MemTable处理，在转存过程中不阻塞数据更新操作。

SSTable

有序键值对集合，是LSM树组在磁盘中的数据结构。为了加快SSTable的读取，可以通过建立key的索引以及布隆过滤器来加快key的查找。

LSM树过程

LSM树(Log-Structured-Merge-Tree)正如它的名字一样，LSM树会将所有的数据插入、修改、删除等操作记录(注意是操作记录)保存在内存之中，当此类操作达到一定的数据量后，再批量地顺序写入到磁盘当中。这与B+树不同，B+树数据的更新会直接在原数据所在处修改对应的值，但是LSM树的数据更新是日志式的，当一条数据更新是直接append一条更新记录完成的。这样设计的目的就是为了顺序写，不断地将Immutable MemTable flush到持久化存储即可，而不用去修改之前的SSTable中的key，保证了顺序写。

因此当MemTable达到一定大小flush到持久化存储变成SSTable后，在不同的SSTable中，可能存在相同Key的记录，当然最新的那条记录才是准确的。这样设计的虽然大大提高了写性能，但同时也会带来一些问题：

1）冗余存储，对于某个key，实际上除了最新的那条记录外，其他的记录都是冗余无用的，但是仍然占用了存储空间。因此需要进行Compact操作(合并多个SSTable)来清除冗余的记录。
2）读取时需要从最新的倒着查询，直到找到某个key的记录。最坏情况需要查询完所有的SSTable，这里可以通过前面提到的索引/布隆过滤器来优化查找速度。

LSM树的压缩操作

SSTable中存在大量的冗余数据，需要进行压缩，才能节约磁盘空间。

三个概念： 1）读放大:读取数据时实际读取的数据量大于真正的数据量。例如在LSM树中需要先在MemTable查看当前key是否存在，不存在继续从SSTable中寻找。
2）写放大:写入数据时实际写入的数据量大于真正的数据量。例如在LSM树中写入时可能触发Compact操作，导致实际写入的数据量远大于该key的数据量。
3）空间放大:数据实际占用的磁盘空间比数据的真正大小更多。上面提到的冗余存储，对于一个key来说，只有最新的那条记录是有效的，而之前的记录都是可以被清理回收的。

size-tiered策略：SSTable构成一个树形结构。随着SSTable的增多，达到16个的时候，将SSTable两两合并，形成8个二层SSTable。当二层SSTable满的时候，进行归并产生三层SSTable。 随着层数变多，顶层的SSTable会变得越来越大。

level-tiered策略：类似size-tiered，唯一区别是一个key在一层里面只位于一个SSTable里面，每层的SSTable之间没有重复key。