我有点困惑。我找不到任何有关如何对排序字符串表执行范围查询的信息。
LevelDB 和 RocksDB 支持范围迭代器，允许您在范围之间进行查询，这对于 NoSQL 来说是完美的。我不明白的是它是如何实现高效的。
这些表在内存(和磁盘)中排序 - 什么算法或数据结构允许在范围查询中有效地查询排序字符串表？您是否只是循环遍历条目并依赖于充满数据的缓存行？
通常我会在前面放一个前缀树，这给了我键的索引。但我猜测排序字符串表会做一些不同的事情并以某种方式利用排序。
最佳答案
LSM 的每一层(第一层除外)在内部都是按键排序的，因此您可以在每一层中保留一个迭代器，并使用指向字典顺序最小元素的迭代器。图层的文件在磁盘上看起来像这样:
Layer N
---------------------------------------
File1 | File2 | File3 | ... | FileN <- filename
n:File2 |n:File3|n:File4| ... | <- next file
a-af | af-b | b-f | ... | w-z <- key range
---------------------------------------
aaron | alex | brian | ... | walter <- value omitted for brevity, but these are key:value records
abe | amy | emily | ... | xena
... | ... | ... | ... | ...
aezz | azir | erza | ... | zoidberg
---------------------------------------
First Layer (either 0 or 1)
---------------------------------------
File1 | File2 | ... | FileK
alex | amy | ... | andy
ben | chad | ... | dick
... | ... | ... | ...
xena | yen | ... | zane
---------------------------------------
...
假设您正在寻找 ag-d 范围内的所有内容(不包括)。 “范围扫描”只是找到第一个匹配的元素，然后迭代该层的文件。因此，您发现 File2 是第一个包含任何匹配元素的元素，并向上扫描到以“ag”开头的第一个元素。您迭代 File2，然后查看 File2 的下一个文件 (n:File3)。您检查它包含的键范围，发现它包含您感兴趣的范围中的更多元素，因此您对其进行迭代，直到找到以“d”开头的第一个条目。除了第一层之外，你在每一层都做同样的事情。第一层的文件彼此之间没有排序，但它们在内部排序，因此您可以为每个文件保留一个迭代器。您还可以为当前的内存表再保留一个(内存中的数据，仅保留在日志中)。
这永远不会变得太昂贵，因为第一层通常是在一个小的恒定阈值上压缩的。由于每一层中的文件都已排序，并且文件内部也按键排序，因此您可以只推进最小的迭代器，直到所有迭代器都用完为止。除了初始搜索之外，每个步骤都必须查看固定数量的迭代器(假设是简单的方法)，因此时间复杂度为 O(1)。大多数 LSM 采用 block 缓存，因此顺序读取通常大部分时间都会命中缓存。
最后但并非最不重要的一点是，请注意，这主要是概念性的解释，因为大多数实现都有一些额外的技巧，可以使这些事情变得更加高效。无论如何，当您进行主要压缩时，您必须知道哪些数据包含在哪些文件范围中，即将第 N 层合并到第 N + 1 层。甚至文件级操作也可能看起来完全不同:例如，RocksDB 维护一个粗索引与每个文件开头的键偏移量以避免扫描文件中通常更大的键/值对部分。
关于algorithm - 范围查询如何与排序字符串表一起使用？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/67219117/