LSM(Log Structured Merged Tree)树一般用在写多读少的场景，比如日志类型的数据，是HBase、 Cassandra、 LevelDB、 RocksDB 以及 ClickHouse MergeTree 等流行的 NoSQL 数据库的底层数据结构
核心思想
- WAL保证数据持久性
- 数据写入内存，达到阈值后再批量写入磁盘
- 数据的所有操作：增删改全部作为顺序写，追加写的方式，大大提升写入性能
- 顺序追加写会形成很多无用的数据，需要异步实现数据压缩和整理
核心原理
这张经典图片来自 Flink PMC 的 Stefan Richter 在Flink Forward 2018演讲的PPT
typical LSM backed system
SSTable (Sorted String Table)
LSM-Tree的优点和缺点
与B-tree系列数据结构相比，LSM的写性能提升10作用倍，读性能降低10倍左右（但是使用布隆过滤器Bloom Filter可以改进读性能，特别是针对不存在的key的读取性能的改进）
写入流程
- 写入WAL（Write Ahead Logging）保证数据持久性
- 写入Active MemTable
- 如果Active MemTable写满，则变成Immutable MemTable，再一步写入到磁盘中的SSTable，同时生成一个新的Active MemTable
- 更新索引
- 更新布隆过滤器
读取流程
- 读取MemTable，如果读取到则返回
- 读取布隆过滤器，如果没有，则返回
- 如果布隆过滤器存在，则使用索引定位SSTable
- 如果索引不存在，则返回空值
- 如果存在则加载索引值对应的SSTable，读取指定的值
数据合并流程
因为LSM都是追加写入SSTable，哪怕是删除操作都是追加一个标识，所以经过一段时间的操作后，就会存在很多重复的key以及被删除的key，所以还需要进行数据合并，减少资源占用以及提供查询性能
参考
- Log Structured Merge Trees
- Understanding LSM Trees: What Powers Write-Heavy Databases
- LSM 树详解
- 平衡二叉树、B树、B 树、B*树 理解其中一种你就都明白了
- 一文了解数据库索引：哈希、B-Tree 与 LSM
- 深入理解什么是LSM-Tree
- 日志结构的合并树 The Log-Structured Merge-Tree
- LSM-tree vs B-tree
