前言
LSM树全称为The Log structured Merage - Tree，根据名称可以大概认识到主要有以下特点：
- 是基于日志结构思想的。其中日志结构主要特点就是可以不断追加，而不做原始日志的覆盖。
- 要进行Merage，即要把日志结构进行Merage。
所以根据名称可以大概推测LSM的一些基本特性。
概念
LSM的思想起源于1996年的一篇论文(点击查看)
LSM的核心思想：将数据的添加和增量修改首先保存在内存中（追加日志的形式），而后满足一定条件后，将内存中的数据flush到磁盘上。磁盘中按照不同层级组织数据文件，内存中的数据首先flush到某一层级，而后当该层级满足一定条件后，会和磁盘上下一个层级的数据文件进行合并（Merage）。为了保证查询性能，内存中数据和磁盘中不同层级的数据都需要保持有序。如下图所示：
关键流程
写入
LSM的写入流程如下：1）首先写WAL日志，避免故障导致数据丢失；2）将数据写入C0内存中memtable，相当于在内存中保留最新的数据更新。3）当C0内存中的数据达到一定量级的时候（大小限制）会将C0中的数据flush到磁盘C1中，并且对磁盘C1层级的数据进行合并（归并排序）。4）当磁盘C1层级大小到一定规模，又会将C1中的数据同C2合并（归并排序）。5）以此类推，上一层级的数据文件达到一定规模后，会向下一层级合并。
特别说明
- 由于后面的磁盘文件合并是后台异步进行，不会阻塞数据写入内存，所以LSM的数据写入性能很高。
- 磁盘上不同层级数据文件合并时，会将原有本层级的数据删掉，重新写入新的数据文件，使磁盘是顺序写，这也避免了磁盘的时间消耗。
- 磁盘不同层级数据文件合并时，都会对本层级数据进行归并排序，也就是说，每一层级的数据永远都是有序的，这是为了保证查询时的效率。
查询
LSM的查询比较麻烦，由于内存中只保留了最近更新的数据，而且磁盘上不同层级的数据也不是完全完整的数据，越靠上层的数据越新，越靠下层的数据越老，所以查询时需要从上至下分别查询多次。1）首先查看内存中是否包含指定目标。若查到则直接返回，若没有查到则继续向下查找。2）其次查看磁盘C1层级中是否包含指定目标。以此类推，一直向下层级查找，直到命中指定目标或者查完所有层级后仍然没有命中（不存在）。
特别说明
- 由于上述查询的特性，所以LSM更适合高密度写入，低密度查询的场景。
- 有很多对于LSM查询的优化，比如增加布隆过滤器，来直接判断该key是否存在，而避免遍历所有层级的磁盘文件。又比如会增加一个类似于元数据的结构（levelDB中的Mainfest 文件，它描述各个层级数据的key最小值，最大值，层级数）查询时可以直接通过该结构快速定位要查找的数据层级。
更新
k-v的更新也就是写入的流程，内存中都是向后追加最新的数据记录，磁盘中合并的时候较新的数据值（上层级）会覆盖较老的数据值（下层级），每个层级合并完之后仅保留唯一并且有序的key。
删除
由于LSM不会直接在内存或磁盘上直接删除某个key，而是发生删除请求的时候追加一个特定标志的数据记录，比如 key-del，这意味该key被做了删除标记。只有当磁盘中数据文件合并的时候才会执行真正的删除。
LSM的优劣性
- 将用户随机写，转换为顺序写，以追加的方式快速写入，这些要素保证了其写入性能高，吞吐量大。
- 由于需要多次分批查询，导致读性能相对较差。（这个读性能查是相对的，在实际场景中，并不一定性能差）
- 读写放大问题：读写放大（read and write amplification）是 LSM-tree 的主要问题。读写放大 = 磁盘上实际读写的数据量 / 用户需要的数据量。由于磁盘IO带宽是共享的，特殊情况下，会对用户读写造成一定影响。
LSM的实现
LSM思想提出后，有很多基于该结构的数据库或文件系统的出现。并且在此基础上实现时对一些细节都做了不同的优化。
LevelDB、RocksDB、Cassandra、Hbase以及一些时序数据库（InfluxDB）都实现或借鉴了LSM的思想。
以下分别就LevelDB 和 Hbase 中的关键结构说明一下。
LevelDB
上图为LevelDB的基本架构。其中内存中有两种类型的memtable：一种是正常的memtable，接受用户的写入数据更新。一种是Immutable，将作为固定的不可更新的memtable。硬盘中包括若干个SStable，他们分别按照L0到L6进行分层，每一层都包含多个SStable文件，每一层的容量大小限制均为上一层的10倍。
写入时：1）还是先写入wal日志。2）然后写入memtable。3）当memtable满足容量限制后，则转换为immutable，停止接受数据写入，并再新开启一个memtable接收新数据的写入。这样的处理使得数据写入更加的连续，不会受到flush磁盘的影响。4）immutable的数据会直接flush到L0层，并且采取向L0层直接追加SStable文件而不是合并的方式添加，所以L0层的SStables中可能存在冗余数据（重复key）。5）然后L0超过限制后，会选择一个（最老）SStable同下层级进行合并，然后下一层级所有受此影响的SStable都会进行更新。更新完成后保证该层级（所有SStable）中的数据是唯一有序的。
查询时：依次memtable、immutable、L0、L1-L6
Hbase
数据先写入到内存中，对应HRegion中的memStore。
为了防止数据丢失同时写Log(类似WAL)，对应HRegion中的Hlog文件。
MemStore 到达一定大小后，刷磁盘，对应HRegion中的StoreFile（其中Hfile是真正的数据文件，并且里面还会包含类似于布隆过滤器的结构以及索引数据）。
HRegion内部的StoreFile 会不断合并更新。
总结
传统关系型数据库的索引一般是通过B/B+树结构实现的，B+树为了保证查询性能，其索引结构必须保证全局有序，所以这就导致在添加数据的时候需要树节点而引起重新排序（树平衡），也就造成了大量随机写磁盘的操作，影响效率。
LSM的重要思想就是使大量随机写变成了顺序写，大大提高了数据写入的性能，但是牺牲了部分读性能。
