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

Question

在设计数据密集型应用程序中，Martin 介绍了一种称为 LSM 树的数据结构。

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

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

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

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

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

Answer 1

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

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