如何维护LSM-tree中的sparse index以保证索引键偏移量递增

你提到的疑问本质是混淆了稀疏索引的绑定粒度，LSM-tree的原生设计本身就避开了跨段全局排序的问题，具体实现规则如下：

• 稀疏索引是和单个SSTable段一一绑定的，不存在全局统一的单份稀疏索引。每次内存memtable写满刷入磁盘生成新SSTable时，会同步生成对应这个段的专属稀疏索引。由于SSTable内部的key是严格有序写入的，所以对应索引里记录的key天然按从小到大排列，关联的磁盘文件偏移量自然也是严格递增的，完全不需要考虑不同段之间的key顺序问题。
• 读取请求触发索引查询时，会按段的新旧顺序逐个检索：先查内存中的memtable，没找到就从最新生成的SSTable开始，逐个查询每个段自己的稀疏索引，定位到当前段内key可能存在的偏移区间后，读取磁盘对应区间的内容校验，找不到就继续查询更早生成的旧段的索引即可。
• Compaction操作不会引发索引混乱：多个旧段合并生成新的有序SSTable时，会直接为新段生成全新的专属稀疏索引，被合并的几个旧段对应的索引会直接从内存中移除，不涉及其他未参与合并段的索引变更，自然不会出现索引偏移量错乱的问题。

配图如下：

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