SSTable，从字面上理解是”sorted string table”，即包含排序过的字符串的表。LevelDB的SSTable实际上是存储key/value数据的一种文件。SSTable有以下特点：

• 数据是按key排好序的，顺序读SSTable可以得到有序的数据，多路归并多个SSTable可以得到全局有顺的数据；
• 由于所有写操作写好操作日志即可返回成功，将SSTable写入磁盘一个离线的追加写过程；
• SSTable在写完后就不再修改，最终只会整体的删除。

后两个特点让SSTable特别适合在分布式文件系统上使用。

SSTable的代码在LevelDB中是比较独立的一部分，用户可以跳过数据库直接接口通过TableBuilder/Table类读写SSTable文件。需要注意的是，使用TableBuilder生成SSTable文件时添加的key/value对需要是有序的，这也是LevelDB使用TableBuilder的方式：用户写入数据时先写日志，待内存缓冲区填满后排好序写出SSTable文件。

将数据排好序是为了查找方便。由于SSTable一经写成不再修改，因此索引结构可以做在非常简单的静态结构，无需像数据库那样考虑更新数据时索引维护的问题。在分析内存数据结构和算法时，我们往往关注的是比较次数，因为这直接反应了算法的运行效率。然而在磁盘中查找数据，我们更看重的是读磁盘的次数。从传统的机械硬盘上随机读一块数据，即使只读一个扇区，也要花费至少10毫秒。这个时间称为寻道时间。在这10毫秒时间内，CPU可以进行成千上万次的内存比较操作。因此，无论是采用简单如SSTable的索引，还是是复杂如B树的索引，最终目标都是最小化磁盘寻道次数。

用户写入的key/value对在SSTable中是以一个个block的形式存放的。默认配置的block是4K左右。每个block中存储若干排序后相邻的key和与之对应的value。无论查找block中任何一个key时，都会将一个block完整读出。这是因为寻道时间占整个读磁盘花销的主要部分，读一个扇区和多读几个也区别不大。同时，我们可以整体地将block中的key/value以特别的形式编码（下文详述），以求达到更高的压缩率。此外，由于block中的key是排序后相邻的，在用户的逻辑中也很可能是相关的（例如在有表结构的存储中可能是属于同一行的数据），将block整体做为内存缓存的最小单位也会更有效率。

图1: 数据/索引block在SSTable文件中的位置

图2: 索引结构

索引block和数据block的结构相似，只是value变成了数据block在SSTable文件中的偏移和长度。在查找时（假设未命中缓存），首先从磁盘中读出索引block，然后通过二分查找定位到相应数据block的位置，再从磁盘读出数据block。如此，在一个SSTable中查找一对key/value只需至多两次读盘。当然，一个数据库中往往存储了多个SSTable文件，后续博文将介绍在减少读盘次数上的一些优化。

图3: 采用前缀压缩的block结构，其中”key_000″、”key_010″等是恢复点，”key_001″、”key_002″等采用前缀压缩编码

让我们回头看看block的存储结构。逻辑上一个block可以认为是若干key/value的集合。在实际中为了节省空间，LevelDB采用前缀压缩编码存储key。具体来说，因为同一block中的key是在字典序中相邻的，那么它们就很可能有公共前缀（如上例中的”key_0″、”key_1″等，考虑上层有表结构的存储可能有很长的公共前缀）。在存储key/value对时，我们不需要完整地存储key，而是记录下当前key与上一个key的共同前缀长度和不同部分即可。这样做的负面影响是要匹配到某个key必须顺序遍历先前的所有key。为解决这一问题，在block中并不是所有key都采用这种前缀编码，而是每隔几个key就记录下完整的值。这些key称为恢复点（restart point）。在二分查找时，只需要比较恢复点便可得知大致的范围，再从最接近的恢复点再后遍历即可找到相应的数据。

值得一提的是，在SSTable层面并不处理直接处理序号。在数据库层面，将序号和key一起拼成SSTable层面的key，并指定一个特别的比较器实现多版本的key/value支持（逻辑和MemTable中基本一样：若key相同，序号大的排在前面）。

参考资料：
Table Format