1

例如，我向 DB 添加了几个键，例如，

<1 + 2> 
<1 + 3>
<2 + 1>
<2 + 4>
<3 + 2>

首先Seek()到 <1, 2> 然后Next()到 <1, 3> 之后，我想跳过键 <2, 1> 和 <2, 4> （它们的前缀都是2）并将迭代器移动到 <3, 2>无需新seek操作。使用新Seek()操作是出乎意料的，因为它Seek()是昂贵的。我应该使用哪种方法？

这种跳过扫描方法与此类似

我更喜欢像下面这样编程：

DBIter* it = NewDBIterator(...);
set = {key1, key2, key3, ...};
Iterator key_iter = set.begin();
for (it->SeekToFirst(); it->Valid() && key_iter != set.end(); it->SkipToNext(*key_iter), ++ key_iter) {
  // do something
}
4

1 回答 1

0

如帖子中所述，您通过在密钥按顺序存储的假设下查看密钥前缀来链接跳过扫描。如果您正在寻找小于 3 的第二个关键部分的任何值：

1,2
1,3
1,4
2,1
2,2
2,3
...

当您达到 1,3 时，您知道将不再有与您的谓词匹配且具有键前缀 1 的键，因此您可以跳到下一个键前缀。这通常仍然意味着您必须在查找下一个前缀的过程中至少查看每个键前缀，或者以某种方式查找它。这是否好取决于。对于一组不同的键的操作，单独查找几乎肯定是更好的选择，因为除非你非常清楚你的数据是什么样的，否则你不知道你必须前缀扫描的键的数量，你可能有查看每一个 (O(n))，其中 k 次查找只需要 O(k) * O(log(n)) 时间。所以只要k << n，一定要查。您正在谈论的优化适用于键上的谓词，否则，您将不得不评估表中每个键的谓词。因此，在这种情况下，跳过键是一种优化，因为您必须不那么频繁地评估谓词，并且可以使用廉价的谓词比较。

于 2019-08-20T23:50:08.230 回答