---
title: "Valkey 9.2 drops the skiplist for a B+ tree, cutting sorted-set memory overhead by up to 43%"
url: https://badiyaa.com/valkey-sorted-sets-b-tree-memory/
published: 2026-11-21T06:32:00+00:00
modified: 2026-11-21T06:32:00+00:00
section: Tech
publisher: Badiyaa
---

# Valkey 9.2 drops the skiplist for a B+ tree, cutting sorted-set memory overhead by up to 43%

Valkey 9.2 replaces the skiplist behind large sorted sets with a B+ tree, cutting per-member memory overhead by 36% to 43% in the project’s own tests.

Valkey, the open-source fork of Redis, has thrown out the data structure that ordered its biggest sorted sets for years. Version 9.2 replaces the skiplist with a custom B+ tree, and the project’s own tests show per-member memory overhead falling by 36% to 43%.

Sorted sets are the workhorse behind leaderboards, rate limiters and job queues: every member carries a score, and the database keeps them in order. [The Valkey 9.2 release announcement](https://valkey.io/blog/valkey-9.2-release/), published November 19, puts the memory cut first on its list of changes.

## Why the skiplist had to go

A [skip list](https://en.wikipedia.org/wiki/Skip_list), first described by William Pugh in 1989, stacks “express lane” linked lists on top of an ordered list so searches can hop ahead. It is simple, but each member lives in its own heap allocation tied to others by pointers.

In [the engineering deep dive by Rain Valentine and Dragos Andriciuc](https://valkey.io/blog/from-skiplist-to-b+tree/), the authors tally the bill: a backward pointer, about 1.33 levels of forward pointers and span values, plus an 8-byte score, for roughly 37 bytes per node before the member string itself. Their opening line sums up the problem: “A sorted set can spend more memory describing how its elements are ordered than storing the elements themselves.”

The replacement, called fbtree (Feature B+ Tree), packs up to 61 entries into each node. A [B+ tree](https://en.wikipedia.org/wiki/B%2B_tree) keeps all data in linked leaf nodes and uses a high fanout, which means fewer levels to walk and fewer slow trips to main memory.

## The numbers, and what they mean at scale

In the Valkey team’s test, inserting 5 million 20-byte members in order cut overhead from 50.3 bytes to 28.5 bytes per member. Random-order inserts landed at 32.0 bytes, because they leave more half-empty nodes. That works out to roughly 109 MB and 92 MB saved on that one set.

We scaled that up. The saving is per member, so it grows in a straight line: 21.8 bytes times 100 million members is about 2.18 GB, and the random-insert figure of 18.3 bytes gives about 1.83 GB. For a team renting memory-heavy cloud instances, that is the difference between needing the next size up or not. The relative gain shrinks as members get bigger, since the overhead becomes a smaller slice of each entry.

Speed improved too. On a 64-core Graviton3 machine with a 3-million-member set, score updates through ZADD ran 105% faster and mixed add/remove work through ZREM 76% faster. ZCOUNT rose 27% and ZRANK 19%, while ZSCORE barely moved because it uses the hash table, not the ordered index.

## What changes if you run Valkey

Commands behave the same. The one visible difference is that OBJECT ENCODING reports “btree” instead of “skiplist” for a large sorted set, so any monitoring script or test that checks for the old string needs a one-line update. Small sets below the listpack threshold never used the skiplist and are unaffected.

The release notes flag a separate edge case: ZRANGEBYSCORE and ZCOUNT will now return an error when handed an empty string or a lone “(” as a score limit, where older versions silently treated it as 0. Valkey also advises holding off on new features until you are sure you will not need to downgrade.

Valkey itself was born in 2024, when the Redis company moved its core code away from the BSD license and contributors from Amazon, Google, Alibaba and others forked Redis 7.2.4 under the Linux Foundation, as [Wikipedia’s Valkey history](https://en.wikipedia.org/wiki/Valkey) explains. Badiyaa recently covered a similar open-source database upgrade in [the PostgreSQL 19 release](https://badiyaa.com/postgresql-19-release-repack/) and [how its new repack command works](https://badiyaa.com/postgresql-19-repack-concurrently-explained/).

Valkey 9.2.0 is available now, and the project credits more than one hundred contributors with the release.

## Sources

- [Valkey 9.2 release announcement](https://valkey.io/blog/valkey-9.2-release/), Valkey project (Linux Foundation), 2026

- [Engineering deep dive on replacing the skiplist with fbtree](https://valkey.io/blog/from-skiplist-to-b+tree/), Valkey project (Linux Foundation), 2026

- [Skip list](https://en.wikipedia.org/wiki/Skip_list), Wikipedia, 2026

- [B+ tree](https://en.wikipedia.org/wiki/B%2B_tree), Wikipedia, 2026

- [Valkey](https://en.wikipedia.org/wiki/Valkey), Wikipedia, 2026

*Image: BalticServers.com, CC BY-SA 3.0 via Wikimedia Commons*

*This article was produced with AI assistance and reviewed by our Editorial Desk. [How we work](https://badiyaa.com/editorial-policy/).*
