SuRF

SuRF是一种查询效率高、压缩比高的字典树（Trie）数据结构，其功能十分简单，提供过滤器的功能。众所周知，BloomFilter被广泛用于单点过滤——用于判断单个key是否存在于集合中。而SuRF的不仅拥有单点过滤功能，还能支持范围查询这个大杀器，即其能根据给出的key范围来判断其是否在集合中。SuRF是一种Trie树结构，Trie树的结构使其能支持范围查询，但传统Trie树所占空间太大，效率低，在数据库里实际运用很少。SuRF的突破创新点是其拥有极限小的空间，其trie树的每个节点平均只需要占10bit空间，而且同时保持了很高的查询性能，构造性能。SuRF团队将SuRF运用到了目前十分受欢迎的NoSQL系统RocksDB之中，在范围查询之中提升了1.5倍~5倍的效率。