# Interpolation search for SST index blocks

DevFeed: [Interpolation search for SST index blocks](<https://devfeed.tech/articles/interpolation-search-for-sst-index-blocks-22398.md>)

Original publisher: [Read original article](<http://rocksdb.org/blog/2026/05/04/interpolation-search.html>)

Author: Josh Kang

Published: 2026-05-04T00:00:00Z

Content type: article

Language: en

Sources: [RocksDB](<https://devfeed.tech/sources/rocksdb.md>)

Topics: [rocksdb](<https://devfeed.tech/topics/rocksdb.md>), [Algorithm](<https://devfeed.tech/topics/algorithm.md>)

Tags: [algorithm](<https://devfeed.tech/tags/algorithm.md>), [blog](<https://devfeed.tech/tags/blog.md>), [rocksdb](<https://devfeed.tech/tags/rocksdb.md>)

## AI overview

RocksDB adds interpolation search for SST index blocks as an alternative to binary search, targeting fewer probes for uniformly distributed keys. The article explains key conversion, fallback behavior, configuration, and automatic per-block selection based on a uniformity hint.

## Source excerpt

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 where the target should land based on its value relative to the current boundaries: 1 probe = low + (target - key[low]) * (high - low) / (key[high] - key[low]) On uniformly distributed keys, that's expected O(log log n) probes. The canonical example: for an index block with restart keys 0, 1, 2, ..., 1023 and a seek for 900, binary search needs about 10 hops; interpolation search lands on it in 1. The catch is that pure interpolation search degrades to O(n) on badly skewed data. Turning a key into a number The interpolation formula needs numeric values, but index keys are variable-length byte slices. RocksDB extracts a uint64_t per key by reading the first 8 bytes after the common prefix shared by the block's boundary keys, in big-endian, and zero-pads to the right if the remaining bytes are too short. 1 2 3 4 5 6 7 8 9 inline uint64_t ReadBe64FromKey(Slice s, bool is_user_key, size_t offset) { // ... strip internal seq/type bytes if needed ... if (s.size() - offset >= 8) { uint64_t val; memcpy(&val, s.data() + offset, sizeof(val)); return port::kLittleEndian ? EndianSwapValue(val) : val; } // pad short tails with zeros on the right (preserves bytewise order) } Big-endian + zero-pad preserves bytewise ordering, so the linear interpolation formula stays consistent with the comparator. This is also why the feature requires BytewiseComparator. Two distinct keys can still collapse to the same uint64_t once you go past the first 8 non-shared bytes. To avoid a divide-by-zero, we simply fall back to binary search in that case. How to enable it To force interpolation search on every index block: 1 2 3 rocksdb::BlockBasedTableOptions table_