对于凡人来说，SSTables 和 LSM-Trees 的最佳解释之一可能是马丁·克莱普曼 https://stackoverflow.com/users/121436 in his 《设计数据密集型应用程序》 https://dataintensive.net书。这些数据结构在第 3 章“存储和检索”第 69 至 79 页中进行了解释。这真是一本很棒的读物，我会推荐整本书！
不耐烦的人可以在下面找到我的主题概要????
一切都从一个非常愚蠢的键值数据库开始，它仅由两个 Bash 函数实现：
db_set () {
echo "$1,$2" >> database
}
db_get () {
grep "^$1," database | sed -e "s/^$1,//" | tail -n 1
}
这个想法是将数据存储在类似 CSV 的文件中：
$ source database.sh
$ db_set 1 'Anakin Skywalker'
$ db_set 2 'Luke Skywalker'
$ db_set 1 'Darth Vader'
$ cat database
1,Anakin Skywalker
2,Luke Skywalker
1,Darth Vader
$ db_get 1
Darth Vader
请注意，该键的第一个值1被后续写入覆盖。
该数据库具有相当好的写入性能：db_set只是将数据附加到文件中，这通常很快。但读取效率低下，尤其是在巨大的数据集上：db_get扫描整个文件。因此，写入为 O(1)，读取为 O(n)。
接下来介绍指数。索引是从数据本身派生的数据结构。维护索引总是会产生额外的成本，因此，索引总是会降低写入性能，但会提高读取性能。
最简单的索引之一是哈希索引。该索引只不过是一个字典，保存数据库中记录的字节偏移量。继续前面的示例，假设每个字符都是一个字节，则哈希索引将如下所示：
每当将数据写入数据库时，也会更新索引。当您想要读取给定键的值时，您可以快速查找数据库文件中的偏移量。有了偏移量，您可以使用“查找”操作直接跳转到数据位置。根据特定的索引实现，您可能会期望读取和写入的复杂度为对数。
接下来，马丁讨论存储效率。将数据附加到数据库文件会很快耗尽磁盘空间。拥有的不同键越少，这种仅附加存储引擎的效率就越低。解决这个问题的方法是压缩：
当数据库文件增长到一定大小时，您将停止向其追加内容，创建一个新文件（称为段）并将所有写入重定向到该新文件。
段是不可变的，因为它们永远不会用于附加任何新数据。修改段的唯一方法是将其内容写入新文件，中间可能进行一些转换。
因此，压缩会创建仅包含每个键的最新记录的新段。此步骤的另一种可能的增强功能是将多个片段合并为一个片段。当然，压缩和合并可以在后台完成。旧的片段就被扔掉了。
每个段（包括正在写入的段）都有自己的索引。因此，当您想要查找给定键的值时，您可以按相反的时间顺序搜索这些索引：从最新到最旧。
到目前为止，我们的数据结构具有以下优点：
✔️ 顺序写入通常比随机写入快
✔️ 使用单个编写器进程可以轻松控制并发性
✔️ 崩溃恢复很容易实现：只需顺序读取所有段，并将偏移量存储在内存索引中
✔️ 合并和压缩有助于避免数据碎片
但是，也存在一些限制：
❗ 如果段很大且数量众多，则崩溃恢复可能会非常耗时
❗ 哈希索引必须适合内存。实现磁盘上的哈希表要困难得多
❗ 范围查询（BETWEEN）几乎是不可能的
现在，有了这个背景，让我们转向 SSTable 和 LSM 树。顺便说一句，这些缩写相应地表示“排序字符串表”和“日志结构合并树”。
SSTables 与我们之前看到的“数据库”非常相似。唯一的改进是我们要求段中的记录按键排序。这似乎破坏了使用仅附加写入的能力，但这就是 LSM-Tree 的用途。我们一会儿就会看到！
与我们之前的那些简单段相比，SSTable 具有一些优势：
✔️ 由于记录已预先排序，合并段的效率更高。您所要做的就是在每次迭代中比较分段“头”并选择最低的一个。如果多个段包含相同的键，则最新段中的值获胜。这个紧凑和合并过程还保存键的排序。
✔️ 通过对键进行排序，您不再需要在索引中包含每个键。如果钥匙B已知位于键之间的某个位置A and C你可以做一个扫描。这也意味着范围查询是可能的！
最后一个问题是：如何获得按键排序的数据？
帕特里克·奥尼尔等人描述了这个想法。在他们的“日志结构合并树（LSM-Tree）” https://www.cs.umb.edu/%7Eponeil/lsmtree.pdf很简单：内存中有一些数据结构，例如红黑树或AVL树，它们擅长对数据进行排序。因此，您将写入分为两个阶段。首先，将数据写入内存中的平衡树。其次，将树刷新到磁盘上。实际上，可能有两个以上的阶段，较深的阶段比上层更大且“慢”（如在另一个答案中显示 https://stackoverflow.com/a/58169581/750510).
- 当写入到来时，您将其添加到内存中的平衡树中，称为 memtable。
- 当memtable变大时，它会被刷新到磁盘。它已经排序了，所以它自然会创建一个 SSTable 段。
- 同时，写入由新的内存表处理。
- 读取首先在内存表中查找，然后在段中查找，从最近的到最旧的。
- 如前所述，片段会在后台不时被压缩和合并。
该方案并不完美，它可能会突然崩溃：内存表作为内存中的数据结构会丢失。这个问题可以通过维护另一个仅附加文件来解决，该文件基本上复制了内存表的内容。数据库只需要在崩溃后读取它即可重新创建内存表。
就是这样！请注意，上面描述的简单仅附加存储的所有问题现在都已解决：
✔️ 现在在崩溃的情况下只有一个文件可供读取：memtable 备份
✔️ 索引可能很稀疏，因此更容易安装 RAM
✔️ 现在可以进行范围查询
TLDR：SSTable 是一种键排序的仅附加键值存储。 LSM 树是一种基于平衡树的分层数据结构，它允许 SSTable 存在，而不会同时存在排序和仅附加的争议。
恭喜，您已经读完了这篇长文！如果您喜欢这个解释，请确保不仅支持这篇文章，还支持一些马丁的答案在这里 https://stackoverflow.com/users/121436/martin-kleppmann?tab=answers以及。请记住：所有功劳都归他所有！
