范围过滤器是一类紧凑的概率数据结构，用于近似判断查询区间是否为空。它们在键值存储等场景中广泛使用，能够快速排除查询区间内不存在的键，从而避免不必要的磁盘查找。然而，现有的范围过滤器普遍存在三大缺陷：
- 无法提供明确的误报率或性能保证；
- 不支持可变长度的键和查询区间；
- 不支持动态更新。\ \ 我们提出 Diva，它是首个同时克服上述所有问题的范围过滤器。Diva 通过对数据集进行抽样，将抽样键存入缓存友好的 Trie 中。对于抽样键之间的键，Diva 通过去除最长公共前缀（LCP）并截断后缀，只保留中间的若干位（即 infix），以在排序后仍能唯一区分这些键。\ \ 这些 infix 被存放在支持常数时间插入的动态数据块中，数据块在需要插入或扩容时会被拆分。范围查询时，Diva 先遍历 Trie，随后检查目标区间是否包含相应的 infix，从而判断区间是否可能非空。我们在理论上证明，针对多数真实数据分布，Diva 在内存占用与误报率之间达到了最佳的权衡。\ \ 为了进一步提升在更广泛工作负载下的表现，我们在 Diva 的基础上构建了 Diva++。Diva++ 通过保持顺序的熵编码消除 infix 之间的冗余，然后去除所有完全相同的 infix，并利用释放出的空间在紧凑的二进制 Trie 中存储原始键的更多位。实验结果显示，Diva 与 Diva++ 在真实数据集上的误报率与最先进的范围过滤器持平，同时支持动态更新以及可变长度的键和值查询。\ \ 博主点评：Diva++ 的设计巧妙地结合了 Trie 的缓存友好性和熵编码的压缩优势，在保持低误报率的同时实现了动态性和可变长度支持，值得在实际系统中进一步探索与部署。