LevelDB 有两个地方需要用到有序遍历：

1. 对外提供范围查询的接口（NewIterator）。
2. 内部的 Compaction。

通过前面的文章，我们了解到 LevelDB 的数据是保存在内部多个不同组件的，并且每个组件的数据格式都不一样。

LevelDB 通过在每一个组件上实现一套相同的迭代器接口来屏蔽掉每个组件的实现细节。

再通过这些迭代器的组合，提供完整的有序遍历能力。

Iterator

应用程序可以通过调用 leveldb::DB::NewIterator 来创建一个迭代器。

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

NewIterator 返回一个 leveldb::Iterator 指针，这个指针在使用之后需要 delete 掉。 Iterator 提供了和遍历数据相关的接口：

• SeekToFirst() – 定位到 leveldb 的第一个 key。
• SeekToLast() – 定位到 leveldb 的最后一个 key。
• Seek(target) – 定位到第一个大于等于 target 的 key。
• Next() – 定位到前一个 key。
• Prev() – 定位到后一个 key。
• Valid() – 判断当前迭代器是否还有效。每次使用迭代器之前都需要判断。
• key() – 迭代器当前指向的 key。
• value() – 迭代器当前指向的 value。
• status() – 迭代器当前的状态。一般当 Valid() 为 false，需要通过 status() 判断是结束了，还是出错了。

迭代器的组合

1. leveldb::DB::NewIterator 的实现是 leveldb::DBImpl::NewIterator，返回的对象是 DBIter。DBIter 将整个 LevelDB 的数据抽象成一个有序的 map。
2. DBIter 封装了 MergingIterator。MergingIterator 合并了 LevelDB 中的多个存储数据的组件的迭代器。
3. MemTableIterator：一个 MemTable 对应一个迭代器。
4. level0 的一个 SSTable 对应一个 TwoLevelIterator —— index block 的迭代器 + data block 的迭代器。
5. level1～n 一个 level 对应一个 TwoLevelIterator —— LevelFileNumIterator + TwoLevelIterator（index block 的迭代器 + data block 的迭代器）。

这里要注意，level0 的 TwoLevelIterator 和 level1~n 的 TwoLevelIterator 是不一样的。

MergingIterator

简单看下 MergingIterator 如何合并多个迭代器，实现有序遍历的。

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

Seek(target) 的作用是：定位到第一个大于等于 target 的 key。所以，需要将内部每个迭代器都定位到各自的第一个大于等于 target 的 key，再找出其中最小的，就是全局第一个大于等于 target 的 key。这个过程可能产生多次 I/O。

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

    // 简单起见，忽略掉 Forward <=> Backward 的转变...

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

current 就是指向当前目标值的迭代器。Next() 的作用是定位到下一个比 current 指向的目标大的 key。

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

    // 简单起见，忽略掉 Forward <=> Backward 的转变...

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

Prev() 的作用与 Next() 相反。

Next vs Prev

简单说：Prev 的性能比 Next 差。

因为 LevelDB 维护的有序数据是单向的。每次 Prev 都需要使用类似二分查找的方式定位数据；而 Next 基本上只需要取相邻的下一个值。

具体可以参考我以前写的一篇文章：leveldb iterator 的 Prev 究竟比 Next 差在哪？