SSTable按键排序换来高效合并与稀疏内存索引

针对[[哈希索引配合分段压缩及其无法支持范围查询的局限]]，只需要对段文件格式做一个 看似简单的改变——要求键值对按键排序、且每个键在每个合并后的段里只出现一次——就能 消除哈希索引的两个局限，这种格式称为排序字符串表（SSTable）。SSTable带来两个关键 优势。第一，合并段变得简单高效，即使文件远大于可用内存：用归并排序的思路，并排 读取多个输入段、每次比较各自当前最小的键、把最小的那个写入输出文件，重复这个过程； 如果多个输入段有相同的键，因为一个输入段里的数据整体上一定比另一段更新（假设总是 合并相邻段），直接保留较新段的值、丢弃旧段的值即可，完全不需要把所有键都载入内存。 第二，不再需要在内存里保存所有键的索引：由于键已排序，即使只知道少数几个键（如 handbag和handsome）的偏移量，也能推断出handiwork一定落在这两者之间，可以直接跳转 到handbag的偏移位置往后扫描——内存索引因此可以是稀疏的，每隔几千字节的段文件放一个 索引条目就够了，因为几千字节的范围可以被快速线性扫描完。这个设计的关键洞察是： 排序这个看起来只是”格式约束”的改动，同时解决了合并效率和索引内存占用两个问题，是 一种用一次性排序成本换取后续操作复杂度大幅下降的典型权衡。