Log Structured Merge Trees (LSM) 1 概念 2 解决问题 3 应用场景 4 实现原理 5 优点 6 缺点 7 最佳实践 8 参考
LSM = Log Structured Merge Trees
来源于google的bigtable论文。
2 解决问题
传统的数据库如MySql采用B+树存放数据，B+树是一个随机读写的数据结构。 我们知道，顺序读写要比随机读写快无数倍，所以需要把数据结构改成顺序读写。
3 应用场景
LSM是当前被用在许多产品的文件结构策略：HBase, Cassandra, LevelDB, SQLite,甚至在mangodb3.0中也带了一个可选的LSM引擎（Wired Tiger 实现的）。
LSM-Tree比较适合的应用场景是：insert数据量大，读数据量和update数据量不高且读一般针对最新数据。
4 实现原理
4.1 基本原理
1、 数据按时间和大小分文件存放(sstable文件)。
2、 新的修改用Copy-On-Write Tree方式按key缓存在内存(memtable)中，内存中保序。
3、 内存达到时间或大小条件后，保存在一个新的文件里(顺序写，速度很快)。
4、 对已经保存的文件，不再修改。
5、 查询的时候，先查内存，然后依次查各个保存的文件。
6、 因为每个文件里的数据都是顺序存放的，所以查询速度较快(二分查找)。
4.2 提升读性能的方案
1、 定时触发文件合并操作，删除冗余记录，并减少文件个数，提升查询效率（由于sstable里的记录是顺序存放的，所以合并非常高效(归并算法、顺序读写)）。
2、 采用页缓存，减少二分查找的消耗。LevelDB 和 BigTable 是将 block-index 保存在文件尾部，这样查找就只要一次IO操作，如果block-index在内存中。
3、 采用布隆过滤器，减少不存在数据的判定逻辑。
4、 并行合并。
打个比方，合并操作就是JVM里的GC，在合并的时候，势必会影响其他操作。所以我们用G1的思想，把文件分区域，各个区域分别合并，这样，就可以减少停顿(加锁)的时间，同时也减少了合并文件额外需要的空间。
想想这个结构，类似于一颗新的树，这个树的每个节点是一个文件，每个文件的内容是sstable。
5 优点
1、写性能高。
2、只需要对内存部分加锁，文件不会修改，无需加锁
6 缺点
1、对于频繁大规模改动的场景不好。
7 最佳实践
1、 memtable丢失的问题：需要记录redo日志和恢复时间点，用于重建memtable。
2、
8 参考
LSM存储模型
https://www.cnblogs.com/chenny7/p/4568829.html
LSM 算法的原理是什么？