Finish依次写入：尚未写入的最后一块Data Block及Meta Block、Index Block、Footer。Meta Block暂未使用，Footer则保存了meta block、index block的位置信息。

?

Block

?

Data Block、Meta Block、Index Block是业务划分，分别代表用户数据块、元数据块及用户数据索引块。其存储格式均为Block结构：

Record代表一条数据，蓝色及红色部分(统一称作”重启点”)为附加信息，而这些是做什么的呢？两点：性能优化、节省空间。

?

我们先来看Restart列表的构建逻辑：

?

?

 1 void BlockBuilder::Add(const Slice& key, const Slice& value) {
 2         Slice last_key_piece(last_key_);
 3         ......
 4         size_t shared = 0;
 5         if (counter_ < options_->block_restart_interval) {
 6             // See how much sharing to do with previous string
 7             const size_t min_length = std::min(last_key_piece.size(), key.size());
 8             while ((shared < min_length) && (last_key_piece[shared] == key[shared])) {
 9                 shared++;
10             }
11         }
12         else {    //restart时保存完整的key值
13             // Restart compression
14             restarts_.push_back(buffer_.size());
15             counter_ = 0;
16         }
17         const size_t non_shared = key.size() - shared;
18 
19         //Record信息
20         // shared size | no shared size | value size | no shared key data | value data
21         // Add "" to buffer_
22         PutVarint32(&buffer_, shared);
23         PutVarint32(&buffer_, non_shared);
24         PutVarint32(&buffer_, value.size());
25         // Add string delta to buffer_ followed by value
26         buffer_.append(key.data() + shared, non_shared);
27         buffer_.append(value.data(), value.size());
28 
29         // Update state
30         last_key_.resize(shared);
31         last_key_.append(key.data() + shared, non_shared);
32         assert(Slice(last_key_) == key);
33         counter_++;
34     }

?

每隔一定间隔(block_restart_interval)Record就会创建一个新的重启点，重启点内容为当前block的大小，即重启点在block内的偏移。

?

每当添加一个新的重启点时，重启点指向位置的Record中一定保存了完整的key值(shared size = 0),随后的Record中保存的key值仅为和上一个Record的差异值。因为Key在Block中是有序排列的，所以相邻key值重叠区域节省的空间还是非常可观的。

?

基于上述实现，问题来了：当需要定位一条记录时，因为record中key的信息是不完整的，仅包含了和上一条的差异项，但上一条记录本身也只包含了和再上一条的差异项，那么定位一条记录时如何做key比较？如果需要一直向上查找完成key值拼接，性能上会不会有损伤？

?

分析这个问题就要了解重启点的定位：Block的一级索引，SSTable的二级索引(Index Block是SSTable的一级索引)。本文将每个重启点记录位置所属的Record列表称为一个Restart Block

?

假设每条record记录的都是完整的key值时，从SSTable中查找一条记录的工作流如下：

?

根据Key值从Index Block中找到所属的Data Block

根据Key值从“重启点”列表中找到所属的Restart Block，从Restart Block的起始位置进行key值比较，找到正确的记录。

在上述流程中，我们必定会先找到一个Restart Point，随后进行key值比较，而Restart Point记录本身包含了完整的key值信息，后续key值均可基于此key得到。

?

Restart列表本身做为索引，提升了查找性能，而key值存储的小技巧又降低了空间使用率，在不损伤性能的情况小降低空间利用率，这是一个很好的例子。

?

即使这样，作者觉得还不够，空间利用率还可以进一步优化，并且不损伤任何读取数据的性能。

?

做法和Restart列表的做法类似，是在Index Block中，通过调用FindShortestSeparator / FindShortSuccessor方法实现。

1         // If *start < limit, changes *start to a short string in [start,limit).
2         // Simple comparator implementations may return with *start unchanged,
3         // i.e., an implementation of this method that does nothing is correct.
4         virtual void FindShortestSeparator(std::string* start, const Slice& limit) const = 0;
5 
6         // Changes *key to a short string >= *key.
7         // Simple comparator implementations may return with *key unchanged,
8         // i.e., an implementation of this method that does nothing is correct.
9         virtual void FindShortSuccessor(std::string* key) const = 0;

?

?

FindShortestSeparator找到start、limit之间最短的key值，如“helloworld”和”hellozoomer”之间最短的key值可以是”hellox”。FindShortSuccessor则更极端，用于找到比key值大的最小key，如传入“helloworld”，返回的key值可能是“i”而已。