共计 2956 个字符，预计需要花费 8 分钟才能阅读完成。
LSM tree 保障数据库是有序写入（memtable-skiplist），起高了写性能，然而因为其自身的分层构造，就义了读性能（一个 key 如存储在了低级别的 level，从上到下每一层都要进行查找，代价极大）。所以，针对读的性能晋升有了很多的优化：bloom filter（高效判读一个 key 是否不存在），index-filter（二分查找，耗费低内存的状况下）索引 key-value 数据。这一些数据库都须要存储在 SST 文件之中，用来进行 k - v 数据的有序治理。
SST 文件格式概览
1）Footer：固定 48 字节，指出 IndexBlock 和 MetaIndexBlock 在文件中的偏移量信息，它是元信息的元信息，它位于 sstable 文件的尾部
2）IndexBlock：占用一个 block 空间，记录了 DataBlock 相干的元信息
3）MetaIndexBlock：占用一个 block 空间，各个元信息的 Block，包含 Filter、Properties(整个 table 的属性信息)、Compression dictionary、Range deletion tombstone
4）MetaBlock：可能占用多个 block 空间，存储布隆过滤器的二进制数据 及其他元信息数据
5）DataBlock：可能占用多个 block 空间，存储理论的数据即键值对内容
Footer 构造
Footer 固定 48 个字节大小，位于 SSTable 文件尾部；MetaBlockIndex 和 DataBlockIndex 的 offset 和 size 组成 BlockHandlel 类型，用于寻址 MetaBlockIndex 和 DataBlcokIndex 的块所在的地位，size 和 offset 采纳 varint 变长编码，以节俭空间，offset 和 size 起码占用 1 个字节长度、最多占用 9 个字节长度，因而 MetaBlockIndex 和 DataBlockIndex 的 offset 和 size 最多占用 4 *9=36 个字节，通过 padding 补齐到 40 个字节（8 字节对齐）；比方 DataBlockIndex.offset = 64、DataBlockIndex.size=216，示意 DataBlockIndex 位于 SSTable 文件的第 64 个字节至 280 个字节。
Block 构造
5 个局部的数据结构，除了 Footer，其余的物理构造都是 Block 模式。每个 Block 对应物理磁盘的一个存储块，因而，Block 的大小与磁盘存储块的大小统一．这也是 Footer 放到文件开端的起因，Footer 自身48个字节不能占用一个磁盘存储块．Block 在硬盘上存储的时候，会在理论数据之后加上 5 个字节的额定内容：compression type、crc。
Data Block 构造
DataBlcok Key 的存储采纳了前缀压缩机制，前缀压缩，就是对于 key 的雷同前缀，尽量只存储一次以节俭空间。然而对于 SSTable 来说它并不是对整个 block 的所有 key 进行一次性地前缀压缩，而是设置了很多区段，处于同一区段的 key 进行一次前缀压缩，每个区段的终点就是一个重启点。前缀压缩机制导致每条记录须要记住它对应的 key 的共享长度和非共享长度。所 谓 key 的共享长度，是指以后这条记录的 key 与上一条记录的 key 公共前缀的长 度，非共享长度则是去掉雷同局部后的不同局部的长度。这样以后这条记录只须要存储不同的那局部 key 的值即可。
第一局部 (Entry) 用来存储 key-value 数据。因为 sstable 中所有的 key-value 对都是严格按序存储的，用了节俭存储空间，并不会为每一对 key-value 对都存储残缺的 key 值，而是存储与上一个 key 非共享的局部，防止了 key 反复内容的存储。每距离若干个 key-value 对，将为该条记录从新存储一个残缺的 key。反复该过程（默认距离值为 16），每个从新存储残缺 key 的点称之为 Restart point。
Restart point 的目标是在读取 sstable 内容时，减速查找的过程。因为每个 Restart point 存储的都是残缺的 key 值，因而在 sstable 中进行数据查找时，能够首先利用 restart point 点的数据进行键值比拟，以便于疾速定位指标数据所在的区域；当确定指标数据所在区域时，再顺次对区间内所有数据项逐项比拟 key 值，进行细粒度地查找；该思维有点相似于跳表中利用高层数据迅速定位，底层数据具体查找的理念，升高查找的复杂度。
KV 数据存储构造
shared key length: 与 restart point 雷同的 key 前缀字节长度．
unshared key length: 以后 key 减去 restart point 雷同前缀长度后，残余的字节长度
value length: 数值的字节长度
unshared key content: key 与 restart point 中的 key 不雷同局部的 key 内容．
value: 存储实在的数值
Index Block 构造
index block 蕴含若干条记录，每一条记录代表一个 data block 的索引信息，用于疾速定位到蕴含特定 key 的 Data Block；Index Block 首先是一个 block，因而蕴含三局部 KeyValue、Type（固定 1 字节）、CRC 检验码（固定 4 字节）；Type 标识该局部数据是否采纳压缩算法，CRC 是 KeyValue + Type 的检验码。
一条索引包含以下内容：
key，取值是大于等于其索引 block 的最大 key，并且小于下一个 block 的最小 key；
该 data block 起始地址在 sstable 中的偏移量；
该 data block 的大小；
IndexBlock 和 DataBlock 一样，采取了前缀压缩，只不过距离为 2（DataBlock 默认为 16）。
为什么 key 不是采纳其索引的 DataBlock 的最大 key？
次要目标是节俭空间；假如其索引的 block 的最大 key 为 ”acknowledge”，下一个 block 最小的 key 为 ”apple”，如果 DataBlockIndex 的 key 采纳其索引 block 的最大 key，占用长度为 len(“acknowledge”)；采纳后一种形式，key 值能够为 ”ad”（”acknowledge” < “ad” < “apple”），长度仅为 2，并且检索成果是一样的。
为什么 BlockHandle 的 offset 和 size 的单位是字节数而不是 block？
因为 SSTable 中的 block 大小是不固定的，尽管 option 中能够指定 block_size 参数，但 SSTable 中存储数据时，并未严格依照 block_size 对齐，所以 offset 和 size 指的是偏移字节数和长度字节数。这样做次要有两个起因：
（1）能够存储任意长度的 key 和任意长度的 value，而同一个 key-value 是不能跨 block 存储的，极其状况下，比方咱们的单个 value 就很大，曾经超过了 block_size，那么对于这种状况，SSTable 就没法进 行存储了。所以通常，理论的 Block 大小都是要稍微大于 block_size 的；
（2）从另外一个角度看，如果严格依照 block_size 对齐存储数据，必然有很多 block 通过补 0 的形式对齐，节约存储空间。
