RocksDB 的范围查询是如何优化的?

MySQL 的存储引擎除了最常用的是 InnoDB 引擎之外还有一个 MyRocks 引擎也经常会用到，它是基于 RocksDB 开发的一套存储引擎，比 InnoDB 性能要高出 N 倍。

在索引实现上，InnoDB 的索引使用  B+ 树实现，B+ 树的叶子节点上存储了索引的 key，所有的叶子结点使用指针串了起来，非常易于索引的遍历操作。比如下面这个语句（key1 字段加了索引）的范围查询就可以很好的利用这个特性

select key1 from t where key1 > 'abc'and key1 < 'def'

但是 MyRocks 的索引实现不一样，MyRocks 的索引使用 LSM Tree 来实现，通常 LSM Tree 都不支持高效的范围遍历。原因在于 LSM Tree 是多层结构 —— 内存里的 MemTable 和磁盘上的 7 层 SST 文件，范围遍历需要对内存里的多个 MemTable 和这磁盘上的 7 层文件都需要读取后 Merge 在一起才能拿到最终的范围遍历的结果。如果查询范围比较窄，其中 0 层文件可能需要全部读取，其它 6 层通常只需要读取一个文件，因为 0 层文件的多个文件 Key 之间是有重叠的，而其它 6 层中每层的多个文件之间是严格根据 Key 范围切割的。即使对应 SST 文件里面不存在目标范围的 Key，这样的磁盘读取还是不可避免。

我们知道 RocksDB 磁盘上的每个SST 文件里面里面都存了一个布隆过滤器，布隆过滤器的内容通常是缓存（固定）在内存中的。如果布隆过滤器能帮我们提前把查询范围过滤掉，判断出目标 SST 文件是否存在目标查询范围，这样就可以减少磁盘读取了。

但问题是布隆过滤器也是不存在范围查询的能力的，通常也只能判断一下过滤器中是否存在某个 Key。为了解决这个问题，RocksDB 引入了 prefix_extractor ，它可以很好的解决这个难题。那这个 prefix_extractor 又是个什么高深的技术呢？其实也很简单，它就是 prefix bloom filter。

这个「前缀布隆过滤器」 Add 进来的 Key 不再是原来的 Key，而是 Key 的固定长度的前缀，它带来的好处之一是布隆过滤器占用的空间变小了，坏处是误判率也会跟着提高了一点。假设前缀长度是 3，那么把 abcd 这个 Key 加进去后会认为 abce 也在里面，因为它们共享了 abc 这个前缀。这省下来的空间可以用来存储一个附加的数据结构 —— Key 前缀 的有序集合，它里面容纳了所有的 Key 前缀的值。通过这个有序的 Key 前缀集合可以快速判断出目标范围是否存在于当前的 SST 文件中。

和布隆过滤器的数据一样，这个 Key 前缀的有序集合也是缓存（固定）在内存中的。因为单个  SST 文件的 Key 数量是有限的，前缀设置的比较短的话，对应的的前缀数量也会非常少，消耗的内存就可以忽略不计了。

聪明的同学可能想到了，这个前缀的长度取多少比较合适呢？要是用户的索引字段值上自带了前缀字符串，那切割出来的前缀有可能完全一样，这前缀布隆过滤器岂不是要形同虚设么？