log-structured merge-tree (LSM tree) 是一种被精心设计的数据结构，罕用于解决大量写入的场景。通过对写入操作进行程序写入优化实现性能晋升。LSM tree 是很多数据库外部的外围数据结构，包含 BigTable, Cassandra, Scylla，和 RocksDB。

SSTables

LSM tree 通过一种叫做 SSTable (Sorted Strings Table) 的格局，长久化到硬盘上。正如其名，SSTable 是一种用来存储有序的键值对的格局，其中键的组织是有序存储的。一个 SSTable 会包含多个有序的子文件，被称为 segment。这些 segments 一旦被写入硬盘，就不能够再批改了。一个简略的 SSTable 例子如下图所示：

咱们能够看到，在每个 segment 中的键值对都是依照键的程序有序组织的。

写入数据

因为 LSM tree 只会进行程序写入，所以自然而然地就会引出这样一个问题，写入的数据可能是任意程序的，咱们又如何保证数据可能放弃 SSTable 要求的有序组织呢？
这就须要引入新的常驻内存 (in-memory) 数据结构: memtable_了, _memtable 的底层数据结构则有点像红黑树, 当由新的写入操作则将数据插入到红黑树中。

写入操作会先把数据存储到红黑树中，直至红黑树的大小达到了事后定义的大小。一旦红黑树的大小达到阈值，就会把数据整个刷到磁盘中，这个过程就能够把数据保障有序写入了。通过一层数据结构的承接，就能够保障单向程序写入的同时，也能保证数据的有序了。

读取数据

那么咱们是如何从 SSTable 中查找数据的呢？一种 naive 的办法就是遍历所有的 segments，寻找咱们须要的 key。从最新的 segment 到最老的 segment 一一遍历，晓得找到指标 key 为止。显然，这种形式在寻找刚刚写入的数据是比拟快的，然而文件一多就不太行了。因而也有针对这个问题的优化，稠密索引 就是一种在内存中对数据检索进行优化的技术。

咱们能够通过这个索引疾速找到所需键的后面和前面的偏移量（就是最近的相邻值），这样咱们就只须要扫描很小一部分的 segments 文件就能够了。以如图所示的场景举例，当咱们须要搜寻 dollar 这个值，咱们能够通过二分查找搜寻稠密索引，能够晓得 dollar 处于 dog 和 downgrade 之间。因而咱们只须要搜寻 17208 和 19504 之间的 segment 来失去咱们所需的值，如果搜寻不到则可返回未命中。

译者注：稠密索引和跳表都是为了解决疾速索引的问题，依据不同设计具体抉择。

下面优化在查找存在的数据其实曾经不错了，然而在搜寻不存在的 key 值的时候还是要遍历所有的 segment 才能够确定。为了解决这个问题，就须要引入 布隆过滤器。布隆过滤器是一种以空间换工夫的数据结构，可能帮忙咱们疾速确定某个值是否不存在（如果布隆过滤器认为该值存在，也可能是理论不存在的）。咱们能够在写入数据的时候同时更新布隆过滤器，来减速不存在数据的检索。

数据合并

随着工夫的推移，整个存储系统将会存储十分多的 segment 文件，所以这些文件须要进行肯定的整顿和合并，防止文件太多无法访问。这个文件整顿的过程被称为“数据合并”(compaction)。数据合并是一个后盾线程，将会继续地将老的 segment 合并到一起变成新的 segment。

如图所示，咱们能够看到 segment 1 和 segment 2 都有 key 为 dog 的两个值。合并后的新 segment 将会保留更新的值，因而会保留原有 segment 2 外面的值 84，即 segment 4 中的值是 dog => 84。一旦合并过程曾经实现新的 segment 写入，那么原有的老 segment 文件将会被删除。

删除数据

咱们曾经解释了读取数据和写入数据的过程，那么删除数据又是如何解决的呢？咱们曾经晓得 SSTable 是不可变的，所以外面的数据当然也不可能删除。其实删除操作其实和写入数据的操作是一样的，当须要删除数据的时候，咱们把一个特定的标记（咱们称之为 墓碑 (tombstone)）写入到这个 key 对应的地位，以标记为删除。

上图演示了原来 key 为 dog 的值为 52，而删除之后就会变成一个墓碑的标记。当咱们搜寻键 dog 的时候，将会返回数据无奈查问，这就意味着删除操作其实也是占用磁盘空间的，最初墓碑的值将会被压缩，最初将会从磁盘删除。

总结

咱们曾经根本形容了 LSM tree 引擎是如何工作的：

1. 写入操作是先写入内存的（被成为 memtable）。所有的用于减速查问的数据结构（布隆过滤器和稠密索引）都会被同时更新；
2. 当内存中的 memtable 太大了，将会被刷到磁盘中，留神是有序的；
3. 当查问时咱们先回查问布隆过滤器，如果布隆过滤器返回说键不存在，则理论不存在，如果布隆过滤器说存在，进一步遍历 segment 文件；
4. 对于遍历 segment 文件的过程，咱们将会先通过稠密索引找到最小的文件范畴，并开始由新到老开始遍历，找到一个 key 则间接返回。