LSM树（Log-Structured-Merge-Tree）是一种采用追加写、数据有序以及将随机 I/O 转换为顺序 I/O的延迟更新，批量写入硬盘的数据结构

牺牲了小部分读性能，而大幅度提高了写性能，所以很适合写多读少的场景，已经用于LevelDB等开源产品中，阿里云的OTS也是基于此。

LSM树会将所有的数据插入、修改、删除等操作保存在内存中，当此类操作达到一定的数据量后，再批量地写入到磁盘当中。而在写入磁盘时，会和以前的数据做合并。在合并过程中，并不会像B+树一样，在原数据的位置上修改，而是直接插入新的数据，从而避免了随机写。

结构

LSM树的结构是横跨内存和磁盘的，包含memtable、immutable memtable、SSTable等多个部分。

  • memtable
    • memtable是在内存中的数据结构，用以保存最近的一些更新操作，当写数据到memtable中时，会先通过WAL的方式备份到磁盘中，以防数据因为内存掉电而丢失。
    • 预写式日志（Write-ahead logging，缩写 WAL）是关系数据库系统中用于提供原子性和持久性（ACID属性中的两个）的一系列技术。在使用WAL的系统中，所有的修改在提交之前都要先写入log文件中。
    • memtable可以使用跳跃表或者搜索树等数据结构来组织数据以保持数据的有序性。当memtable达到一定的数据量后，memtable会转化成为immutable memtable，同时会创建一个新的memtable来处理新的数据。
  • immutable memtable
    • immutable memtable在内存中是不可修改的数据结构，它是将memtable转变为SSTable的一种中间状态。
    • 目的是为了在转存过程中不阻塞写操作。写操作可以由新的memtable处理，而不用因为锁住memtable而等待。
  • SSTable
    • SSTable(Sorted String Table)即为有序键值对集合，是LSM树组在磁盘中的数据的结构。如果SSTable比较大的时候，还可以根据键的值建立一个索引来加速SSTable的查询

CRUD

  • 增/写：首先需要通过WAL将数据写入到磁盘Log中，防止数据丢失，然后数据会被写入到内存的memtable中，这样一次写操作即已经完成了，只需要1次磁盘IO，再加1次内存操作。相较于B+树的多次磁盘随机IO，大大提高了效率。随后这些在memtable中的数据会被批量的合并到磁盘中的SSTable当中，将随机写变为了顺序写。
  • 删：并不需要像B+树一样，在磁盘中的找到相应的数据后再删除，只需要在memtable中插入一条数据当作标志，如delKey:1933，当读操作读到memtable中的这个标志时，就会知道这个key已被删除。随后在日志合并中，这条被删除的数据会在合并的过程中一起被删除。
  • 改：与删除操作类似，都是只操作memtable，写入一个标志，随后真正的更新操作被延迟在合并时一并完成。
  • 查：相较于B+树慢很多，读操作需要依次读取memtable、immutable memtable、SSTable0、SSTable1……。需要反序地遍历所有的集合，又因为写入顺序和合并顺序的缘故，序号小的集合中的数据一定会比序号大的集合中的数据新。所以在这个反序遍历的过程中一旦匹配到了要读取的数据，那么一定是最新的数据，只要返回该数据即可。但是如果一个数据的确不在所有的数据集合中，则会白白得遍历一遍。可用布隆过滤器加速查询，也可以用索引加速查询

合并方式

  • size-tiered策略：是HBase采用的合并策略，具体内容是当某个规模的集合达到一定的数量时，将这些集合合并为一个大的集合。比如有5个50个数据的集合，那么就将他们合并为一个250个数据的集合。这种策略有一个缺点是当集合达到一定的数据量后，合并操作会变得十分的耗时。
  • leveled策略：是LevelDB和RocksDB采用的合并策略，size-tiered策略因为会产生大数据量的集合，所以会造成突发的IO和CPU资源的消耗，所以leveled策略使用了分层的数据结构来代替原来的大数据集合。leveled策略将集合的大小限制在一个小的范围内如5MB，而且将集合划分为不同的层级。每一个层级的集合总大小是固定且递增的。如第一层为50MB，第二层为500MB…。当某一层的数据集合大小达到上限时，就会从这一层中选出一个文件和下一层合并，或者直接提升到下一层。如果在合并过程中发现了数据冲突，则丢弃下一层的数据，因为低层的数据总是更新的。同时leveled策略会限制，除第一层外。其他的每一层的键值都不会重复。这是通过合并时剔除冗余数据实现的，以此来加速在同一层内数据的线性扫描速度。

比较B树和LSM树

读写速度

通常LSM树的写入速度更快，而B树的读取速度更快

LSM树上的读取通常比较慢，因为它们必须在压缩的不同阶段检查几个不同的数据结构和SSTables。

LSM树的优点

B树索引必须至少两次写入每一段数据：一次写入预先写入日志，一次写入树页面本身（也许再次分页）。即使在该页面中只有几个字节发生了变化，也需要一次编写整个页面的开销。有些存储引擎甚至会覆盖同一个页面两次，以免在电源故障的情况下导致页面部分更新

LSM树通常能够比B树支持更高的写入吞吐量，部分原因是它们有时具有较低的写放大（尽管这取决于存储引擎配置和工作负载），部分是因为它们顺序地写入紧凑的SSTable文件而不是必须覆盖树中的几个页面

LSM树可以被压缩得更好，因此经常比B树在磁盘上产生更小的文件。 B树存储引擎会由于分割而留下一些未使用的磁盘空间：当页面被拆分或某行不能放入现有页面时，页面中的某些空间仍未被使用。由于LSM树不是面向页面的，并且定期重写SSTables以去除碎片，所以它们具有较低的存储开销，特别是当使用平坦压缩时。

LSM树的缺点

日志结构存储的缺点是压缩过程有时会干扰正在进行的读写操作，因为磁盘资源有限

压缩的另一个问题出现在高写入吞吐量：磁盘的有限写入带宽需要在初始写入（记录和刷新内存表到磁盘）和在后台运行的压缩线程之间共享。写入空数据库时，可以使用全磁盘带宽进行初始写入，但数据库越大，压缩所需的磁盘带宽就越多。

如果写入吞吐量很高，并且压缩没有仔细配置，压缩跟不上写入速率。在这种情况下，磁盘上未合并段的数量不断增加，直到磁盘空间用完，读取速度也会减慢，因为它们需要检查更多段文件。

B树的一个优点是每个键只存在于索引中的一个位置，而日志结构化的存储引擎可能在不同的段中有相同键的多个副本。这个方面使得B树在想要提供强大的事务语义的数据库中很有吸引力：在许多关系数据库中，事务隔离是通过在键范围上使用锁来实现的，在B树索引中，这些锁可以直接连接到树