今天终于写到LevelDB最有意思的部分了。我们知道，在经典的merge-dump系统查询数据，运气差时可能需要访问每个SSTable，才能找到需要的数据。虽然BloomFilter在概率上解决了这一问题，但付出的代价却是与key/value对数据成正比的内存使用量（例如每个key/value对占用两三个比特，主要取决于可以容忍的出错概率）。如果将经典的merge-dump系统比喻成链表的话，LevelDB则使用一种类似搜索树的方式精心排列好SSTable，让查询在树的每一层上只命中一个SSTable，从而极大减少磁盘寻道次数。
我们先从SSTable的产生来源开始说。生成SSTable的途径有两种:
1. MemTable内存满，溢写到磁盘
2. 将旧的SSTable”合并”成新的，优化寻道次数
第一种溢写出来的SSTable是在系统内存耗尽时被迫的写出来的，优化余地不大。LevelDB中的优化是作用在第二种途径产生的SSTable上。传统的merge-dump系统只是简单地选择将几个小的SSTable合并为一个大的，由于SSTable内部是类似B树的索引方式（当然是只读的），实际中最多随机寻道两三次，相比原先的几个小的SSTable可以显著减少寻道次数。
但是大文件带来的问题是下次合并时会不灵活：下次合并时，这个大文件要么整体参与合并，要么整体不参与合并，再也不能像几个小文件那样选择其中的几个放弃另外几个了。尽管有如此不灵活，但考虑到合并带来的好处－－寻道次数一下从线性级变成了对数级，大家仍然会”义无反顾”地选择合并。
LevelDB走了另一条路：从多个文件”合并”到多个文件。SSTable按顺序地存储了很多key/value对，我们可以记下其中最小和小大的key。最小key和最大key组成一个区间，当在用户查询落在这个区间之外（即用户查询的key比SSTable中最小的key还要小、或者比最大的key还大），那么就自然不必在这个SSTable中继续查找。显然，当这个区间范围越小时，这个SSTable也就不容易被无效命中了。LevelDB正是利用这个特点，让每次”合并”产生区间不重叠的多个输出文件，这样一来这些小文件逻辑上与单个大文件无异，又可以增加灵活性，一举两得。
LevelDB将所有SSTable分为7层（level），下文称为第0层至第6层。MemTable溢写生成的SSTable放在第0层。除第0至外，第1至6层中，每层内的SSTable的最小key和最大key区间是不重叠的。这就保证用户查找到第1至6层的SSTable时每层最多只需读一个SSTable。
如何生成这样的文件布局？让我们回到最开始，只有MemTable溢写出的第0层。随着用户不断写入，第0层的文件越来越多，当超过4个时开始第0层到第1层的合并。类似的，当第1层的数据太多时就合并到第2层，依次类推。衡量某层数据多少的标准是，第0层是否多于4个文件，或者第i层数据总量大于(10^i) MB。每次合并向更高一层输出多个区间不重叠的文件。当进行第i层到第i+1层的合并时，如果第i+1层原先也有一些文件存在，那么在发生区间重叠时需要将这些文件一起合并。
LevelDB中所有SSTable都是固定2MB大小。假如用以覆盖key区间为底、占用空间为面积的矩形表示SSTable，应用以上规则不断整理数据，最终会形成上图中布局：每层的文件数和数据量呈指数增长，越高层的文件越偏向瘦高，即单个文件覆盖更小的key区间。
到这里，想必读者应该已经明白LevelDB名字的由来了。
Codingstory 