LevelDB 完全解析(10):读操作之 Iterator

LevelDB 完全解析(10):读操作之 Iterator对外提供范围查询的接口(NewIterator)。 内部的 Compaction。 通过前面的文章,我们了解到 LevelDB 的数据是保存在内部多个不同组件的,并且每个组件的数据格式都不一样。 LevelDB 通过在每一个组件上实现一套相同的迭代器接口来屏蔽掉每个组件的实现细…

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() 判断是结束了,还是出错了。

迭代器的组合

LevelDB 完全解析(10):读操作之 Iterator

  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 差在哪?

今天的文章LevelDB 完全解析(10):读操作之 Iterator分享到此就结束了,感谢您的阅读。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:https://bianchenghao.cn/18913.html

(0)
编程小号编程小号

相关推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注