SSTable(1) data block

每次minor compaction都会生成新的sstable，major compaction会将若干个sstable合并成一个大的sstable。

这次我们看一下sstable的读写过程。参考文章在这里

一个sstable文件按照块划分，用来提高读写效率。每个块的大小为4kb，每个block中除了存储数据还有压缩类型以及校验码

sstable中不同的block有不同的功能

data block

由于leveldb是按序存储，所以我们会使用类似前缀压缩的技术。不同的是每若干个键后我们会重头存储一个完整的键，并称为restart point

这样我们可以在restart point上进行比较，从而快速定位需要的数据块。然后顺序遍历并解压缩数据

看一下代码。结构内部很简单，就是data以及size，owned表示我们是否拥有这个数据，是的话释放的时候就要delete掉这块数据。restart offset就是 上面图中的restart point数据的起点。

检查一下restart point的有效性。然后计算restart offset。每个restart point以及最后的length都是uint32。乘起来计算一下偏移量就行。

读取block的方法就是通过iterator来。所以只提供了NewIterator

具体的实现在block.cc中。继承的Iterator

由于SSTable是不可变的，所以我们可以随意存储data pointer

为了减少indirection，我们就直接把data_和一些必要的信息存在Iterator中了

移动迭代器的核心在current_和restart_index_上

并且由于SSTable不可变，所以我们移动迭代器的时候就可以直接把对应的kv也拿出来。不会涉及到额外的拷贝。

先看Seek

通过二分来找到最大的小于target的restart point，这样我们就可以从这个restart point开始。

最开始的这个判断是判断如果我们已经在扫描状态下，就可以复用一下当前的结果。从而缩短更新的区间。

然后开始用二分，找到restart point并decode，根据结果去缩小区间。

最后在块内线性遍历。直到找到第一个大于等于target的key。

上面那个判断是说如果我们复用了之前的结果，就直接从之前的起点处继续扫描，而不是回到restart point上扫描了。因为之前判断的key是基于current的，而不是restart point上的值。

这里有一个很细节的地方要注意，就是我们最后得到的left这个restart point，他自己的key一定是小于target的，而left + 1的这个点则是大于等于target的。所以我们准确扫描的区间应该是(left, left + 1]。而在下面linear search的时候，我们是先ParseNextKey，再去比较。所以是先获得下一个key，从而跳过了left。

ParseNextKey会读取下一个key，并存储到key_中，这里的实现就是resize到shared上，然后append non shared个字节。

然后会判断如果我们跨越了restart point的话，就更新restart index。表示current所属的restart point区间。

剩下的移动也很容易。对于Next来说，就是调用ParseNextKey。而Prev的话则是记录当前的offset，然后从上一个restart point开始做线性扫描。

有一个很有意思的细节就是计算下一个entry的offset

current是当前key的offset，我们可以从中推导出next offset，但是通过value这种方法效率更高。利用了value是对当前block的slice的特性。

这里的实现中，更新了restart index后。直觉上来讲我们也需要更新current。但是我们每次调用ParseNextKey也需要更新current。所以他这里将这个职责留给了ParseNextKey。并且由于NextEntryOffset需要通过value来更新，所以这里我们只会设置一个特殊的value，然后在调用NextEntryOffset的时候，就会将offset更新为restart point的offset。

看完了读取然后看一下写入。我们是怎么构建data block的。具体在block_builder.cc中

核心API就三个。Reset表示重新构建，Add添加一个kv pair，Finish则是结束构建并返回buffer

restarts记录了restart point。counter则表示现在有多少个数据加入了，从而让我们可以添加新的restart point。

finshish就是将restart point的offset都写进去。最后写入restart point length

添加kv的时候，判断是否应该重设restart point。如果需要的话就添加restart point并重设counter

否则的话我们就根据last key计算一下共享的key

将非共享的key写入到buffer中。然后更新last key。用来下一次的判断。