RocksDB

For workloads with uniformly distributed keys, RocksDB now supports interpolation search for SST index blocks as an alternative to the default binary search.

The idea

Binary search always splits the remaining range in half:

1 mid = low + (high - low) / 2

That’s Θ(log n) probes regardless of the data. Interpolation search instead estimates w...