LevelDB requires ordered traversal in two places:

  1. Provides an interface for range query (NewIterator).
  2. An internal Compaction.

From previous articles, we learned that LevelDB’s data is stored internally in several different components, each of which has a different data format.

LevelDB shields each component from implementation details by implementing the same set of iterator interfaces on each component.

The combination of these iterators provides complete ordered traversal capability.

Iterator

An application can create an iterator by calling Leveldb ::DB::NewIterator.

 virtual Iterator* NewIterator(const ReadOptions& options) = 0;
Copy the code

NewIterator returns a Leveldb ::Iterator pointer that needs to be deleted after use. Iterator provides interfaces for iterating through data:

  • SeekToFirst() – Locate the first key to LevelDB.
  • SeekToLast() – Locate the last key to LevelDB.
  • Seek(target) – Locate the first key that is greater than or equal to target.
  • Next() – Locates the previous key.
  • Prev() – Locate to the latter key.
  • Valid() – Determines whether the current iterator is still Valid. We need to judge each time we use an iterator.
  • Key () – The key to which the iterator is currently pointing.
  • Value () – The value to which the iterator is currently pointing.
  • Status () – The current state of the iterator. When Valid() is false, you need status() to determine whether it is finished or an error.

Combination of iterators

  1. Leveldb: : DB: : NewIterator implementation is leveldb: : DBImpl: : NewIterator, the object returned is DBIter. DBIter abstracts the entire LevelDB data into an ordered map.
  2. DBIter encapsulates MergingIterator. MergingIterator merges iterators for multiple components in LevelDB that store data.
  3. MemTableIterator: One MemTable corresponds to one iterator.
  4. Level0 an SSTable corresponds to a TwoLevelIterator — an iterator of the index block + an iterator of the data block.
  5. Level1 ~ n A level corresponds to a TwoLevelIterator — LevelFileNumIterator + TwoLevelIterator (iterator of index block + iterator of data block).

Note that the TwoLevelIterator at Level0 is different from the TwoLevelIterator at Level1 ~n.

MergingIterator

Take a quick look at how MergingIterator merges multiple iterators to achieve ordered traversal.

  virtual void Seek(const Slice& target) {
    for (int i = 0; i < n_; i++) {
      children_[i].Seek(target);
    }
    FindSmallest();
    direction_ = kForward;
  }
Copy the code

Seek(target) is used to locate the first key whose value is greater than or equal to target. Therefore, we need to locate each internal iterator to the first key that is greater than or equal to target, and then find the smallest one, which is the first global key that is greater than or equal to target. This process can produce multiple I/ OS.

virtual void Next(a) {
    assert(Valid());

    // For simplicity, ignore the transform with Forward <=> Backward...

    current_->Next();
    FindSmallest();
}

Copy the code

Current is an iterator to the current target value. Next() is used to locate the Next key that is larger than the target that current points to.

virtual void Prev(a) {
    assert(Valid());

    // For simplicity, ignore the transform with Forward <=> Backward...

    current_->Prev();
    FindLargest();
}

Copy the code

Prev() does the opposite of Next().

Next vs Prev

Simply put: Prev performs worse than Next.

Because LevelDB maintains ordered data that is one-way. Each Prev needs to locate the data in a manner similar to binary lookup; Next basically just takes the Next adjacent value.

How is Leveldb Iterator’s Prev worse than Next’s?