专栏首页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 完全解析(8):读操作之 Get

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

    linjinhe
  • LevelDB 完全解析(9):写操作

    以上,便是 LevelDB 的写入流程。写入队列 + 合并写操作,逻辑和代码都十分简洁。比较不足的是,整个写入过程都是单线程的。

    linjinhe
  • LevelDB原理解析:数据的读写与合并是怎样发生的?

    导语 | LevelDB是一款十分优秀的存储引擎,具有极高的数据读写性能,尤其是写入性能,在笔者经历的多个项目中都有用到,因此本文打算结合LevelDB的部分源...

    腾小云
  • 漫谈 LevelDB 数据结构(一):跳表(Skip List)

    早对 LevelDB 有所耳闻,这次心血来潮结合一些资料粗略过了遍代码,果然名不虚传 —— 绝对是不世出的工艺品!如果你对存储感兴趣、如果你想优雅使用 C++、...

    青藤木鸟
  • SSTable 介绍

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。

    狼啸风云
  • Leveldb 源码类功能解析

    Leveldb 的基本介绍网上很多资料,这里不赘述,我们直接进入主题,解析 leveldb 源码中各个类(概念)的功能。

    skwang
  • LevelDB 完全解析(4):Manifest

    内容上,Manifest 文件保存了整个 LevelDB 实例的元数据,比如:每一层有哪些 SSTable。 格式上,Manifest 文件其实就是一个 lo...

    linjinhe
  • LevelDB 完全解析(6):Filter

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

    linjinhe
  • LevelDB封装和功能拓展

    上期分享了LevelDB Java&Go实践内容,按照惯例,我自然不会傻傻地使用原生API,肯定要进行一番封装。经过一段时间的尝试和测试,功能终于稳定下来。

    FunTester
  • 鸿篇巨制 —— LevelDB 的整体架构

    本节信息量很大,我们要从整体上把握 LevelDB 这座大厦的结构。当我们熟悉了整体的结构,接下来就可以各个击破来细致了解它的各种微妙的细节了。

    老钱
  • LevelDB 代码撸起来!

    LevelDB 的大致原理已经讲完了,本节我们要亲自使用 Java 语言第三方库 leveldbjni 来实践一下 LevelDB 的各种特性。这个库使用了 J...

    老钱
  • LevelDB 完全解析(3):SSTable

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

    linjinhe
  • 秒级去重:ClickHouse在腾讯海量游戏营销活动分析中的应用

    导语 | 腾讯内部每日都需要对海量的游戏营销活动数据做效果分析,而活动参与人数的去重一直是一项难点。本文将为大家介绍腾讯游戏营销活动分析系统——奕星,在去重服...

    腾讯QQ大数据
  • Google-LevelDB简介

    LevelDB简介 LevelDB一句话描述 LevelDB是google开发的,一个速度非常块的KV存储库(storage library),它支持字符串的k...

    架构师之路
  • LevelDB 完全解析(5):Cache

    在 LevelDB 中,block cache 和 table cache 都是基于 ShardedLRUCache 实现的。

    linjinhe
  • lsm派系(不仅lsm tree)存储模型概述(下篇)

    这部分内容主要回答我们在文章开头提到的第二个问题。第二个问题展开其实是一连串的问题。例如:lsm派系难道只有lsm tree这一类存储模型吗?如果答案是否定的,...

    jaydenwen123
  • 源码面前没有秘密,推荐 9 个带你阅读源码的开源项目

    在文章开始之前,请各位先回忆下在日常开发过程中,都使用或依赖了哪些开源项目?是不是发现,开源项目已经完全融入到日常开发!

    HelloGitHub
  • 秒级去重:ClickHouse在腾讯海量游戏营销活动分析中的应用

    导语 | 腾讯内部每日都需要对海量的游戏营销活动数据做效果分析,而活动参与人数的去重一直是一项难点。本文将为大家介绍腾讯游戏营销活动分析系统——奕星,在去重服务...

    腾讯云大数据
  • 秒级去重:ClickHouse在腾讯海量游戏营销活动分析中的应用

    奕星 (EAS) 是腾讯内部专注于游戏营销活动分析的系统,在营销活动效果分析中,奕星遇到一个最大的问题就是对活动参与人数的去重,并给出对应的活动号码包。单个营销...

    腾小云

扫码关注云+社区

领取腾讯云代金券