我有点困惑。我找不到任何关于如何对排序字符串表执行范围查询的信息。
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(exclusive(中的所有内容。A"；"范围扫描"；只是找到第一个匹配的元素，然后迭代该层的文件。因此，您会发现File2是第一个包含任何匹配元素的，并扫描到以"ag"开头的第一个元素。您对File2进行迭代，然后查看File2的下一个文件(n:File3(。您检查它所包含的键范围，发现它包含了您感兴趣的范围中的更多元素，因此您对其进行迭代，直到找到以"d"开头的第一个条目。你在每一层都做同样的事情，除了第一层。第一层有一些文件，它们之间没有排序，但它们是内部排序的，所以您可以为每个文件保留一个迭代器。您还为当前的memtable保留了一个(在内存数据中，仅持久化在日志中(。
这永远不会变得太昂贵，因为第一层通常是在一个小的恒定阈值上压实的。由于每一层中的文件都经过了排序，并且文件也按照键进行了内部排序，因此您可以只推进最小的迭代器，直到所有迭代器都用完为止。除了初始搜索之外，每个步骤都必须查看固定数量的迭代器(假设是一种简单的方法(，因此是O(1(。大多数LSM使用块缓存，因此顺序读取通常在大部分时间都会命中缓存。
最后但同样重要的是，请注意，这主要是一个概念性的解释，因为大多数实现都有一些额外的技巧，可以提高这些事情的效率。在进行主要压缩(即，将N层合并到N+1层(时，您必须知道哪些数据包含在哪个文件范围中。即使是文件级操作也可能看起来很不一样：例如，RocksDB在每个文件的开头都保留一个带有键偏移量的粗略索引，以避免扫描文件中通常要大得多的键/值对部分。