如何使用迭代器跳过一些键?

Question

例如，我向数据库添加了几个键，就像 ，

<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
}

Answer 1

如帖子中所述，您正在链接跳过扫描的工作原理是在假设键按顺序存储的情况下查看键前缀。如果您正在寻找 小于 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，一定要做一个查找。您正在谈论的优化适用于键上的谓词，否则您必须计算表中每个键的谓词。因此，在这种情况下跳过键是一种优化，因为您必须减少计算谓词的频率，并且摆脱廉价的谓词比较。