leveldb源码分析--SSTable之block

void BlockBuilder::Add(const Slice& key, const Slice& value) {
  //一些基本的状态判断，如上次插入的key是否比当前key小等
  if (counter_ < options_->block_restart_interval) {
    // 不需要restart时取得跟上一个restart点的key的相同部分
    const size_t min_length = std::min(last_key_piece.size(), key.size());
    while ((shared < min_length) && (last_key_piece[shared] == key[shared])) {
      shared++;
    }
  } else {
    // 否则，完整存储key，并记录restart点
    restarts_.push_back(buffer_.size());
    counter_ = 0;
  }
  const size_t non_shared = key.size() - shared;
  // 按“共享长度 | 非共享长度| 值长度| 非共享数据| value值写入buffer
  PutVarint32(&buffer_, shared);
  PutVarint32(&buffer_, non_shared);
  PutVarint32(&buffer_, value.size());
  // Add string delta to buffer_ followed by value
  buffer_.append(key.data() + shared, non_shared);
  buffer_.append(value.data(), value.size());
  // Update state
  last_key_.resize(shared);
  last_key_.append(key.data() + shared, non_shared);
  assert(Slice(last_key_) == key);
  counter_++;
}

const FilterPolicy* policy_;         //  filter,即hash算法实现类
  std::string keys_;                     //  所有key，一个接一个一直添加在一起
  std::vector<size_t> start_;            //  每个key在keys_中的开始位置
  std::string result_;                   // 已经产生的Filter数据
  std::vector<Slice> tmp_keys_;          // 用来还原keys的一个临时数组
  std::vector<uint32_t> filter_offsets_; //每次生成的filter值偏移

void FilterBlockBuilder::StartBlock(uint64_t block_offset) {
  uint64_t filter_index = (block_offset / kFilterBase); // block的偏移 / 2K
// 这里上一个block时 filter_index == 上次 block_offset  / kFilterBase,
//所以这次block大小/kFilterBase >=2 时会调用两次以上GenerateFilter，
//而连续调用时，只是在filter_offsets_中添加一个当前大小，但并未扩充其空间
  while (filter_index > filter_offsets_.size()) {
    GenerateFilter();
  }
}

void FilterBlockBuilder::GenerateFilter() {
  const size_t num_keys = start_.size();
  if (num_keys == 0) {
    // Fast path if there are no keys for this filter ，连续被第二次调用时进入此逻辑
    filter_offsets_.push_back(result_.size());
    return;
  }
  //还原为key数组
  start_.push_back(keys_.size()); // Simplify length computation
  tmp_keys_.resize(num_keys);
  for (size_t i = 0; i < num_keys; i++) {
    const char* base = keys_.data() + start_[i];
    size_t length = start_[i+1] - start_[i];
    tmp_keys_[i] = Slice(base, length);
  }
  // 记录生成filter信息的开始偏移量
  filter_offsets_.push_back(result_.size());
  policy_->CreateFilter(&tmp_keys_[0], num_keys, &result_);
//还原状态
  tmp_keys_.clear();
  keys_.clear();
  start_.clear();
}