WAL：Write Ahead Log 写前日志，顺序日志文件

1 LSM tree的定义

LSM tree：
Log-Structured-Merge-Tree，日志结构合并树。

Log-Structured Merge-tree (LSM-tree) is a disk-based data structure designed to provide low-cost indexing for a file experiencing a high rate of record inserts (and deletes) over an extended period.

可以认为，LSM tree是内存的树和磁盘文件的树的集合。
如LSM的内存中的memtable可以使用B+Tree实现、磁盘上面的每层sst文件也可以使用B+Tree实现。

2 LSM tree的组成

LSM tree包括三个部分：

1. MemTable，
2. Immutable MemTable，
3. SSTable(Sorted String Table)
   

2.1 MemTable

MemTable 是内存中的数据结构，用于保存最近更新的数据，会按照 Key 有序地组织这些数据。
可以是红黑树、跳表等。

2.2 Immutable MemTable

内存数据持久化到磁盘时增加的缓存。

2.3 SSTable

有序键值对集合。文件结构基本思路就是先划分为数据块，然后再为数据块建立索引，索引项放在文件末尾。

当某层的SSTable数量大小达到阈值，会通过 Compact 策略将其转化到下一层。
有两种基本策略：

1. size-tiered 策略
2. leveled 策略

3 LSM tree的操作

利用顺序写来提高写性能，代价就是会稍微降低读性能（读放大），写入量增大（写放大）和占用空间增大（空间放大）。

3.1 LSM tree的插入、修改、删除

LSM 树的插入、修改、删除都是在 L0 层的树里操作，并记录记录项的时间戳。

3.2 LSM tree的查找

查找只需从 L0 层往下查，直到查到某个 key 的记录就可以了。

4 LSM tree的与B+tree对比

1. LSM tree吞吐量高写入性能高；
   LSM 树不需要磁盘 IO，直接操作内存，单次插入耗时短，所以其写入的最大吞吐量是高于 B+ 树的。
2. LSM tree查找效率低；
   查找时， LSM tree需要遍历所有层次的树，查找效率上要低于 B+ 树。
3. 并发控制和故障恢复方面：
   

5 LSM tree的应用

LSM 树主要被用于 NoSql 数据库中，如 HBase、RocksDB、LevelDB 等。
TiDB 的底层存储也是用的 LSM 树。

6 小结

LSM tree特点：顺序写入、Compact 操作、读、写和空间放大。
LSM tree适用场景：对于写操作吞吐量要求很高、读操作吞吐量要就较高的场景，目前主要在 NoSql 数据库中用的比较多。