SuRF，全称为Succinct Range Filter，是一个高效的压缩型范围过滤器。

Succinct是一种编码算法，支持在编码后数据上直接进行查询。它使用0和1来编码数据。

SuRF的核心数据结构是Fast Succinct Tries，它是一种支持点和范围查询的极致压缩树结构。它将树分为热点和冷点两部分，对热点部分使用密集编码，对冷点部分使用稀疏编码。

在SuRF中，使用LOUDS方法来表示树结构。每个节点有几个儿子就写几个1，最后加上一个0。通过这种方式，可以得到node_id和position的对应关系。

通过基本操作，SuRF扩展了更多的功能。它还提出了几种操作，如D-Labels、D-HasChild、D-IsPrefixKey和D-Values等。

SuRF提出了四种裁剪方式：Base、Hash、Real和Mix，用于减少空间需求。Base方式裁剪所有无分支的链，最节省空间，但误判率较高。

在数据结构测试中，使用Yahoo生成工具生成int64和email数据，并同时生成查询。数据量分别为5000w和2500w，大部分范围查询命中50-100个。

SuRF的误判率比同等大小的bloom filter略高，但通过调整bits per key可以降低误判率。在速度方面，SuRF与bloom filter在int64数据上的性能相当，但在字符串场景下速度会慢约60%。

RocksDB测试中，SuRF在point query中的吞吐量和IO性能不如bloom filter，但在open-seek和closed-seek查询中，SuRF的吞吐量和IO性能优于bloom filter，随着空结果的增加，效果更明显。

为了更好地理解SuRF的构成，官方提供了demo，地址为：SuRF Demo。