LevelDB: Implementing an iterator to enumerate by key prefix

Question

I am looking for an efficient way to implement a key enumerator using leveldb to iterate by a key-prefix. The key is byte array (and the db uses default byte array comparer, so all keys with specific prefix stored/retrieved sequentially), and I would like my iterator to be able to take a key prefix and return only the data with keys having that prefix.

Do I have to use or inherit the default db iterator, seek to the first key in the range (ofcourse I need to know what it is), and then verify and return every slice that starts with the prefix (by overriding the movenext or something)? or is there a more efficient way of implementing this?

Let me know if anybody has solved this already and can share the code or the general idea. I am trying this from C++/CLI, but implementation in any language would help.

Thanks. -raj.

Answer 1

The comparator is used to determine if the keys are different, so overloading it wouldn't help because as you're scanning the database- you have to be able to compare the full keys (not just the prefixes). Overloading the iterator is not necessary: the keys are ordered in leveldb, you would know that if you encounter a key with a different prefix, it will already be out of the range. You can just use the iterator as you normally would and as long as your keys are evaluated properly, you should get the right results:

void ScanRecordRange(const leveldb::Slice& startSlice, const leveldb::Slice& endSlice)
{
    // Get a database iterator
    shared_ptr<leveldb::Iterator> dbIter(_database->NewIterator(leveldb::ReadOptions()));

    // Possible optimization suggested by Google engineers 
    // for critical loops. Reduces memory thrash.
    for(dbIter->Seek(startSlice); dbIter->Valid() && _options.comparator->Compare(dbIter->key(), endSlice)<=0 ;dbIter->Next())
    {                
        // Read the record
        if( !dbIter->value().empty() )
        {
            leveldb::Slice keySlice(dbIter->key());
            leveldb::Slice dataSlice(dbIter->data());
            // TODO: process the key/data

        }
    }
}

Answer 2

I have a prefix iterator in my LevelDB wrapper.
It is used in the range returned by startsWith method:

int count = 0;
for (auto& en: ldb.startsWith (std::string ("prefix"))) {++count;}