LevelDB源码分析之十四：TwoLevelIterator

LevelDB源码分析之十四：TwoLevelIterator

一.原理

先看一个例子，我们为书店写一个管理图书的程序，书店里有许多书Book，每个书架（BookShelf)上有多本书。 类结构如下所示：

class Book {private: string book_name_;};class Shelf { private: vector books_;};

如何遍历书架上所有的书呢？一种实现方法是：

vector& GetBooks() const { return books_;}

这样的实现暴漏了内部太多的细节，调用者根本就不需要知道Shelf存储Book的方式，仅仅需要遍历所有的数据即可。而且这样当我们换用另外一种数据结构存储Book时，客户端的代码就需要进行修改。但是如果使用Iterator模式则没有这个问题。

具体的我们需要遍历书店中所有的书，现在应该如何实现呢？ 一种实现方式是，由BookStore负责保存中间状态，包括当前遍历到了哪个书架，遍历到了书架上的哪本书。

class BookStore { Iterator* NewIterator() const; private: vector shelf_; vector::iterator shelf_iter_; vector::iterator book_iter_;};

这种实现方法对外是干净的，但是对于BookStore的维护者来说却是不友好的，Iterator的中间状态不是BookStore的成员，逻辑上不应该由BookStore维护。而且当两个甚至多个用户同时遍历书店时BookStore得同时维护多个中间状态，极其容易出错。更好的一种实现方式是，把遍历Iterator相关的代码和状态封装成一个类，有两个层级Shelf 和 Book，这个类的名字我们叫做TwoLevelIteator。

在双层迭代器中，level1中的迭代器指向的是一个容器，level2中的迭代器才指向真正的元素。对应到书店，level1指向书架（对图书进行分类），level2指向图书。当要查找某本书时，先要定位到书架，再在该书架中根据书的编号找到具体的书。

二.LevelDB中的实现

1.头文件

class TwoLevelIterator: public Iterator { public: TwoLevelIterator( Iterator* index_iter, BlockFunction block_function, void* arg, const ReadOptions& options); virtual ~TwoLevelIterator(); virtual void Seek(const Slice& target); virtual void SeekToFirst(); virtual void SeekToLast(); virtual void Next(); virtual void Prev(); virtual bool Valid() const { return data_iter_.Valid(); } virtual Slice key() const { assert(Valid()); return data_iter_.key(); } virtual Slice value() const { assert(Valid()); return data_iter_.value(); } virtual Status status() const { // It'd be nice if status() returned a const Status& instead of a Status if (!index_iter_.status().ok()) { return index_iter_.status(); } else if (data_iter_.iter() != NULL && !data_iter_.status().ok()) { return data_iter_.status(); } else { return status_; } } private: void SaveError(const Status& s) { if (status_.ok() && !s.ok()) status_ = s; } void SkipEmptyDataBlocksForward(); void SkipEmptyDataBlocksBackward(); void SetDataIterator(Iterator* data_iter); void InitDataBlock(); BlockFunction block_function_;//生成Data Block中block_data字段的迭代器 void* arg_; const ReadOptions options_; Status status_; IteratorWrapper index_iter_;//第一层迭代器，Index Block的block_data字段迭代器的代理 IteratorWrapper data_iter_; //第二层迭代器，Data Block的block_data字段迭代器的代理 // If data_iter_ is non-NULL, then "data_block_handle_" holds the // "index_value" passed to block_function_ to create the data_iter_. std::string data_block_handle_;//handle中间变量};

这里需要注意的是，两层迭代器都是IteratorWrapper类型而不是iter，主要是为了缓存key和valid，避免每次都要调用iterator->key()和iterator->valid()，因为虚函数调的频繁调用，有一定的性能消耗。至于为何有性能损耗，可参考：

​​C++中虚函数(virtual function)到底有多慢​​

​​为什么 C++ 中使用虚函数时会影响效率？​​

2.迭代器的初始化

void TwoLevelIterator::InitDataBlock() { if (!index_iter_.Valid()) { // 当index_iter_无效时，让data_iter_也无效 SetDataIterator(NULL); } else { // index_iter_是Index Block中block_data字段迭代器的代理 // handle是对应的Data Block的偏移和该Data Block的block_data字段大小编码后的结果 Slice handle = index_iter_.value(); if (data_iter_.iter() != NULL && handle.compare(data_block_handle_) == 0) { // 如果data_iter_已经创建了，什么都不用干，这可以防止InitDataBlock被多次调用 } else { // 创建Data Block中block_data字段的迭代器 Iterator* iter = (*block_function_)(arg_, options_, handle); // 将handle转化为data_block_handle_ data_block_handle_.assign(handle.data(), handle.size()); // 将iter传给其代理data_inter_ SetDataIterator(iter); } }}

3.迭代器的各种操作

// Index Block的block_data字段中，每一条记录的key都满足：// 大于上一个Data Block的所有key，并且小于后面所有Data Block的key// 因为Seek是查找key>=target的第一条记录，所以当index_iter_找到时，// 该index_inter_对应的data_iter_所管理的Data Block中所有记录的// key都小于target，需要在下一个Data Block中seek，而下一个Data Block// 中的第一条记录就满足key>=targetvoid TwoLevelIterator::Seek(const Slice& target) { index_iter_.Seek(target); InitDataBlock(); // data_iter_.Seek(target)必然会找不到，此时data_iter_.Valid()为false // 然后调用SkipEmptyDataBlocksForward定位到下一个Data Block，并定位到 // 该Data Block的第一条记录，这条记录刚好就是要查找的那条记录 if (data_iter_.iter() != NULL) data_iter_.Seek(target); SkipEmptyDataBlocksForward();}// 因为index_block_options.block_restart_interval = 1// 所以这里是解析第一个Block Data的第一条记录void TwoLevelIterator::SeekToFirst() { index_iter_.SeekToFirst(); InitDataBlock(); if (data_iter_.iter() != NULL) data_iter_.SeekToFirst(); SkipEmptyDataBlocksForward();}// 因为index_block_options.block_restart_interval = 1// 所以这里是解析最后一个Block Data的最后一条记录void TwoLevelIterator::SeekToLast() { index_iter_.SeekToLast(); InitDataBlock(); if (data_iter_.iter() != NULL) data_iter_.SeekToLast(); SkipEmptyDataBlocksBackward();}void TwoLevelIterator::Next() { assert(Valid()); data_iter_.Next(); SkipEmptyDataBlocksForward();}void TwoLevelIterator::Prev() { assert(Valid()); data_iter_.Prev(); SkipEmptyDataBlocksBackward();}void TwoLevelIterator::SkipEmptyDataBlocksForward() { // 1.如果data_iter_.iter()为NULL，说明index_iter_.Valid()为为NULL时调用了 // SetDataIterator(NULL)，此时直接返回，因为没数据可读啦 // 2.如果data_iter_.Valid()为false，说明当前Data Block的block_data字段读完啦 // 开始读下一个Data Block的block_data字段（从block_data第一条记录开始读） while (data_iter_.iter() == NULL || !data_iter_.Valid()) { // Move to next block if (!index_iter_.Valid()) { SetDataIterator(NULL); return; } index_iter_.Next(); InitDataBlock(); if (data_iter_.iter() != NULL) data_iter_.SeekToFirst(); }}void TwoLevelIterator::SkipEmptyDataBlocksBackward() { while (data_iter_.iter() == NULL || !data_iter_.Valid()) { // Move to next block if (!index_iter_.Valid()) { SetDataIterator(NULL); return; } index_iter_.Prev(); InitDataBlock(); if (data_iter_.iter() != NULL) data_iter_.SeekToLast(); }}

注释还是写的比较详细的，备忘足矣。block_function_是BlockFunction类型的函数指针，实参在Table类中，名为BlockReader。

关于Table，详见： ​​LevelDB源码分析之十三：table​​

​

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。