Как пропустить некоторые ключи с помощью итератора?

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, определенно сделайте поиск. Оптимизация, о которой вы говорите, применима к предикатам на ключах, для которых вам в противном случае придется оценивать предикат для каждого ключа в таблице. Следовательно, пропуск ключей является оптимизацией в этом случае, потому что вы должны оценивать предикат реже и обходиться без дешевого сравнения предикатов.