Level DB --- TableBuilder

TableBuilder是Level DB里面重要的类和模块，它描述了数据如何序列化到文件中，以及数据里面的格式逻辑。它里面包含了之前介绍的多个模块和类。

data block、filter block和index block

block格式，之前已经介绍过Level DB --- BlockBuilder-CSDN博客 、 Level DB --- Block-CSDN博客。data block 是借助block为基础数据结构用来存储 Key-Value数据。filter 之前也已经介绍过Level DB --- BloomFilterPolicy-CSDN博客，filter block 是借助block为基础的数据结构存储filter数据。table中有多个data block，么个data block有在table中自己的index，index block是借助block为基础数据结构用来存储data block的index。这个数据组织如图1所示。

                                                          图1.   table builder 

写入数据

写入数据，这里写数据使用WritableFile（Level DB --- env.File-CSDN博客），block的序列化数据支持不压缩或是压缩数据，且使用crc做校验。

index filter key

在计算上由于key一直都是有序的，所以index block里面，其key是由上一个data block最后一个key，和下一个data block第一个key，比较计算组成，其计算代码和注释如下：

 void FindShortestSeparator(std::string* start,
                             const Slice& limit) const override {
    // Find length of common prefix
    size_t min_length = std::min(start->size(), limit.size());
    size_t diff_index = 0;
    while ((diff_index < min_length) &&
           ((*start)[diff_index] == limit[diff_index])) {
      diff_index++;
    }

    if (diff_index >= min_length) {
      // Do not shorten if one string is a prefix of the other
    } else {
      uint8_t diff_byte = static_cast<uint8_t>((*start)[diff_index]);
      if (diff_byte < static_cast<uint8_t>(0xff) &&
          diff_byte + 1 < static_cast<uint8_t>(limit[diff_index])) {
        //获得diff位上字符在字母表中的下一个字符，"the quick brown fox" and "the who" 的例子，通过这种方式，计算得到"the r"
        (*start)[diff_index]++;
        start->resize(diff_index + 1);
        assert(Compare(*start, limit) < 0);
      }
    }
  }