Valkey 9.2 swaps skiplist for B+ tree, cutting sorted set overhead by up to 43%

A sorted set can spend more memory describing how its elements are ordered than storing the elements themselves. A post on the Valkey project's blog says that in Valkey 9.2 the skiplist behind large sorted sets is replaced by fbtree, short for Feature B+ Tree, a high-fanout B+ tree variant. Valkey 9.2 is currently in release-candidate testing.

Why the skiplist had to go. Sorted sets that exceed the listpack threshold are backed by a skiplist paired with a hashtable. The hashtable gives O(1) lookups by member; the skiplist gives O(log n) lookups by rank or score. Smaller sorted sets use a compact listpack and are unaffected. The skiplist holds one element per node, each a separate allocation connected by pointers. Every node carries an 8B backward pointer plus an average of 1.33 levels of forward pointers and span values (each node has a 25% chance of gaining another level). Each level costs 8B for the pointer and 8B for the span, which the post puts at around 29B of pointer and span overhead per node. Add the 8B score and the total is roughly 37B per node before the member string.

The second problem is cache misses. Because each node is scattered across the heap and each step decides where the next one goes, the fetches are dependent, and each can mean a round trip through the memory hierarchy. As a rough illustration, the post says an L1 cache hit can take about 1 ns while a DRAM access can take around 100 ns. It cites a 2025 study of concurrent in-memory indexes in which, on its tested workloads, traditional skiplists had roughly 2.4-4.8x more cache misses than a comparable B-tree, with 2-8x lower throughput. That study tested other data structure implementations, not Valkey.

How fbtree works. It uses a 61-way fanout: each node holds up to 61 entries or child pointers. Nodes are sized to fit jemalloc allocation classes without wasting space. A 512-byte leaf holds up to 61 value pointers, so 61 members share one node instead of each having its own. Score and member are stored together as one packed value: the normalized 8-byte score followed by the member bytes, which keeps comparison data together and removes a level of pointer indirection. The skiplist's 25%-per-level rule gives an effective branching factor of about 4, against 61 for fbtree. Both keep O(log n) search, but the tree has far fewer levels to walk.

The post lists several optimizations. Inner nodes store each child's anchor (the largest member in that child) with a four-byte feature, plus the shared prefix stored separately. The implementation compares the features in parallel with SIMD, often picking the right child before fetching it; if features do not uniquely identify a child, they still narrow the range for a full binary search. Leaves are linked in a doubly-linked list, so range commands such as ZRANGE move from leaf to leaf without climbing back up, and the CPU can work on 61 items while fetching the next leaf. The leftmost and rightmost leaves are cached, so finding them is O(1) as in a skiplist, which keeps pop and append operations at parity rather than regressing. Range deletions remove a contiguous run of members without rebuilding the surrounding structure.

What changes for users. Functionally, nothing: commands and behavior are unchanged. The one visible difference is that OBJECT ENCODING returns btree instead of skiplist for a large sorted set, so monitoring, tests or tooling that check for the literal string skiplist need updating.

Memory results. The comparison covers only the ordered index, with the hashtable and member embedding unchanged. With 5 million 20-byte members inserted sequentially, per-member overhead excluding the member data fell from 50.3B to 28.5B, a 43% reduction. With the same members inserted in random order it fell from 50.3B to 32.0B, a 36% reduction; the post attributes the smaller gain to random insertion leaving more partially filled nodes. That is roughly 109 MB saved with sequential inserts and 92 MB with random inserts on the 5-million-member set. Because the savings are per member rather than per byte stored, the relative reduction in total memory is largest for sets with many small members and shrinks as member size grows.

Command performance. These benchmarks ran on a Graviton3 c7g.metal system with 64 cores, nine I/O threads, a pipeline depth of 10 and a 3-million-member sorted set. Each test was repeated five times, with confidence intervals of 2% or less for all commands except ZRANDMEMBER. They were measured on the pull request's branch (PR #4206) and not rerun for the merged commit. ZADD and ZREM gain the most, with throughput up 105% and 76%, because they reposition elements and benefit from the shallower tree and fewer pointer updates. Range operations gain less, since once traversal is cheap, producing and returning the elements dominates the cost. ZSCORE and ZRANDMEMBER barely move because they use the hashtable, not the ordered index. The post says fbtree was repeatedly benchmarked against the skiplist through the full server, with optimizations added until it matched or exceeded the skiplist across the tested sorted set commands.

The post closes by asking readers to try the 9.2 release candidate with real workloads before GA, especially if large sorted sets or commands such as ZADD, ZREM, ZRANK or ZCOUNT matter to them, and to open an issue with anything they find.

Key facts

  • Valkey 9.2, currently in release-candidate testing, replaces the skiplist behind large sorted sets with fbtree, a 61-way B+ tree variant.
  • In a 5-million-member test, per-member overhead of the ordered index fell from 50.3B to 28.5B with sequential inserts (43%) and to 32.0B with random inserts (36%), saving roughly 109 MB and 92 MB.
  • In a separate 3-million-member benchmark on Graviton3, ZADD throughput rose 105% and ZREM 76%; ZSCORE and ZRANDMEMBER barely changed because they use the hashtable.
  • Commands and behavior are unchanged; the visible difference is that OBJECT ENCODING returns btree instead of skiplist for large sorted sets.
  • The command benchmarks were run on the PR branch and not rerun for the merged commit; the post asks users to test the release candidate before GA.

Why it matters

Sorted sets are a core Valkey data type, and the post's opening claim is that the ordering structure can cost more memory than the data it orders. The old skiplist spent roughly 37B per node before the member string, and each node was a separate allocation reached through dependent fetches. Swapping it for a structure that packs up to 61 members per node attacks both the memory bill and the cache behavior, without changing the commands people use. Both structures keep O(log n) search; the gain comes from layout and fewer levels, not from a better big-O.

Who it affects

Anyone running Valkey with large sorted sets, meaning those above the listpack threshold. Small sorted sets that use the listpack encoding are unaffected. The post says savings are largest for sets with many small members and shrink as member size grows. Teams with monitoring, tests or tooling that check for the literal string skiplist in OBJECT ENCODING output will see btree instead and need to update.

How to use it

There is nothing to switch on: the change is internal to Valkey 9.2. The post asks users to try the 9.2 release candidate with their real workload before GA, especially if large sorted sets or commands such as ZADD, ZREM, ZRANK or ZCOUNT matter, and to open an issue with anything they find. Check any tooling that matches the string skiplist in OBJECT ENCODING.

How solid is it

This is a first-party post from the Valkey project describing its own work, with concrete figures and test setups: 5 million 20-byte members for memory, and a Graviton3 c7g.metal system with 64 cores, nine I/O threads, pipeline depth 10 and a 3-million-member set for throughput. Each throughput test was repeated five times with confidence intervals of 2% or less, except for ZRANDMEMBER. The post says it benchmarked through the full server, adding optimizations until fbtree matched or exceeded the skiplist on the tested commands. No independent verification is cited.

Risks and caveats

The throughput figures were measured on the PR branch and not rerun for the merged commit. The memory and throughput numbers come from different tests (5 million versus 3 million members), and the post does not state the hardware for the memory test. The 36-43% figure applies to per-member overhead of the ordered index only; the post gives no percentage for total memory including member data. Random inserts gave a smaller saving than sequential ones because of partially filled nodes. The 2.4-4.8x cache-miss and 2-8x throughput figures come from a 2025 study of other implementations, not from Valkey. The post gives only ZADD and ZREM throughput numbers in its text, and 9.2 is still a release candidate.

“A sorted set can spend more memory describing how its elements are ordered than storing the elements themselves.”

— Valkey blog, From Skiplists to B+ Trees: Making Valkey Sorted Sets More Memory Efficient