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

Question

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

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

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

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

Answer 1

RocksDB 有多种迭代器实现，如 Memtable 迭代器、文件迭代器、合并迭代器等。

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

请参阅有关迭代器实现的文档。