范围查询如何在 LSM（日志结构合并树）上工作？

Question

最近我一直在研究数据库中常见的索引结构，比如 B+-trees 和 LSM。我对点读/写/删除/压缩如何在 LSM 中工作有一个可靠的处理。

例如（在 RocksDB/levelDB 中），在点查询读取时，我们将首先检查内存索引（memtable），然后是从最近到最近的一些 SST 文件。在 LSM 的每个级别上，我们将使用二分搜索来帮助加快查找给定密钥的每个 SST 文件的速度。对于给定的 SST 文件，我们可以使用布隆过滤器快速检查密钥是否存在，从而节省更多时间。

我没有看到范围读取具体是如何工作的。LSM 是否必须在每个 SST 级别（包括 memtable）上打开一个迭代器，并在所有级别上同步迭代，以返回最终的排序结果？它是否仅作为一系列点查询实现（几乎绝对不是）。是否先拉出所有潜在的键，然后再排序？希望有人在这里有任何见解。

我无法找到有关该主题的太多文档，任何见解在这里都会有所帮助。

Answer 1

RocksDB 有多种迭代器实现，如 Memtable Iterator、File Iterator、Merging Iterator 等。

在范围读取期间，迭代器将使用SeekTo()call寻找类似于点查找（在 SST 中使用二进制搜索）的起始范围。在寻找开始范围后，将为每个内存表创建一个迭代器，为每个 0 级文件创建一个迭代器（因为 L0 中 SST 的重叠性质），稍后为每个级别创建一个迭代器。合并迭代器将从这些迭代器中的每一个收集键，并按排序顺序提供数据，直到达到 End 范围。

请参阅本上迭代器实现文档。