LevelDB 有兩個地方需要用到有序遍歷：

1. 對外提供范圍查詢的接口（NewIterator）。
2. 內(nèi)部的 Compaction。

通過前面的文章，我們了解到 LevelDB 的數(shù)據(jù)是保存在內(nèi)部多個不同組件的，并且每個組件的數(shù)據(jù)格式都不一樣。

LevelDB 通過在每一個組件上實現(xiàn)一套相同的迭代器接口來屏蔽掉每個組件的實現(xiàn)細節(jié)。

再通過這些迭代器的組合，提供完整的有序遍歷能力。

Iterator

應(yīng)用程序可以通過調(diào)用 leveldb::DB::NewIterator 來創(chuàng)建一個迭代器。

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

NewIterator 返回一個 leveldb::Iterator 指針，這個指針在使用之后需要 delete 掉。
Iterator 提供了和遍歷數(shù)據(jù)相關(guān)的接口：

• SeekToFirst() - 定位到 leveldb 的第一個 key。
• SeekToLast() - 定位到 leveldb 的最后一個 key。
• Seek(target) - 定位到第一個大于等于 target 的 key。
• Next() - 定位到前一個 key。
• Prev() - 定位到后一個 key。
• Valid() - 判斷當前迭代器是否還有效。每次使用迭代器之前都需要判斷。
• key() - 迭代器當前指向的 key。
• value() - 迭代器當前指向的 value。
• status() - 迭代器當前的狀態(tài)。一般當 Valid() 為 false，需要通過 status() 判斷是結(jié)束了，還是出錯了。

迭代器的組合

1. leveldb::DB::NewIterator 的實現(xiàn)是 leveldb::DBImpl::NewIterator，返回的對象是 DBIter。DBIter 將整個 LevelDB 的數(shù)據(jù)抽象成一個有序的 map。
2. DBIter 封裝了 MergingIterator。MergingIterator 合并了 LevelDB 中的多個存儲數(shù)據(jù)的組件的迭代器。
3. MemTableIterator：一個 MemTable 對應(yīng)一個迭代器。
4. level0 的一個 SSTable 對應(yīng)一個 TwoLevelIterator —— index block 的迭代器 + data block 的迭代器。
5. level1～n 一個 level 對應(yīng)一個 TwoLevelIterator —— LevelFileNumIterator + TwoLevelIterator（index block 的迭代器 + data block 的迭代器）。

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

MergingIterator

簡單看下 MergingIterator 如何合并多個迭代器，實現(xiàn)有序遍歷的。

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

Seek(target) 的作用是：定位到第一個大于等于 target 的 key。所以，需要將內(nèi)部每個迭代器都定位到各自的第一個大于等于 target 的 key，再找出其中最小的，就是全局第一個大于等于 target 的 key。這個過程可能產(chǎn)生多次 I/O。

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

    // 簡單起見，忽略掉 Forward <=> Backward 的轉(zhuǎn)變...

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

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

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

    // 簡單起見，忽略掉 Forward <=> Backward 的轉(zhuǎn)變...

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

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

Next vs Prev

簡單說：Prev 的性能比 Next 差。

因為 LevelDB 維護的有序數(shù)據(jù)是單向的。每次 Prev 都需要使用類似二分查找的方式定位數(shù)據(jù)；而 Next 基本上只需要取相鄰的下一個值。

具體可以參考我以前寫的一篇文章：leveldb iterator 的 Prev 究竟比 Next 差在哪？