SSTable是Leveldb的核心之一，是表数据最终在磁盘上的物理存储。也是体量比较大的模块。

作者在文档doc/table_format.txt中描述了表的逻辑结构，如图6.1-1所示。逻辑上可分为两大块，数据存储区Data Block，以及各种Meta信息。

1）文件中的k/v对是有序存储的，并且被划分到连续排列的Data Block里面，这些Data Block从文件头开始顺序存储，Data Block的存储格式代码在block_builder.cc中；

2）紧跟在Data Block之后的是Meta Block，其格式代码也在block_builder.cc中；Meta Block存储的是Filter信息，比如Bloom过滤器，用于快速定位key是否在data block中。

3）MetaIndex Block是对Meta Block的索引，它只有一条记录，key是meta index的名字（也就是Filter的名字），value为指向meta index的BlockHandle；

BlockHandle是一个结构体，成员offset_是Block在文件中的偏移，成员size_是block的大小；

4）Index block是对Data Block的索引，对于其中的每个记录，其key >=Data Block最后一条记录的key，同时<其后Data Block的第一条记录的key；value是指向data index的BlockHandle；

图6.1-1

5）Footer，文件的最后，大小固定，其格式如图6.1-2所示。

图6.1-2

成员metaindex_handle指出了meta index block的起始位置和大小；成员index_handle指出了index block的起始地址和大小；这两个字段都是BlockHandle对象，可以理解为索引的索引，通过Footer可以直接定位到metaindex和index block。再后面是一个填充区和魔数（0xdb4775248b80fb57）。

Data Block是具体的k/v数据对存储区域，此外还有存储meta的metaIndex Block，存储data block索引信息的Index Block等等，他们都是以Block的方式存储的。来看看Block是如何组织的。每个Block有三部分构成：block data, type, crc32，如图6.2-1所示。

图6.2-1

类型type指明使用的是哪种压缩方式，当前支持none和snappy压缩。

虽然block有好几种，但是Block Data都是有序的k/v对，因此写入、读取BlockData的接口都是统一的，对于Block Data的管理也都是相同的。

对Block的写入、读取将在创建、读取sstable时分析，知道了格式之后，其读取写入代码都是很直观的。

由于sstable对数据的存储格式都是Block，因此在分析sstable的读取和写入逻辑之前，我们先来分析下Leveldb对Block Data的管理。

Leveldb对Block Data的管理是读写分离的，读取后的遍历查询操作由Block类实现，BlockData的构建则由BlockBuilder类实现。

BlockBuilder对key的存储是前缀压缩的，对于有序的字符串来讲，这能极大的减少存储空间。但是却增加了查找的时间复杂度，为了兼顾查找效率，每隔K个key，leveldb就不使用前缀压缩，而是存储整个key，这就是重启点（restartpoint）。

在构建Block时，有参数Options::block_restart_interval定每隔几个key就直接存储一个重启点key。

Block在结尾记录所有重启点的偏移，可以二分查找指定的key。Value直接存储在key的后面，无压缩。

对于一个k/v对，其在block中的存储格式为：

> 共享前缀长度         shared_bytes:    varint32

> 前缀之后的字符串长度 unshared_bytes:  varint32

> 值的长度             value_length:     varint32

> 前缀之后的字符串     key_delta:        char[unshared_bytes]

> 值                   value:           char[value_length]

对于重启点，shared_bytes= 0

Block的结尾段格式是：

> restarts:       uint32[num_restarts]

> num_restarts:  uint32 // 重启点个数

元素restarts[i]存储的是block的第i个重启点的偏移。很明显第一个k/v对，总是第一个重启点，也就是restarts[0] = 0;

图6.2-2给出了block的存储示意图。

图6.2-2

总体来看Block可分为k/v存储区和后面的重启点存储区两部分，其中k/v的存储格式如前面所讲，可看做4部分：

前缀压缩的key长度信息 + value长度 + key前缀之后的字符串+ value

最后一个4byte为重启点的个数。

对Block的存储格式了解之后，对Block的构建和读取代码分析就是很直观的事情了。见下面的分析。

首先从Block的构建开始，这就是BlockBuilder类，来看下BlockBuilder的函数接口，一共有5个：

  void Reset(); // 重设内容，通常在Finish之后调用已构建新的block
  //添加k/v，要求：Reset()之后没有调用过F