Log-structured merge-tree
日志结构合并树 （LSM-Tree）。它是一种树形的数据结构，由多个层级组成，每层的数据按 key 有序。LSM-Tree 主要设计用来应对写入密集型工作负载，并于 1996 年在同名论文 The Log-Structured Merge-Tree (LSM-Tree) 被大家所知。
LSM-Tree 的最高层保存在内存中，包含最近写入的数据。其他较低层级的数据存储在磁盘上，层数编号从 0 到 N 。第 0 层 L0 存储从内存移动到磁盘上的数据，第 1 层及以下层级则存储更老的数据。通常某层的下个层级在数据量上会比该层大一个数量级，当某层数据量变得过大时，会合并到下一层。
⓵ MemTable
MemTable 在内存中缓存客户端写请求发送的数据，通常用平衡二叉树或跳跃表实现。MemTable 中存储的所有数据都是按照 key 有序排列的，当 MemTable 中存储的数据量到达设置的阈值时，这些数据会被写入磁盘，生成一个新的 SSTable。与此同时，一个新的空的 MemTable 被创建出来继续响应客户端的写请求。
客户端的读请求最先也是同 MemTable 进行交互
⓶ SSTTable
当 MemTable 中的数据量到达设置的阈值或 LSM-Tree 在后台对已有 SSTable 进行压缩操作时，新的 SSTable 就会被创建。SSTable 中的数据也是按照 key 有序存储，以提高读操作的性能。
同一个 SSTable 中的
key是有序的，但不同的 SSTable 之间的key不保证有序
随着时间的推移，写操作会导致磁盘上 SSTable 数量增加，这些 SSTable 会被不断的重新组织并压缩成从 level 0 到 level n 的不同级别。level 0 级的 SSTable 只是简单的将 MemTable 中的数据进行转储，并不进行其他的处理，所以多个 SSTable 中会出现重复的 key。level 1 及以后的级别的 SSTable 中则不会出现这种情况。
高 level 中的 SSTable 是通过压缩合并低 level 中的 SSTable 得到的
已有的 SSTable 在经过压缩合并后会生成新的、数据量更大的 SSTable 存入更高的 level 中，这样既可以减少磁盘中文件的数量，还有助于提升读操作的性能
往往越高的 level 中的 SSTable 的 size 会越大，SSTable 之间出现重复 key 的情况会越少
在实际应用中，为了提升 SSTable 读操作的性能，SSTable 中还会存储一些额外的元数据：
稀疏索引（sparse indexes）
稀疏索引提供 SSTable 中的 key 或 key 的范围到 key 的具体存储地址或偏移量的映射。SSTable 中的数据按照 key 有序存储，在 SSTable 中查找某个特定的 key 时，可以先通过稀疏索引定位查找的起始位置，然后再在 SSTable 中进行二次查找。
块索引（block-based indexes）
块索引的原理与稀疏索引类似，只不过块索引将 key 或 key 的范围映射到了指定的存储块（block）。SSTable 中的数据会被分成多个指定大小的块，每个块都会被分配一个指定的 ID 或偏移量，读操作先通过块索引定位要查询的数据所在的块，然后再在特定的块中进行二次查找。相对于稀疏索引，块索引的粒度相对比较粗。
bloom filter
bloom filter 可以快速确定要查找的 key 是否存在于指定的 SSTable 中。由于存在哈希碰撞，bloom filter 可能会误报，但不会漏报。
以上这些元数据，不一定同时存在于 SSTable 中，具体情况取决于各个应用中的代码实现。
为什么LSM不直接顺序写入磁盘，而是需要在内存中缓冲一下？
单条写的性能没有批量写快，很多中间件比如elasticsearch、kafka、mysql都有类似的内存缓冲设计
在磁盘缓冲的另一个好处是，针对新增的数据，可以直接查询返回，能够避免一定的IO操作
LSM-Tree和B+Tree的比较
LSM-Tree的优点是支持高吞吐的写O1，这个特点在分布式系统上更为看重
针对读取普通的LSM-Tree结构，读取是On的复杂度
在使用索引或者缓存优化后的也可以达到O(logN)的复杂度。
适用于写多读少
B+tree的优点是支持高效的读（稳定的O(logN)）
但是在大规模的写请求下（O(LogN)），效率会变得比较低，因为随着insert的操作，为了维护B+树结构，节点会不断的分裂和合并。操作磁盘的随机读写概率会变大，故导致性能降低。
适用于写少读多或写读平衡