在数据库领域，B+树拥有无可撼动的地位，但是B+树的缺点就是在写多读少的场景下，需要进行大量随机的磁盘IO读写，而这个性能是最差的。并且在删除和添加数据的时候，会造成整个树进行递归的合并、分裂，数据在磁盘上也不是连续的。所以会不断的随机写入操作。

所以针对这个问题，如何在写多读少的场景下提升性能，LSM就是为了解决这个问题。
LSM（Log Structure Merge Tree）比B+树更适合写多读少的场景。
主要原理LSM通过批量的合并写数据，减少磁盘旬道的开销。

早期LSM Tree

C0-tree 是存储在内存中，而C1-tree是存储在磁盘中。

核心流程是：先将数据写入到C0-tree，当C0-tree数据写入到一定的阈值时，然后开始批量将数据合并和覆写，因为可以批量写入，所以写入磁盘可以进行顺序写入，避免单次的随机写操作。

现代的LSM-tree也是通过内存维护有序结构，然后延迟写入磁盘的时机，通过合并多次随机写操作。降低磁盘移动的开销。
所以在写多读少的场景下，比B+树能获得更多的性能。

现代 LSM Tree

包含三部分，memtable、immutable memtable、SSTable，前两个在内存中，后一个在磁盘中。先将数据写入到memtable、然后在合适的时机写入到SSTbale中。

其实仔细一想，如果数据都在内存中，那么一旦出现断电或者机器宕机，那么内存中的数据就会丢失？LSM如何来防止出现数据丢失呢
很简单，其实就是利用WAL机制，也就是同步写入到内存中的时候，同步写入到磁盘中一份，因为是是以追加append Only的方式存储，所以可以在一定程度提写数据的性能。

1.Memtable
memtable存储的是近期最新的数据记录，一般使用跳表或者哈希等实现。可以快速的删除和查找。
2.Immutable Table
在memtable达到一定的量级之后，然后会进行数据的合并，好处是一个可以快速的进行顺序写入磁盘中，另一个通过数据副本的方式，memtable可以继续提供服务。
3.SSTable

包含两部分一个是索引文件，另一个就是数据文件。
写入数据的时候，会按照一个segment为一段，直接将最新的数据追加。那样的话，从尾部查询最后一条数据就是最新的数据。但是这样极端情况下，可能多个数据存储多次，造成磁盘的浪费。并且重复数据多的话，查询效率很差，但是可以利用布隆过滤器进行优化。

压缩数据
压缩数据，其实就是将多个segment合并成一个新的segment，图中最新的dog是84，所以dog：52在合并之后就不存储了。

删除数据
删除数据的时候，其实不删除真实数据，而是逻辑删除，通过标记位tombstone。如果存在就代表数据被删除，否则数据存在。

小结

本篇主要为了解决在B+树中读少写多而带来的数据合并和分裂，引入了LSM，LSM的核心其实就是将数据分为两部分，一部分在内存中，定时更新到磁盘，使用WAL机制来保证数据不丢失。所以在写多读少的场景下，可以通过使用LSM结构进行构建分布式存储结构。