Leveldb源码分析--7
6 SSTable之1
SSTable是Leveldb的核心之一，是表数据最终在磁盘上的物理存储。也是体量比较大的模块。
6.1 SSTable的文件组织作者在文档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）。
6.2 Block存储格式6.2.1 Block的逻辑存储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类实现。
6.2.2 重启点-restartpointBlockBuilder对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的构建和读取代码分析就是很直观的事情了。见下面的分析。
6.3 Block的构建与读取6.3.1 BlockBuilder的接口首先从Block的构建开始，这就是BlockBuilder类，来看下BlockBuilder的函数接口，一共有5个：
while (true) { if (!ParseNextKey()) return; if (Compare(key_, target)>= 0) return; }上面就是Block::Iter的全部实现逻辑，这样Block的创建和读取遍历都已经分析完毕。