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

Question

在设计数据密集型应用程序中，Martin引入了一种名为LSM-tree的数据结构。

主要有三个部分:内存备忘录(通常是红黑树)、内存中的稀疏索引和磁盘上的SSTables (又名段)。他们像这样一起工作：

• 当写发生时，它首先进入memtable，当它满时，所有的数据被刷新到一个新的段中(所有的键都被排序)。
• 当阅读发生时，它首先查找可记忆的内容。如果键不存在，它会查找稀疏索引，以了解键可能驻留在哪个部分。参见图1。
• 周期性地，压缩会将多个段合并成一个。参见图2。

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

​

​

Answer 1

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

仅仅通过查看索引就无法判断某个特定段是否包含特定的键。为了避免对每个段进行磁盘读取，常见的优化方法是为每个段提供一个布卢姆滤波器 (或类似的数据结构，如布库滤波器)，它总结了该段中包含的键。这允许读取操作只对那些实际包含所需键的段进行磁盘读取(由于Bloom筛选器误报而产生不必要的磁盘读取的可能性很小)。