LSMT（Log-Structured Merge-Tree）

LSM简介Log Structured Merge Tree，下面简称 LSM。2006年，Google 发表了 BigTable 的论文。这篇论文提到 BigTable 单机上所使用的数据结构就是 LSM。目前，LSM 被很多存储产品作为存储结构，比如 Apache HBase, Apache Cassandra, MongoDB 的 Wired Tiger 存储引擎, LevelDB 存储引擎, RocksDB 存储引擎等。简单地说，LSM 的设计目标是提供比传统的 B+ 树更好的写性能。LSM 通过将磁盘的随机写转化为顺序写来提高写性能 ，而付出的代价就是牺牲部分读性能、写放大（B+树同样有写放大的问题）。LSM 相比 B+ 树能提高写性能的本质原因是：外存，其随机读写都要慢于顺序读写，无论磁盘还是 SSD。

1. 追加写日志，顺序写提高写入效率。
2. 构建SSTables（sorted string tables）。
1. 写入时，首先写入Memtable内存表(排序结构，保存键和磁盘偏移位置)。当内存表大于某个阈值，作为SSTables写入磁盘。防止数据库崩溃，导致写入内存表，但还未写入磁盘的数据丢失，可以进行wal，类似于redo log。
2. 读取时，首先在内存表中查找键，然后是最新的磁盘段文件，接下来是次新的磁盘段文件，直到找到目标（或为空）。防止查找数据库中某个不存在的键很慢，引入布隆过滤器。对于数据库中不存在的某个键，会很快告诉你结果。
3. 压缩SSTables
1. 后台进程周期性地合并与压缩磁盘段。这个阶段可以用旧段继续正常读取、写入，合并完成后切换新段。