下图为在一个sstable中查找某个数据项的流程图：

大致流程为：

• 首先判断“文件句柄”cache中是否有指定sstable文件的文件句柄，若存在，则直接使用cache中的句柄；否则打开该sstable文件，按规则读取该文件的元数据，将新打开的句柄存储至cache中；
• 利用sstable中的indexblock进行快速的数据项位置定位，得到该数据项有可能存在的两个datablock；
• 利用index block中的索引信息，首先打开第一个可能的data block；
• 利用filter block中的过滤信息，判断指定的数据项是否存在于该datablock中，若存在，则创建一个迭代器对datablock中的数据进行迭代遍历，寻找数据项；若不存在，则结束该datablock的查找；
• 若在第二个datablock中找到了目标数据，则返回结果；若未查找成功，则返回错误信息；缓存

在leveldb中，使用cache来缓存两类数据：

• sstable文件句柄及其元数据；
• data block中的数据；

因此在打开文件之前，首先判断能够在cache中命中sstable的文件句柄，避免重复读取的开销。

元数据读取

由于sstable复杂的文件组织格式，因此在打开文件后，需要读取必要的元数据，才能访问sstable中的数据。

元数据读取的过程可以分为以下几个步骤：

• 读取文件的最后48字节的利用，即Footer数据；
• 利用meta index block的索引信息读取该部分的内容；
• 遍历meta index block，查看是否存在“有用”的filterblock的索引信息，若有，则记录该索引信息；若没有，则表示当前sstable中不存在任何过滤信息来提高查询效率；数据项的快速定位

一个index block的文件结构示意图如下：

index block是由一系列的键值对组成，每一个键值对表示一个datablock的索引信息。

键值对的key为该data block中数据项key的最大值，value为该datablock的索引信息（offset, length）。

因此若需要查找目标数据项，仅仅需要依次比较indexblock中的这些索引信息，倘若目标数据项的key大于某个datablock中最大的key值，则该datablock中必然不存在目标数据项。故通过这个步骤的优化，可以直接确定目标数据项落在哪个datablock的范围区间内。

注解

值得注意的是，与data block一样，indexblock中的索引信息同样也进行了key值截取，即第二个索引信息的key并不是存储完整的key，而是存储与前一个索引信息的key不共享的部分，区别在于datablock中这种范围的划分粒度为16，而index block中为2 。

也就是说，indexblock连续两条索引信息会被作为一个最小的“比较单元“，在查找的过程中，若第一个索引信息的key小于目标数据项的key，则紧接着会比较第三条索引信息的key。

这就导致最终目标数据项的范围区间为某”两个“data block。

过滤data block

若sstable存有每一个data block的过滤数据，则可以利用这些过滤数据对datablock中的内容进行判断，“确定”目标数据是否存在于data block中。

过滤的原理为：

• 若过滤数据显示目标数据不存在于datablock中，则目标数据一定不存在于data block中；
• 若过滤数据显示目标数据存在于datablock中，则目标数据可能存在于data block中；

具体的原理可能参见《布隆过滤器》。

因此利用过滤数据可以过滤掉部分data block，避免发生无谓的查找。

查找data block

在data block中查找目标数据项是一个简单的迭代遍历过程。虽然datablock中所有数据项都是按序排序的，但是作者并没有采用“二分查找”来提高查找的效率，而是使用了更大的查找单元进行快速定位。

与index block的查找类似，data block中，以16条记录为一个查找单元，若entry1的key小于目标数据项的key，则下一条比较的是entry 17。

可以看到，sstable很多文件格式设计（例如restart point， indexblock，filter block，maxkey）在查找的过程中，都极大地提升了整体的查找效率。