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

Question

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

主要有 3 个部分:内存中的内存表(通常是红黑树)、内存中的稀疏索引和磁盘上的 SSTables(也称为段)。他们像这样一起工作:

• 当写入发生时，它首先进入 memtable，当它变满时，所有数据都被刷新到一个新段中(所有键都已排序)。

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

• 定期进行压缩，将多个段合并为一个段。见图2。

从图 2 中可以看出，键在段内 排序，但是键不在段之间 排序。这让我想知道:我们如何维护稀疏索引 s.t.索引中的键具有递增的偏移量？

Answer 1

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

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