database - 如何维护 LSM 树中的稀疏索引？

Question

在Designing Data Intensive Applications中，Martin 介绍了一种称为 LSM-trees 的数据结构。

主要有 3 个部分：内存中的 memtable（通常是红黑树）、内存中的稀疏索引和磁盘上的 SSTable（又名段）。他们像这样一起工作：

• 当写入发生时，它首先进入内存表，当它变满时，所有数据都被刷新到一个新的段中（所有键都已排序）。

• 当发生读取时，它首先查找内存表。如果该键不存在，它会查找稀疏索引，以了解该键可能驻留在哪个段。见图 1。

• 定期地，压缩发生，将多个段合并为一个。见图 2。

从图 2 可以看出，键在段内排序，但键不在段之间排序。这让我想知道：我们如何保持索引中的稀疏索引 st 键具有增加的偏移量？

Answer 1

一种典型的方法是为每个段文件建立一个单独的索引，并且在段文件的压缩/合并期间重新生成该索引。当读取一个键时，我们必须检查可能包含该键的多个当前段文件，并返回出现在这些段中的最新段中的值。

仅通过查看索引无法判断特定段是否包含特定键。为了避免必须对每个段进行磁盘读取，一种常见的优化是为每个段使用一个Bloom 过滤器（或类似的数据结构，例如Cuckoo 过滤器），该过滤器总结了该段中包含的键。这允许读取操作仅对实际包含所需键的那些段进行磁盘读取（由于布隆过滤器误报而进行不必要的磁盘读取的可能性很小）。