LevelDB源码分析--Iterator

我们先来参考来至使用Iterator简化代码2-TwoLevelIterator的例子,略微修改希望能帮助更加容易立即,如果有不理解请各位看客阅读原文。

下面我们再来看一个例子,我们为一个书店写程序,书店里有许多书Book,每个书架(BookShelf)上有多本书。

类结构如下所示

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

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

vector<Book>& GetBooks() const {
  return books_;
}
 

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

一种实现方式是,由BookStore负责保存中间状态,包括当前遍历到了哪个书架,遍历到了书架上的那本书。

// 书店类
class BookStore {
 Iterator* NewIterator() const;
 private:
  vector<Shelf> shelf_;
  vector<Shelf>::iterator shelf_iter_;
  vector<Book>::iterator book_iter_;
};

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

class TwoLevelIterator: public Iterator {
  vector<Shelf>::iterator shelf_iter_;
  vector<Book>::iterator book_iter_;
void SeekToFirst() {
  shelf_iter_.SeekToFirst();
  if (shelf_iter_.iter() != NULL) book_iter_.SeekToFirst();
}
void TwoLevelIterator::Next() {
  if (book_iter_ == shelf_iter_.end())
  {
    shelf_iter_.Next();
    book_iter_.SeekToFirst();
  }else{
    book_iter_.Next();
  }
}

这里只是作一个简单的示例过程,具体代码暂时不列出,如果以后有空进行整理的时候可以列一个完整的代码。

了解了这个基本原理以后,我们来看leveldb 中的

class TwoLevelIterator: public Iterator {
BlockFunction block_function_; block内部迭代器的生成函数
  void* arg_;  //通常为TableCahe,供block_function_调用的参数
  const ReadOptions options_;
  Status status_;
  IteratorWrapper index_iter_; //大致相当于shelf_iter_
  IteratorWrapper data_iter_; // 大致相当于book_iter_
  std::string data_block_handle_;
};

void TwoLevelIterator::SeekToFirst() {
  index_iter_.SeekToFirst(); //跳到第一个block
  InitDataBlock();                 //根据当前block设置data_iter_
  if (data_iter_.iter() != NULL) data_iter_.SeekToFirst();
  SkipEmptyDataBlocksForward(); //跳过空block
}

leveldb中TwoLevelIterator也类似BookStore有一个block的遍历指针存放至TwoLevelIterator中而已,当一个block遍历完的时候使用该迭代器跳到下一个block,然后在设置对应的data_iter_。只是在过程中遍历下一层data_iter时内部结构可能尚未初始化需要调用BlockReader从磁盘读取文件进行初始化设置。

这里只是说明了使用TwoLevelIterator遍历SSTable时,当遍历db的时候也同样可以类似的对应SSTable层级的一个迭代器即可,而block_function_需要设置为GetFileIterator就可以遍历整个数据库了。

LevelDB源码分析--Iterator,布布扣,bubuko.com

LevelDB源码分析--Iterator

上一篇:Win7 64bit系统WinFrom下未能加载文件或程序集“System.Data.SQLite”的解决办法


下一篇:SQL 如果存在就更新,如果不存在就添加,使用 Merge 函数(SQL2008版本及以上)