面向不可变存储环境的近似成员查询二级索引

摘要

键值存储系统得益于优异的写入性能被广泛应用于各种Web应用。主流的键值存储系统多利用布隆过滤器优化非主键查询性能，而该方法存在查询效率受数据段数量影响和误判引发的多余数据段访问可能性等不足。为了进一步优化键值系统分析处理的查询能力，针对一次写多次读的数据访问特征，提出了新型二级索引。通过构建全局索引，避免了多过滤器探测引发的查询延迟提高。此外，提出了预探测递归驱逐策略，优化了索引构建效率。与传统方法相比，该索引处理存在数据项查询时能够返回完全正确的数据段编号序列。进一步，该索引基于逻辑链的范围查询方案实现了范围查询。实验结果验证了索引结构的有效性。与基线结构相比，该索引的查询性能提升了约10～50倍。

关键词

二级索引 / 键值数据存储 / 查询优化 / NoSQL / 在线分析处理