NEWS

Valkey 9.2 replaces skiplist with B+ tree and cuts sorted set memory by up to 43%

Valkey 9.2 replaces skiplist with B+ tree and cuts sorted set memory by up to 43%
Image: Redação iMasters
News
Reading
5 min
Tables
1
In short

Version 9.2, currently in release candidate stage, replaces the internal structure that orders sorted sets with a B+ tree called fbtree. The result: less memory per member and commands like ZADD and ZREM running noticeably faster.

Anyone running Valkey (the open source fork of Redis maintained by the Linux Foundation) with large sorted sets in production will feel a behind-the-scenes change in version 9.2, now in release candidate stage. In a technical post published on November 16, 2026, engineers Rain Valentine and Dragos Andriciuc detail the replacement of the skiplist, the structure used since the beginning to order sorted sets, with a B+ tree variant called fbtree.

The change is internal and doesn't alter the API: ZADD, ZRANGE, ZSCORE and the rest keep working exactly as before. But anyone operating large sorted sets in memory will notice two practical effects: less RAM consumed per stored member and meaningful throughput gains on write operations.

Why the skiplist weighed so much

Large sorted sets (above the listpack limit) have always used a combination of a hashtable, for O(1) member lookups, with a skiplist, for O(log n) ordered lookups by rank or score. The problem is that the skiplist is a probabilistic structure: each node has a 25% chance of gaining an extra level, which gives an effective branching factor of just 4.

In practice, this means a backward pointer (8 bytes), an average of 1.33 levels of pointers and span values (about 29 bytes), and the score (8 bytes) per node, adding up to roughly 37 bytes of pure overhead before even counting the member string. Worse: each node is a separate allocation, scattered across the heap, and traversing the structure requires a sequence of dependent memory accesses, each one a potential cache miss.

The post cites a 2025 study on concurrent in-memory indexes that measured traditional skiplists with 2.4 to 4.8 times more cache misses than a comparable B-tree, with throughput 2 to 8 times lower in the tested workloads (this isn't a Valkey-specific test, but it illustrates the structural problem).

fbtree: high fanout, fewer memory jumps

fbtree uses a fanout of 61, meaning each node holds up to 61 entries or child pointers, compared to the skiplist's effective factor of 4. This drastically reduces the number of levels to traverse during a lookup and, more importantly, the number of dependent memory jumps.

Three design decisions underpin the gain:

  • Compact data: 512-byte leaf nodes fit up to 61 value pointers, and each entry stores score and member together as a single packed value, eliminating a level of indirection.
  • SIMD-based search: internal nodes store a 4-byte "feature" per child (derived from the member's prefix), allowing multiple candidates to be compared in parallel via SIMD before even fetching the child node from memory.
  • Chained leaves: leaf nodes form a doubly linked list, so range commands like ZRANGE traverse the set without climbing up and down the tree at each step, and reads can advance to the next leaf while processing the current 61 entries.

For operations at the ends of the set, like ZPOPMIN, fbtree caches the leftmost and rightmost leaves, preserving O(1) access as in the skiplist, instead of regressing to O(log n).

The numbers: memory and throughput

In the reference test, inserting 5 million 20-byte members reduced the overhead per member (not counting the data itself) from 50.3 bytes to 28.5 bytes with sequential insertion, a 43% drop, and to 32 bytes with random insertion, a 36% drop. In absolute terms, that represents up to 109 MB saved on the 5-million-member set with sequential insertion, and 92 MB with random insertion.

The command benchmarks, run on a Graviton3 c7g.metal instance with 64 cores, nine I/O threads, and a sorted set of 3 million members, show uneven throughput gains across commands:

CommandWorkloadThroughput gain
ZADDScore update+105%
ZREMRandom 50/50 add/remove+76%
ZCOUNTRange count by score+27%
ZRANKPoint rank lookup+19%
ZRANGE100-element scan by rank+6%
ZRANDMEMBER100 random samples+2%
ZSCOREPoint score lookup+2%
ZRANGEBYSCORE100-element scan by score+1%
ZPOPMINPop + append~0%

The pattern makes sense: ZADD and ZREM reposition elements in the tree, so they directly benefit from the shallower structure with fewer pointer updates. ZSCORE and ZRANDMEMBER, on the other hand, barely change because they depend on the hashtable, not the ordered index, which was the only component replaced.

What changes for those running production

For those administering Valkey instances with large sorted sets (priority queues, leaderboards, score-based rate limiting, proximity indexes), the math is straightforward: less RAM per set means more sets fitting on the same instance, or the possibility of running with less allocated memory. The relative gain is larger on sets with many small members and shrinks as the average member size grows.

There's an operational point to watch: the OBJECT ENCODING command now returns btree instead of skiplist for large sorted sets. Any monitoring, automated test, or observability tool that does a literal match on the string skiplist needs to be updated before the migration. Small sorted sets, which already used the listpack representation, aren't affected at all.

It's worth noting that the command benchmarks were measured on a pull request branch (PR #4206) and weren't re-run against the final merged commit, so the throughput figures should be read as a rough order of magnitude, not as a contractual guarantee for any given workload.

What's still open

Valkey 9.2 remains in release candidate stage, with no GA (general availability) date disclosed in the source. The team's own recommendation is to test the RC with real workloads before the final release, especially if large sorted sets or the ZADD, ZREM, ZRANK, or ZCOUNT commands are critical to the application, and to report any issues found via the project's GitHub issue tracker.

For those already running Redis or Valkey in production with heavy sorted sets, the natural path is to spin up a staging environment with the RC, replay the typical workload, and compare resident memory and ZADD/ZREM latency before and after the encoding switch, rather than relying solely on the numbers published in the post.

Translated from the Brazilian Portuguese original · Read the original