专栏首页linjinhe的专栏LevelDB 完全解析(10):读操作之 Iterator

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

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

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • LevelDB 完全解析(6):Filter

    LevelDB 可以设置通过 bloom filter 来减少不必要的读 I/O 次数。

    linjinhe
  • LevelDB 完全解析(3):SSTable

    SSTable 全称 Sorted String Table,顾名思义,里面的 key-value 都是有序保存的。除了两个 MemTable,LevelDB ...

    linjinhe
  • LevelDB 完全解析(8):读操作之 Get

    LevelDB 通过 leveldb::DB::Get 接口对外提供点查询的能力,具体的实现是 leveldb::DBImpl::Get。接口声明如下:

    linjinhe
  • 写爬虫,不会正则怎么行?

    很多人觉得正则很难,在我看来,这些人一定是没有用心。其实正则很简单,根据二八原则,我们只需要懂 20% 的内容就可以解决 80% 的问题了。我曾经有几年几乎每天...

    丹枫无迹
  • 正则表达式

    很多人觉得正则很难,在我看来,这些人一定是没有用心。其实正则很简单,根据二八原则,我们只需要懂 20% 的内容就可以解决 80% 的问题了。我曾经有几年几乎每天...

    Crossin先生
  • 【左神算法课】二维矩阵的子矩阵最大累加和

    xiaoxi666
  • 干货 | 每天上百万通话,携程电话系统性能测试实践

    作为全球领先的在线旅游企业,携程注重服务质量,并拥有全球最大的旅游呼叫中心,分别部署在国内自建系统、国内和国外第三方云服务平台上。呼叫中心每天承接着上百万通的通...

    携程技术
  • 申请软件著作权就不要忽视软件著作权登记的这几点深层次应用

    计算机软件著作权在一定程度上面有许多人们不知道它深层次的用处,最初听到它的名字有可能是在法律上,它更多的用处是在保护企业的合法权益。其实软件著作权的用处不仅是这...

    西安弈聪软件公司
  • 第188天:extend拷贝创建对象的原理

    半指温柔乐
  • 商业飞行时间仅为3分钟,无人驾驶的空中的士未来在哪里?

    据BBC报道,世界各地的科技公司正在为开发首款可行的空中的士而激烈竞争,不管是需要人类操作还是无人驾驶的。那么这些智能化的空中交通工具还需要多久才能翱翔在城市上...

    机器人网

扫码关注云+社区

领取腾讯云代金券