术语 SSTable 和 LSM Tree 之间有什么区别
Kak*_*you 15 database indexing lsm-tree
这两个术语可以互换使用吗？
我已经阅读了关于 SSTable 是如何工作的，通常，文章只是开始提到 LSM 树。然而，它们似乎是同一回事。
我什么时候应该使用一个术语而不是另一个？
mad*_*ead 47
Martin Kleppmann在他的《设计数据密集型应用程序》一书中对 SSTables 和 LSM-Trees 进行了最好的解释，这可能是对凡人来说最好的解释之一。这些数据结构在第 3 章“存储和检索”第 69 至 79 页中进行了解释。这真是一本很棒的读物，我会推荐整本书！
\n不耐烦的人可以在下面找到我的主题概要
\n\n
一切都从一个非常愚蠢的键值数据库开始，它仅由两个 Bash 函数实现：
\ndb_set () {\n echo "$1,$2" >> database\n}\n\ndb_get () {\n grep "^$1," database | sed -e "s/^$1,//" | tail -n 1\n}\n这个想法是将数据存储在类似 CSV 的文件中：
\n$ source database.sh\n\n$ db_set 1 \'Anakin Skywalker\'\n$ db_set 2 \'Luke Skywalker\'\n$ db_set 1 \'Darth Vader\'\n\n$ cat database\n1,Anakin Skywalker\n2,Luke Skywalker\n1,Darth Vader\n\n$ db_get 1\nDarth Vader\n请注意，该键的第一个值1将被后续写入覆盖。
该数据库具有相当好的写入性能：db_set只需将数据附加到文件中，通常速度很快。但读取效率低下，尤其是在巨大的数据集上：db_get扫描整个文件。因此，写入为 O(1)，读取为 O(n)。
接下来介绍指数。索引是从数据本身派生的数据结构。维护索引总是会产生额外的成本，因此，索引总是会降低写入性能，但会提高读取性能。
\n最简单的索引之一是哈希索引。该索引只不过是一个字典，保存数据库中记录的字节偏移量。继续前面的示例，假设每个字符都是一个字节，则哈希索引将如下所示：
\n
每当将数据写入数据库时，也会更新索引。当您想要读取给定键的值时，您可以快速查找数据库文件中的偏移量。有了偏移量，您可以使用“查找”操作直接跳转到数据位置。根据特定的索引实现，您可能会期望读取和写入的复杂度为对数。
\n接下来，马丁讨论存储效率。将数据附加到数据库文件会很快耗尽磁盘空间。\xe2\x80\x94 的不同键越少，这种仅附加存储引擎的效率就越低。解决这个问题的方法是压缩：
\n
当数据库文件增长到一定大小时，您将停止向其追加内容，创建一个新文件（称为段）并将所有写入重定向到此新文件。
\n段是不可变的，因为它们永远不会用于附加任何新数据。修改段的唯一方法是将其内容写入新文件，中间可能进行一些转换。
\n因此，压缩会创建仅包含每个键的最新记录的新段。此步骤的另一种可能的增强功能是将多个片段合并为一个片段。当然，压缩和合并可以在后台完成。旧的片段就被扔掉了。
\n每个段（包括正在写入的段）都有自己的索引。因此，当您想要查找给定键的值时，您可以按相反的时间顺序搜索这些索引：从最新到最旧。
\n到目前为止，我们的数据结构具有以下优点：
\n\xe2\x9c\x94\xef\xb8\x8f 顺序写入通常比随机写入更快
\n\xe2\x9c\x94\xef\xb8\x8f 单个写入进程很容易控制并发性
\n\xe2\x9c \x94\xef\xb8\x8f 崩溃恢复很容易实现：只需顺序读取所有段，并将偏移量存储在内存索引中
\n\xe2\x9c\x94\xef\xb8\x8f 合并和压缩帮助以避免数据碎片
但是，也存在一些限制：
\n\xe2\x9d\x97 如果段很大并且数量众多，则崩溃恢复可能会非常耗时
\n\xe2\x9d\x97 哈希索引必须适合内存。实现磁盘哈希表要困难得多
\n\xe2\x9d\x97 范围查询 ( BETWEEN) 实际上是不可能的
\n
现在，有了这个背景，让我们转向 SSTable 和 LSM 树。顺便说一句，这些缩写相应地表示“排序字符串表”和“日志结构合并树”。
\nSSTables 与我们之前看到的“数据库”非常相似。唯一的改进是我们要求段中的记录按键排序。这似乎破坏了使用仅追加写入的能力，但这就是 LSM-Tree 的用途。我们一会儿就会看到！
\n与我们之前的那些简单段相比，SSTable 具有一些优势：
\n\xe2\x9c\x94\xef\xb8\x8f 由于记录已预先排序，合并段的效率更高。您所要做的就是在每次迭代中比较分段“头”并选择最低的一个。如果多个段包含相同的键，则最新段中的值获胜。这个紧凑和合并过程还保存键的排序。
\n
\xe2\x9c\x94\xef\xb8\x8f 通过对键进行排序，您不再需要在索引中包含每个键。如果已知钥匙B位于钥匙之间的某个位置A，C您只需进行扫描即可。这也意味着范围查询是可能的！
最后一个问题是：如何获得按键排序的数据？
\nPatrick O\xe2\x80\x99Neil 等人描述了这个想法。在他们的“The Log-Structured Merge-Tree (LSM-Tree)”中，很简单：内存中的数据结构，例如红黑树或AVL树，擅长对数据进行排序。因此，您将写入分为两个阶段。首先，将数据写入内存中的平衡树。其次，将树刷新到磁盘上。实际上，可能有两个以上的阶段，更深的阶段比上层更大且“更慢”（如另一个答案所示）。
\n- \n
- 当写入到来时，您将其添加到内存中的平衡树中，称为 memtable。 \n
- 当memtable变大时，它会被刷新到磁盘。它已经排序了，所以它自然会创建一个 SSTable 段。 \n
- 同时，写入由新的内存表处理。 \n
- 读取首先在内存表中查找，然后在段中查找，从最近的到最旧的。 \n
- 如前所述，片段会在后台不时被压缩和合并。 \n
该方案并不完美，它可能会突然崩溃：内存表作为内存中的数据结构会丢失。这个问题可以通过维护另一个仅附加文件来解决，该文件基本上复制了内存表的内容。数据库只需要在崩溃后读取它即可重新创建内存表。
\n就是这样！请注意，上面描述的简单仅附加存储的所有问题现在都已解决：
\n\xe2\x9c\x94\xef\xb8\x8f 现在在崩溃的情况下只有一个文件可供读取：memtable 备份
\n\xe2\x9c\x94\xef\xb8\x8f 索引可能是稀疏的，因此安装 RAM 更容易
\n\xe2\x9c\x94\xef\xb8\x8f 现在可以进行范围查询
\n
TLDR：SSTable 是一种键排序的仅附加键值存储。LSM 树是一种基于平衡树的分层数据结构，它允许 SSTable 存在，而不会同时存在排序和仅附加的争议。
\n\n
恭喜，您已经读完这篇长文！如果您喜欢这个解释，请确保不仅支持这篇文章，还支持这里马丁的一些答案。请记住：所有功劳都归他所有！
\n- 好答案！我只是想说，我觉得 DDIA 对 LSM 的解释没有你的清楚。它解释了什么是LSM，但没有使用LSM这个术语，然后在后面的部分中，说我们刚才讲的是LSM。我很困惑它指的是哪一部分。 (4认同)
- 但是……首先：OP从未问过这个问题。第二：我的空间、时间和常识都有限。做出超全面的答案不是我的目标。而且：这是不可能的。因为，这是第三点：格式是特定于技术的，而我（我猜马丁的）想法是传达原则，而不是实现细节。谢谢您的链接，顺便说一句，这是一个非常好的补充！ (2认同)
排序字符串表（SSTable）是一个基于键/值字符串对的文件，按键排序。
然而，LSM Tree 不同：
在计算机科学中，日志结构合并树（或 LSM 树）是一种具有性能特征的数据结构，使其对于提供对具有高插入量的文件（例如事务日志数据）的索引访问具有吸引力。LSM 树与其他搜索树一样，维护键值对。LSM树以两个或多个独立的结构维护数据，每个结构都针对其各自的底层存储介质进行了优化；数据在两个结构之间高效、批量同步。
https://en.wikipedia.org/wiki/Log-structed_merge-tree
- 因此，如果我们在 SSTable 中添加压缩和合并，我们将得到一个 LSM Tree。这是对的吗？ (5认同)
它在基于 LSM 的存储技术中有很好的解释：第 1 节和 2.2.1 中的调查论文
LSM-tree由一些内存组件和一些磁盘组件组成。基本上，SSTable只是 LSM-tree 磁盘组件的一种实现。
上面提到的论文解释了SSTable：
一个SSTable（Sorted String Table）包含一个数据块列表和一个索引块；一个数据块存储按键排序的键值对，索引块存储所有数据块的键范围。
- https://arxiv.org/pdf/1812.07527.pdf (2认同)