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

Question

最近，我一直在研究数据库中的常见索引结构，例如B+树和LSM。我对点读取/写入/删除/压缩如何在LSM中工作有一个可靠的句柄。

例如(在RocksDB/levelDB中)，在点查询读取时，我们将首先检查内存中的索引(memtable)，然后检查一定数量的SST文件(从最近到最近)。在LSM的每个级别上，我们将使用二进制搜索来帮助加速查找给定关键字的每个SST文件。对于给定的SST文件，我们可以使用bloom filters来快速检查密钥是否存在，从而节省了我们的时间。

我不明白的是range read具体是如何工作的。LSM是否必须在每个SST级别(包括内存表)上打开迭代器，并在所有级别上锁步迭代，以返回最终的排序结果？它只是作为一系列点查询实现的吗(几乎肯定不是)。是否所有的潜在关键字都是先拉取，然后再排序？会很感激这里任何人的洞察力。

我还没有找到很多关于这个主题的文档，任何见解都会对我有所帮助。

Answer 1

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

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

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