一、定义
LSM（Log Structured Merge Trees）日志结构合并树。
其实不是一种树，是一种思想
根B/B+树一样，常用于一些nosql数据库的索引结构(如Hbase Cassandra SQLite)。
它的出现时为了解决B+树 磁盘IO随机读取的效率问题。
LSM索引只做append 顺序读取,以提升磁盘IO效率
二、原理
把一棵大树拆分成N棵小树（B+树），它首先写入内存中，随着小树越来越大，内存中的小树会flush到磁盘中，磁盘中的树定期可以做merge操作，合并成一棵大树，以优化读性能。
LSM-Tree可以想象一份索引由两棵树组成：一个存在于内存（可以使用其他树结构），一个存在于磁盘（如下图）。
WAL
在设计数据库的时候经常被使用，当插入一条数据时，数据先顺序写入 WAL 文件中，之后插入到内存中的 MemTable 中。
这样就保证了数据的持久化，不会丢失数据，并且都是顺序写，速度很快。当程序挂掉重启时，可以从 WAL 文件中重新恢复内存中的 MemTable。
如HBase的HLog
MemTable
MemTable 对应的就是 WAL 文件，是该文件内容在内存中的存储结构。
Immutable Memtable
顾名思义，Immutable Memtable 就是在内存中只读的 MemTable，由于内存是有限的，通常我们会设置一个阀值，
当 MemTable 占用的内存达到阀值后就自动转换为 Immutable Memtable，Immutable Memtable 和 MemTable 的区别就是它是只读的，系统此时会生成新的 MemTable 供写操作继续写入。
之所以要使用 Immutable Memtable，就是为了避免将 MemTable 中的内容序列化到磁盘中时会阻塞写操作。
SSTable
SSTable 就是 MemTable 中的数据在磁盘上的有序存储。
合并
增删改操作都是追加操作，会造成同一个key存在冗余数据，这些数据将通过合并操作(compact)优化。
三、索引常用结构
参考：
https://blog.csdn.net/gongpulin/article/details/81015440
https://www.cnblogs.com/swordfall/p/10567468.html