本文共 4272 字，大约阅读时间需要 14 分钟。
前言
前面我们介绍了sstable的存储格式，在介绍sstable时，我们主要关注的是sstable的空间布局，主要是以block为单位。但是具体block里面是怎么存储数据的，我们并没有做过多的介绍。在前面一篇介绍TableBuilder的文章中，我们知道TableBuilder主要是负责生成sstable文件，而且正如我们之前所说，TableBuilder负责的是宏观的sstable生成，具体到数据的存储，它主要还是通过调用Block.Add函数完成。本篇我们将介绍sstable中的block里面具体是怎么存储数据的。主要介绍下面两种类型的block：
- data block
- index block
data block和index block
通过TableBuilder的Add函数的源代码我们知道，data block和index block都是通过BlockBuilder类来构造的。在向data block和index block中添加数据时，主要是通过调用block builder的Add函数完成：
void BlockBuilder::Add(const Slice& key, const Slice& value)
我们看一下blockBuilder的数据成员：
Add函数是核心，我们下面详细分析Add函数，来了解leveldb是怎么在block中存储数据的。
BlockBuilder.Add函数的实现
void BlockBuilder::Add(const Slice& key, const Slice& value) Slice last_key_piece(last_key_); assert(!finished_);//确定该block没有调用finish结束添加数据 assert(counter_ <= options_->block_restart_interval); assert(buffer_.empty() // No values yet? || options_->comparator->Compare(key, last_key_piece) > 0);
最开始几行主要是检查一些合法性条件。比如确保新加入的key不小于block中现存的最大key；counter_是一个计数器，leveldb将相邻存储的key-value的key进行压缩存储，压缩形式是提取公共前缀，这counter就是记录提取公共前缀进行压缩的key-value的个数。之所以提取公共前缀可以取得比较好的压缩效果，主要是基于leveldb中存储的key-value是按照key的大小顺序，这导致相邻的key-value的key前缀重合的概率会比较大，因此便于提取前缀压缩存储，但是显然这是需要在一定的相邻范围内才有效的，如果键值对数量太多，则具有较长的公共前缀的优势也便不复存在了。这里的counter就是控制这个压缩范围的。一般以不大于options_->block_restart_interval个键值对为单位进行前缀压缩。
size_t shared = 0; if (counter_ < options_->block_restart_interval) { // See how much sharing to do with previous string 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 { // Restart compression restarts_.push_back(buffer_.size()); counter_ = 0; } const size_t non_shared = key.size() - shared; 后面这部分是一个条件分支。如果counter_ < options_->block_restart_interval，则将当前的key-value和前面的key-value一起进行前缀压缩，并通过一个while循环找到当前的key和前面的key的公共前缀；如果counter_ == options_->block_restart_interval，则说明当前的key不能和前面的键值对一起进行前缀压缩了，需要开启一个新的前缀压缩，并且当前key-value作为这个新的前缀压缩中的第一个元素，显然对于每一个前缀压缩集合，集合中的第一个元素必须要完整保存下来，因为通过它才能找到后面的压缩key的前缀。同时我们还会用一个restart_数组记录新的前缀压缩在block中的起始位置，并重置计数器为0。
这一部分执行完成之后，shared记录了当前key在此次压缩中的共享前缀(与它的前一个key的共享前缀)的长度，non_shared则是除共享前缀之外的其他部分的长度。
PutVarint32(&buffer_, shared); PutVarint32(&buffer_, non_shared); PutVarint32(&buffer_, value.size()); buffer_.append(key.data() + shared, non_shared); buffer_.append(value.data(), value.size());
后面就是将这个压缩后的key-value放入到buffer中。从代码我们可以看到，buffer中的每个key-value的存储格式如下图所示：
last_key_.resize(shared); last_key_.append(key.data() + shared, non_shared); assert(Slice(last_key_) == key); counter_++;
最后这几行代码就是将last_key设置为当前的key，并增加计数器。
这里需要注意一点，从前面的while循环找公共前缀的代码中我们可以看到，每一个key都是和它前面的key进行共享公共前缀，而不是和整个前缀压缩集合中的最起始的key进行共享前缀，因此恢复一个key的本来面目应该具有O(n)的事件复杂度，n就是每个前缀压缩集合中的键值对个数。因为必须从压缩集合的最开始元素开始逐个对后面的元素进行解压缩(恢复它的前缀)
到这里我们基本上就知道了block中的数据存储格式。但是还有一个问题，我们前面说过为了提高效率，每个压缩集合中的键值对不能太多，由此对于一个data block，它应该有多个前缀压缩集合。前面，我们在分析源码时也提到过，BlockBuilder通过一个restart_数组记录每个压缩集合的起始位置，这个位置其实就是该压缩集合的起始key-value在该block中的偏移位置。所以为了找到所有的压缩集合，我们还必须将这个restart_数组存储到block中。这个过程在BlockBuilder.Finish中完成。
BlockBuilder.Finish函数的实现
Slice BlockBuilder::Finish() { // Append restart array for (size_t i = 0; i < restarts_.size(); i++) { PutFixed32(&buffer_, restarts_[i]); // 将各个restart点放到key/value数据后面 } PutFixed32(&buffer_, restarts_.size()); finished_ = true; return Slice(buffer_);} 这个函数一般是在Block构建完毕时调用。我们看到，它将restart_中的元素逐个添加到bock中，restart_中每个元素都是一个数字，为了查找方便，finish直接按每个元素32bit进行存储。
综上一个block的存储布局应该是如下图所示：
总结
本篇博文主要是介绍了index block和data block，或者说以key-value形式存储数据的block，的构造过程。主要细节封装在BlockBuilder类中。由于leveldb中的数据是按照key的大小顺序存储的，因此便于用前缀压缩的方法进行存储以提高空间效率。leveldb将每个block分成多个相邻的key-value组成的集合，以这些集合为单位进行前缀压缩，并将每个集合的起始key-value在block中的的偏移位置放在数据区的后面，因此通过这个找到起始位置就可以找到压缩集合，找到压缩集合就可以将集合中的每个key进行解码恢复。
本篇主要介绍的是以key-value形式存储数据的block的数据存储格式，但并不是所有的block都是以这种方式进行存储数据的，下面我们将剖析filter block的存储形式。