LSM-Tree

B-Tree 这种数据库索引方式是传统关系型数据库中主要的索引构建方式，然而 B-Tree 通常会存在写操作吞吐量上的瓶颈，其需要大量的磁盘随机 IO，很显然，大量的磁盘随机 IO 会严重影响索引建立的速度。对于那些索引数据大的情况(例如，两个列的联合索引)，插入速度是对性能影响的重要指标，而读取相对来说就比较少。譬如在一个无缓存的情况下，B-Tree 首先需要进行一次磁盘读写将磁盘页读取到内存中，然后进行修改，最后再进行一次 IO 写回到磁盘中。

LSM-Tree 则采取读写分离的策略，会优先保证写操作的性能；其数据首先存储内存中，而后需要定期 Flush 到硬盘上。LSM-Tree 通过内存插入与磁盘的顺序写，来达到最优的写性能，因为这会大大降低磁盘的寻道次数，一次磁盘 IO 可以写入多个索引块。HBase, Cassandra, RockDB, LevelDB, SQLite 等都是基于 LSM-Tree 来构建索引的数据库；LSM-Tree 的树节点可以分为两种，保存在内存中的称之为 MemTable, 保存在磁盘上的称之为 SSTable。

LSM-Tree 的主要思想是划分不同等级的树。以两级树为例，可以想象一份索引数据由两个树组成，一棵树存在于内存，一棵树存在于磁盘。内存中的树可以可以是 AVL Tree 等结构；因为数据大小是不同的，没必要牺牲 CPU 来达到最小的树高度。而存在于磁盘的树是一棵 B-Tree。

数据首先会插入到内存中的树。当内存中的树中的数据超过一定阈值时，会进行合并操作。合并操作会从左至右遍历内存中的树的叶子节点与磁盘中的树的叶子节点进行合并，当被合并的数据量达到磁盘的存储页的大小时，会将合并后的数据持久化到磁盘，同时更新父亲节点对叶子节点的指针。

之前存在于磁盘的叶子节点被合并后，旧的数据并不会被删除，这些数据会拷贝一份和内存中的数据一起顺序写到磁盘。这会操作一些空间的浪费，但是，LSM-Tree 提供了一些机制来回收这些空间。磁盘中的树的非叶子节点数据也被缓存在内存中。数据查找会首先查找内存中树，如果没有查到结果，会转而查找磁盘中的树。有一个很显然的问题是，如果数据量过于庞大，磁盘中的树相应地也会很大，导致的后果是合并的速度会变慢。一个解决方法是建立各个层次的树，低层次的树都比 上一层次的树数据集大。假设内存中的树为 c0, 磁盘中的树按照层次一次为 c1, c2, c3, ... ck-1, ck，合并的顺序是 (c0, c1), (c1, c2)...(ck-1, ck)。

LSM-Tree

我们需要一整套的机制来完成从内存排序、写入到磁盘、压缩以及快速读取，这样的完整机制和架构称为 LSM-Tree(The Log-Structured Merge-Tree)。名字很形象，首先是基于 log 的，不断产生 SSTable 结构的 log 文件，并且是需要不断 merge 以提高效率。基于合并和压缩排序文件原理的存储引擎通常都被成为 LSM 存储引擎。

LSM-Tree 的基本思想足够简单有效，可以有效地支持区间查询，支持非常高的写入吞吐量。但当 LSM-Tree 查找某个数据库中不存在的 key 时，需要检查索引及所有的段文件，为了优化这种情况，存储引擎通常会使用布隆过滤器。

哈希表

在数据库实现中，首先考虑建立最简单的 key-value 索引，通常采用类似 HashMap 的方式来实现。如果所有的存储采用追加文件的方式完成，那么可以在内存中保存这个 HashMap，其中 Map 的值对应文件中的偏移量。当写入和更新时需要同时更新索引，查询时首先找到 Map 中的偏移量然后读取文件中的内容。为了避免过多的磁盘占用，我们可以将文件分为不同的段，每个段对应一个哈希索引表，新写入的数据追加在最新的段上，每过一段时间后台合并压缩多个段。为了找到 key 对应的 value，首先检查最新段的 HashMap，如果不存在则依次检查次新的段，以此类推。

SSTables

如果简单地改变段文件的格式，要求 key-value 的顺序按照 key 排序，那么这就变成了排序字符串表（SSTable），它要求每个键在每个合并的段文件中只能出现一次。这样相比不排序的哈希索引日志段模式，具有以下优点：

• 合并段更加高效，即是每个段非常大，也能利用类似归并排序中的合并算法，支持同时合并多个段。
• 查找特定 key 时，无需在内存索引中保留所有的 key。如要查找 AAD 则只需要知道 AA 和 AAM 的偏移量。同时也支持了区间查询。
• 可以压缩文件，将索引的每个 key 对应压缩块的开头

维护排序的结构在内存中更容易（如红黑树），利用这些数据结构，我们的存储引擎可以这样工作：数据写入时将其加到内存中的平衡树中，当树太大时，将其作为 SSTable 文件写入磁盘，同时后台可以对多个 SSTable 进行合并压缩。查询时先在内存数查找 key，再查找最新的文件段、次新文件段，以此类推。LevelDB、RocksDB、Tair LDB、HBase、Lucene 正是基于以上基本算法。

LSM 树

在哈希索引中，每个日志结构存储段都是一系列键值对。这些对按照它们写入的顺序出现，日志中稍后的值优先于日志中较早的相同键的值。除此之外，文件中键值对的顺序并不重要。现在我们可以对段文件的格式做一个简单的改变：我们要求键值对的序列按键排序。我们把这个格式称为排序字符串表（Sorted String Table），简称 SSTable。我们还要求每个键只在每个合并的段文件中出现一次（压缩过程已经保证）。与使用哈希索引的日志段相比，SSTable 有几个很大的优势：

首先，合并段是简单而高效的，即使文件大于可用内存。这种方法就像归并排序算法中使用的方法一样，如下图所示：您开始并排读取输入文件，查看每个文件中的第一个键，复制最低键（根据排序顺序）到输出文件，并重复。这产生一个新的合并段文件，也按键排序。

如果在几个段中出现相同的键，该怎么办？请记住，每个段都包含在一段时间内写入数据库的所有值。这意味着一个输入段中的所有值必须比另一个段中的所有值更新（假设我们总是合并相邻的段）。当多个段包含相同的键时，我们可以保留最近段的值，并丢弃旧段中的值。

其次，为了在文件中找到一个特定的键，你不再需要保存内存中所有键的索引。假设你正在内存中寻找键 handiwork，但是你不知道段文件中该关键字的确切偏移量。然而，你知道 handbag 和 handsome 的偏移，而且由于排序特性，你知道 handiwork 必须出现在这两者之间。这意味着您可以跳到 handbag 的偏移位置并从那里扫描，直到您找到 handiwork（或没找到，如果该文件中没有该键）。

您仍然需要一个内存中索引来告诉您一些键的偏移量，但它可能很稀疏：每几千字节的段文件就有一个键就足够了，因为几千字节可以很快被扫描。由于读取请求无论如何都需要扫描所请求范围内的多个键值对，因此可以将这些记录分组到块中，并在将其写入磁盘之前对其进行压缩。稀疏内存中索引的每个条目都指向压缩块的开始处。除了节省磁盘空间之外，压缩还可以减少 IO 带宽的使用。

构建和维护 SSTables

到目前为止，但是如何让你的数据首先被按键排序呢？我们的传入写入可以以任何顺序发生。在磁盘上维护有序结构是可能的，但在内存保存则要容易得多。有许多可以使用的众所周知的树形数据结构，例如红黑树或 AVL 树。使用这些数据结构，您可以按任何顺序插入键，并按排序顺序读取它们。

现在我们可以使我们的存储引擎工作如下：

• 写入时，将其添加到内存中的平衡树数据结构（例如，红黑树）。这个内存树有时被称为内存表（memtable）。
• 当内存表大于某个阈值（通常为几兆字节）时，将其作为 SSTable 文件写入磁盘。这可以高效地完成，因为树已经维护了按键排序的键值对。新的 SSTable 文件成为数据库的最新部分。当 SSTable 被写入磁盘时，写入可以继续到一个新的内存表实例。
• 为了提供读取请求，首先尝试在内存表中找到关键字，然后在最近的磁盘段中，然后在下一个较旧的段中找到该关键字。
• 有时会在后台运行合并和压缩过程以组合段文件并丢弃覆盖或删除的值。

这个方案效果很好。它只会遇到一个问题：如果数据库崩溃，则最近的写入（在内存表中，但尚未写入磁盘）将丢失。为了避免这个问题，我们可以在磁盘上保存一个单独的日志，每个写入都会立即被附加到磁盘上，就像在前一节中一样。该日志不是按排序顺序，但这并不重要，因为它的唯一目的是在崩溃后恢复内存表。每当内存表写出到 SSTable 时，相应的日志都可以被丢弃。

用 SSTables 制作 LSM 树

这里描述的算法本质上是 LevelDB 和 RocksDB 中使用的关键值存储引擎库，被设计嵌入到其他应用程序中。除此之外，LevelDB 可以在 Riak 中用作 Bitcask 的替代品。在 Cassandra 和 HBase 中使用了类似的存储引擎，这两种引擎都受到了 Google 的 Bigtable 文档（引入了 SSTable 和 memtable）的启发。

最初这种索引结构是由 Patrick O’Neil 等人描述的。在日志结构合并树（或 LSM 树）的基础上，建立在以前的工作上日志结构的文件系统。基于这种合并和压缩排序文件原理的存储引擎通常被称为 LSM 存储引擎。

Lucene 是 Elasticsearch 和 Solr 使用的一种全文搜索的索引引擎，它使用类似的方法来存储它的词典。全文索引比键值索引复杂得多，但是基于类似的想法：在搜索查询中给出一个单词，找到提及单词的所有文档（网页，产品描述等）。这是通过键值结构实现的，其中键是单词（关键词（term）），值是包含单词（文章列表）的所有文档的 ID 的列表。在 Lucene 中，从术语到发布列表的这种映射保存在 SSTable 类的有序文件中，根据需要在后台合并。

性能优化

与往常一样，大量的细节使得存储引擎在实践中表现良好。例如，当查找数据库中不存在的键时，LSM 树算法可能会很慢：您必须检查内存表，然后将这些段一直回到最老的（可能必须从磁盘读取每一个），然后才能确定键不存在。为了优化这种访问，存储引擎通常使用额外的 Bloom 过滤器（布隆过滤器是用于近似集合内容的内存高效数据结构，它可以告诉您数据库中是否出现键，从而为不存在的键节省许多不必要的磁盘读取操作。

还有不同的策略来确定 SSTables 如何被压缩和合并的顺序和时间。最常见的选择是大小分层压实 LevelDB 和 RocksDB 使用平坦压缩（LevelDB 因此得名），HBase 使用大小分层，Cassandra 同时支持。在规模级别的调整中，更新和更小的 SSTables 先后被合并到更老的和更大的 SSTable 中。在水平压实中，关键范围被拆分成更小的 SSTables，而较旧的数据被移动到单独的“水平”，这使得压缩能够更加递增地进行，并且使用更少的磁盘空间。

即使有许多微妙的东西，LSM 树的基本思想：保存一系列在后台合并的 SSTables：简单而有效。即使数据集比可用内存大得多，它仍能继续正常工作。由于数据按排序顺序存储，因此可以高效地执行范围查询（扫描所有高于某些最小值和最高值的所有键），并且因为磁盘写入是连续的，所以 LSM 树可以支持非常高的写入吞吐量。