在数据库管理系统中查找某些关键字会导致很大的磁盘I/O开销，针对这一问题，通常会使用一个内存开销小并且常驻内存的过滤器来检测该关键字是否存。比如现在常用的bloom过滤器对判断某个key是否存在是非常高效的，其能用极少的空间（与key长度无关），极低的出错概率判断key的存在性。
现有的过滤器都仅仅支持point query，例如现在RocksDB里面有一张学生表，现在要做查询，找出年龄等于18岁的学术，我们可以通过在每一个SSTable（LSM Tree的分层结构）上加一个布隆过滤器减少磁盘IO，从而加速查找过程。但是现在查询请求变成了学生表中是否含有年龄段在22到25之间的学生，这个时候布隆过滤器就没有办法工作了。
本篇论文的核心是提出了一种基于succinct data structure的trie树，同时对该树进行合理的编码，从而降低占用内存的大小，同时保留查询能力，既支持point query，也支持range quey。
2. SUCCINCT RANGE FILTERS为了在集合中查找字符串，首先想到的是Trie，一颗不做任何处理的Trie树如下图所示
从起始节点到最底层的叶子节点存储了一个完整的key，所以它是完全精确的，在集合中查找某个字符串的时候，不会出现关键字是否存在判别错误的情况。但是它有一个缺点就是占用的内存空间太大。为了让这棵Trie树变小，就要去截断一部分后缀，只会保存最短的前缀且这个前缀可以与集合中其他元素不同，这棵Trie树被称为Surf-Base，如图所示
但是Surf-Base有个问题就是如果现在有一个字符串的前缀和树中存储的字符串前缀相同，但它又不在给定的字符串集合中，这时判别集合中是否有关键字的FPR(False Positive Rate)就会很高，比如通过上图右部的SuRF-Base去判别集合中SIGMETRIC是否存在，就会认为该字符串存在于该集合中，就会得到一种错误信息。为了降低FPR，作者对原来的SuRF-Base结构做了改进，提出了SuRF-Hash、SuRF-Real以及SuRF-Mixed三种结构。
SuRF-Hash(SuRF with Hashed Key Suffixes)：针对SuRF-Base有很高的FPR，在将集合中的关键字加入到SuRF-Base树的同时，也会对关键字进行hash计算，将得到的hash值的n个bit存储到最终的value中，当进行关键字的查找时，不仅要在Trie树上面查找，还要对比hash值。这种结构有利于Point查询，且保存的hash值每多一位，做Point quey的FPR就会减少一半。但是这个结构并不会对Range query有任何帮助，不能减少range query的FPR。
SuRF-Real(SuRF with Real Key Suffixes)：和SuRF with Hashed Key Suffixes不同，SuRF-Real将存储的hash值的n个bit换成了真实key（即value中存放着key），例如上图的右部分表示添加了8bit的suffixes，这样虽然同时增强了Point query和Range query，但是关键字的区分度还是不高，在point查询下, 它的FPR比SuRF-Hash要高。
SuRF-Mixed(SuRF with Mixed Key Suffixes)：为了同时享受Hash和Real两种方式的优点, Mixed模式就是将两种方式混合使用，存储的value中有一部分是real key，另一部分是hashed key，混合的比例可以根据数据分布进行调节来获得最好的效果。如下图是一个案例：
