随着移动互联网时代的到来,数据量呈爆炸性增长,而数据日渐趋向于非结构化。这些新的趋势给数据存储带来了巨大的挑战。而键值对存储系统由于其简单性、高可扩展性以及高吞吐量等特点,表现出了惊人的优势,并日益成为研究的热点。当前的主流键值对存储系统基于写优化的考虑,大多采用LevelDB所采用的LSM树结构[17]。这一结构虽然大大提升了键值对存储的写入性能,但同时也对读操作造成了一定的影响,尤其是对范围查询而言,会造成大量的无效磁盘读取。许多键值对存储系统利用布隆过滤器来提升单点查询的性能,但是,由于布隆过滤器采用了哈希函数,数据的顺序结构被破坏了,因此无法对范围查询过程进行优化,而这也成为了许多键值对存储系统的短板。针对上述问题,本文以提升键值对存储的范围查询效率为目标,提出了一种面向键值对存储系统的范围过滤器。本文的主要贡献如下:1.针对键值对存储系统的特点和需求,设计并实现了一个范围过滤器。该过滤器主体为二叉树结构,每个节点与一个范围相对应,同时叶节点记录是否有键值对落在与其相对应的范围内。通过这一结构即可实现对范围查询的过滤。随后通过理论性能分析,揭示了过滤效果与内存预算之间的关系。在此基础上,为了能够提升过滤效果,更好地处理不同的存储内容和工作负载,为范围过滤器设计实现了动态调整方案,使其主体二叉树能够根据实际的工作负载进行动态生长和收缩,从而提升过滤效果。2.通过实验对范围过滤器性能进行了评估,发现在多数情况下,范围过滤器能够以较小的内存开销,实现较低的范围查询假阳性率,达到较好的过滤效果。针对实验中观察到的长字符串带来的假阳性率偏高的问题,对范围过滤器进行了一系列的优化。结合一些典型的实际应用场景特点,设计并实现了公共前缀处理机制,以及过滤器自主分裂机制。前者通过对键提取公共前缀的方式,缩小了范围过滤器所需处理键的长度;后者通过使范围过滤器动态地进行分片,进一步提升了提取最大公共前缀的效果,针对性地解决了字符串过长的问题。实验结果表明,这些优化能够大大降低范围查询的假阳性率,显著提升过滤效果。