sstable(sorted string table)是google bigtable中引出的数据结构，在levelDB、RocksDB以及现在各类数据库存储中配合LSM有广泛应用，学习下很有必要，本位以RocksDB中SST的实现来了解SST。
优点
- 空间利用率高：sstable基于sorted string的结构使得他非常适合做压缩，有更好的空间利用率
- 利于合并：key本身是sorted，非常适合采用归并排序来做merge。LSM中利用sstable作为基本存储单元也有这样的考量
存储结构
sstable是sorted string table的缩写，存储结构的设计关键在于sorted string。
sstable文件内部有多个数据块(block)构成。
一个数据块内多个entry的key是按照字符来排序的，并且充分利用prefix string来减少存储开销。
不过为了避免第一个prefix key导致全部entry损坏，固定entry个数会有一个entry包含完整key信息，这个点称之为restart point。
这个entry的key的shared值重置为0。block结尾的tailer会记录restart point的偏移量信息。
下图来源[1] 展示了SST的基本结构。
Block的定义：
Block 结构是指除了内部的有效数据外，还会有额外的压缩类型字段和校验码字段。
每一个 Block 尾部都会有压缩类型和循环冗余校验码（crcValue），这会要占去 5 字节。压缩算法默认是 snappy ，校验算法是 crc32。
-
footer:位于ssTable尾部，记录指向Metaindex Block的Handle和指向Index Block的Handle。
所有的Handle是通过偏移量Offset以及Size一同来表示的，用来指明所指向的Block位置。
Footer是解析ssTable文件最开始的地方。通过Footer中记录的这两个关键元信息Block的位置，可以方便的开启之后的解析工作。
另外Footer种还记录了用于验证文件是否为合法SST文件的常数值魔数(maigicnum)。 -
index block: 记录data block的元信息
-
metaindex block: 记录过滤器相关的元信息
-
data block: 保存了kv信息
-
filter block: 现在其实只有一种meta block即filter block。
写入Data Block的数据会同时更新对应Meta Block中的过滤器。
读取数据时也会首先经过布隆过滤器过滤。
Meta Block的物理结构也与其他Block有所不同。bloom filter帮助读操作，确认该sstable内是否包含对应数据。
如果不包含对应数据，则直接避免遍历sstable
RocksDB & LSM
LSM tree (log-structured merge-tree) 是一种对频繁写操作非常友好的数据结构，同时兼顾了查询效率。
LSM tree 是许多 key-value 型、日志型数据库以及新型分布式数据库、OLAP引擎所依赖的核心数据结构，例如 BigTable、HBase、Cassandra、LevelDB、SQLite、Scylla、RocksDB、OceanBase等。由于RocksDB的实现比较有代表性，下面原理的介绍中关于实现部分都以RocksDB的实现为例。
使用场景
我们都知道的一个客观事实是——磁盘或内存的连续读写性能远高于随机读写性能。
LSM由于避免了随机读写，在读写性能上其实都有还不错的表现，尤其在写性能上很突出。
适合于面向写多读少的场景。下图展示了磁盘内存随机、顺序读写的差异。
结构说明
