overview
本文总结于：https://github.com/facebook/rocksdb/wiki/Rocksdb-BlockBasedTable-Format
整体上来说sst文件的结构如下：
<beginning_of_file>
[data block 1]
[data block 2]
...
[data block N]
[meta block 1: filter block] (see section: "filter" Meta Block)
[meta block 2: index block]
[meta block 3: compression dictionary block] (see section: "compression dictionary" Meta Block)
[meta block 4: range deletion block] (see section: "range deletion" Meta Block)
[meta block 5: stats block] (see section: "properties" Meta Block)
...
[meta block K: future extended block] (we may add more meta blocks in the future)
[metaindex block]
[Footer] (fixed size; starts at file_size - sizeof(Footer))
<end_of_file>
- kv数据对按顺序排布，并且被分割成一些列的数据块。数据区域排布在文件前面。数据块的组织方式参见block_builder.cc。
- 在数据域之后，存储的是meta域。meta域存储了多种类型的meta块。
- meta域后，存储的是metaindex块。metaindex块用于索引meta块。类似这种形式：
meta_name1, offset, size
meta_name2, offset, size
... ...
- 在文件的末尾是footer域，类似wiredtiger/innodb的file header，只不过rocksdb将其放到了文件末尾
// 存储metaindex块的偏移
metaindex_handle: char[p];
// 存储index块的偏移。index块属于meta块的一种。rocksdb将其单独拎出来，应该是为了查询加速
index_handle
// padding
padding:
// magic
magic:
Index块
Index块用于查找数据。查找的过程通过二分查找。一个文件可能包含一个或者多个索引块。索引块的具体格式参见：https://github.com/facebook/rocksdb/wiki/Index-Block-Format 每一个data块在Index块中都有一个entry。这个entry是一个二元组。第一个元素记录了data块的最后一个key?，第二个元素记录了data块的偏移和size。
Partitioned Index
所谓Partitioned Index指的是两层索引，也就是说第一层index块entry指向的不是数据块，而是第二层索引块。第二层索引块的entry记录的才是数据块。这样一个sst文件可以装下更多数据，并且第一层index块有更高的扇出。
Index块中的key
Index块中的key在前一个block块的最后一个key与下一个block块的第一个key之间。如果两个相邻数据块的key如下：
aa aac aade abc abccccab || abd abdd …
那么Index块关于上面例子中第一个数据块的key在[abccccab, abd)范围内。为了节省Index块的空间，可以通过算法选择size最小的key。
单独的索引块
在rocksdb5.14之前，BlockBasedTableOptions::format_version=2时，index块和数据块的格式是一致的。即:
// seq应该用于前缀压缩使用
(<user_key, seq>, value)
5.14以后index块的数据格式发生了变化。主要发生的变化是index块的重启点和data块的重启点不再相同。所谓重启点，即：
BlockBuilder对key的存储是前缀压缩的，对于有序的字符串来讲，这能极大的减少存储空间。但是却增加了查找的时间复杂度，为了兼顾查找效率，每隔K个key，leveldb就不使用前缀压缩，而是存储整个key，这就是重启点（restartpoint）。 在构建Block时，有参数Options::block_restart_interval定每隔几个key就直接存储一个重启点key。
restart_interval配置的越低，内存开销越大但是检索速度更快，cpu使用率更小。
- 在5.15引入format_version3：大多数情况下index块的seq字段是不需要的，因此seq字段可以省略 为什么
- 在5.16引入format_version4：每一个重启段内除了第一个元素后，后续的元素不再编码offset，而是通过delta的方式记录offset.eg:
restart_point 0: k, v (off, sz), k, v (delta-sz), ..., k, v (delta-sz)
restart_point 1: k, v (off, sz), k, v (delta-sz), ..., k, v (delta-sz)
...
restart_point n-1: k, v (off, sz), k, v (delta-sz), ..., k, v (delta-sz)
where, k is key, v is value, and its encoding is in parenthesis.
kBinarySearchWithFirstKey
意思是rocksdb不需要通过读data块来获取data块的第一个key，该feature用于加速查找。做法是在index块每个entry中记录相应的key。eg:
restart_point 0:
k (block_key), v (block_offset, block_size, size_of_first_key, first_key)
k (block_key), v (delta_size, size_of_first_key, first_key)
k (block_key), v (delta_size, size_of_first_key, first_key)
restart_point 1:
k (block_key), v (block_offset, block_size, size_of_first_key, first_key)
k (block_key), v (delta_size, size_of_first_key, first_key)
k (block_key), v (delta_size, size_of_first_key, first_key)
...
filter meta block
用于存储布隆过滤器相关的数据
Properties Meta Block
存储属性信息的meta块。块内数据的组织类似这样：
[prop1] (Each property is a key/value pair)
[prop2]
...
[propN]
Compression Dictionary Meta Block
与压缩相关的元数据块