如何维护 LSM 树中的稀疏索引？
How to maintain the sparse index in a LSM-tree?
在Designing Data Intensive Applications中，Martin介绍了一种叫做LSM-trees的数据结构。
主要有 3 个部分：内存中的内存表（通常是红黑树）、内存中的稀疏索引和磁盘上的 SSTables（也称为段）。他们像这样一起工作：
当写入发生时，它首先进入内存表，当它变满时，所有数据都被刷新到一个新的段中（所有键都排序）。
当读取发生时，它首先查找内存表。如果密钥不存在，它会查找稀疏索引，以了解密钥可能位于哪个段。见图一
定期进行压缩，将多个段合并为一个段。见图2。
从图 2 可以看出，键在 段内 排序，但是键 未 排序 在 段之间。这让我想知道：我们如何维护稀疏索引 s.t。索引中的键具有递增的偏移量？
一种典型的方法是为每个段文件创建一个单独的索引，并且在 compaction/merging 段文件期间重新生成该索引。当读取一个键时，我们必须检查可能包含该键的多个当前段文件，以及 return 这些段中最近出现的值。
仅通过查看索引无法判断特定段是否包含特定键。为了避免必须为每个段执行磁盘读取，一个常见的优化是为每个段设置一个 Bloom filter (or similar data structure such as a Cuckoo filter) 来汇总该段中包含的键。这允许读取操作仅对实际包含所需密钥的那些段进行磁盘读取（由于 Bloom 过滤器误报而进行不必要的磁盘读取的可能性很小）。
在Designing Data Intensive Applications中，Martin介绍了一种叫做LSM-trees的数据结构。
主要有 3 个部分：内存中的内存表（通常是红黑树）、内存中的稀疏索引和磁盘上的 SSTables（也称为段）。他们像这样一起工作：
当写入发生时，它首先进入内存表，当它变满时，所有数据都被刷新到一个新的段中（所有键都排序）。
当读取发生时，它首先查找内存表。如果密钥不存在，它会查找稀疏索引，以了解密钥可能位于哪个段。见图一
定期进行压缩，将多个段合并为一个段。见图2。
从图 2 可以看出，键在 段内 排序，但是键 未 排序 在 段之间。这让我想知道：我们如何维护稀疏索引 s.t。索引中的键具有递增的偏移量？
一种典型的方法是为每个段文件创建一个单独的索引，并且在 compaction/merging 段文件期间重新生成该索引。当读取一个键时，我们必须检查可能包含该键的多个当前段文件，以及 return 这些段中最近出现的值。
仅通过查看索引无法判断特定段是否包含特定键。为了避免必须为每个段执行磁盘读取，一个常见的优化是为每个段设置一个 Bloom filter (or similar data structure such as a Cuckoo filter) 来汇总该段中包含的键。这允许读取操作仅对实际包含所需密钥的那些段进行磁盘读取（由于 Bloom 过滤器误报而进行不必要的磁盘读取的可能性很小）。