Sorted String Table范围查询的工作原理与高效实现方式

SST的范围查询能力完全依托自身的有序存储特性+多层轻量化索引实现，既不需要全表遍历，也不是单纯依赖缓存行命中提升性能，和常见的前缀树索引的设计思路有本质区别。

支撑高效范围查询的核心结构与算法 #

• 块级稀疏索引：SST在磁盘上会按固定大小（LevelDB默认4KB/RocksDB默认可配置）切分为连续存储的数据块，每个块内部的键严格有序。SST文件的尾部会单独维护一组稀疏索引：每个数据块仅存入该块内的最大键，所有块的最大键按块的物理顺序排列，形成有序的索引序列，这部分索引会在SST打开时整体加载到内存。执行范围查询时，仅需在内存的稀疏索引上做二分查找，就能快速定位到查询起点、终点分别落在哪个数据块，即可锁定整个查询范围覆盖的全部数据块，不需要扫描块外的无关内容。
• 单文件级布隆过滤器前置过滤：每个SST的尾部会挂载对应所有键的布隆过滤器，打开SST时加载到内存，如果查询的范围完全不在布隆过滤器覆盖的键集合内，会直接跳过整个文件的读取，减少不必要的IO消耗。
• 块内快速定位结构：每个数据块的头部会维护固定间隔的重启点列表（比如LevelDB默认每16个键设置一个重启点，记录对应键在块内的偏移量），块内查找目标起点时，先在重启点列表上二分，定位到离目标键最近的重启位置，仅从该位置向后顺序扫描最多16个键，就能定位到精确的迭代起点，块内的扫描开销是常数级的。
• 顺序读IO优化：范围查询过程中，被索引锁定的相邻数据块是物理连续存储的，读取时可利用磁盘顺序读的高吞吐特性，不需要逐块发起随机IO，大幅降低读取延迟。

常见认知误区澄清 #

• 不存在“仅通过遍历条目、依赖缓存行命中实现”的情况：如果是无索引的全条目遍历，哪怕有缓存行命中，面对GB级的SST文件查询小范围键的场景，性能也完全无法满足线上需求。实际范围查询的扫描量仅和返回的结果集大小、覆盖的数据块数量正相关，和SST文件的整体大小弱相关：比如1GB的SST中查询仅返回10个键的小范围，实际仅需读取1~2个4KB的数据块，不会触碰文件中99%的无关内容。
• 未使用前缀树作为前置索引的原因：稀疏索引的内存开销远低于全量键构建的前缀树。1GB规模的SST按4KB块切分后，总共仅25万个左右的块，对应的稀疏索引仅存25万个最大键，内存占用仅几MB；如果替换为全量键构建的前缀树，内存开销会上涨数十倍，在磁盘存储类场景下性价比极低。同时稀疏索引的二分查找时间复杂度和前缀树查找持平（都是O(logN)），结构更简单，序列化落盘的成本也更低。

LevelDB/RocksDB范围迭代器的衔接逻辑 #

• 首先从所有层级的SST中，筛选出和查询范围存在重叠的文件，按版本优先级（新数据优先于旧数据）排序，避免读取过期数据。
• 对每个被选中的SST，通过内存中的稀疏索引定位范围起点对应的块，生成对应块的内部迭代器。
• 通过小根堆对多个迭代器的当前键做归并排序，按顺序返回范围内的有效键，迭代过程中顺序读取相邻的连续数据块，不会重复扫描已经加载过的块。

内容的提问来源于stack exchange，提问作者Samuel Squire