← Back to BLACKWIRE EMBER BUREAU MEMORY EFFICIENCY Diagram comparing skiplist node layout with fbtree leaf node packing

The fbtree packs up to 61 entries into a single leaf, dramatically reducing pointer overhead versus the traditional skiplist.

VALKEY REPLACES SKIPLIST WITH B+ TREE, CUTS MEMORY OVERHEAD 43%

*Valkey 9.2 swaps its classic skiplist for a high‑fanout B+ tree variant called fbtree. The change trims per‑member memory use by up to 43% and reshapes cache behavior. The shift matters for any deployment that leans on large sorted sets.*

By EMBER Bureau - BLACKWIRE  |  November 21, 2026, 09:00 CET  |  Valkey, B+ tree, skiplist, memory overhead, in-memory database

Valkey announced a fundamental overhaul of its sorted‑set implementation in version 9.2. The long‑standing skiplist, paired with a hashtable, has been supplanted by a high‑fanout B+ tree variant dubbed fbtree. The change targets the memory bloat that plagues large sorted sets, where each element’s ordering metadata can outweigh the element itself. By redesigning the underlying index, Valkey promises up to a 43% reduction in per‑member overhead, translating to over a hundred megabytes saved in a five‑million‑member test. The upgrade arrives as in‑memory databases face mounting pressure to squeeze performance out of ever‑larger datasets while keeping hardware costs in check.

Why the skiplist became a liability

Valkey’s sorted sets larger than the listpack threshold rely on a skiplist paired with a hashtable. The hashtable gives O(1) member lookups; the skiplist supplies O(log n) rank or score queries. Each skiplist node lives in its own heap allocation, carrying an 8‑byte backward pointer, an average of 1.33 forward pointers, and a span value per level. With a 25% chance of gaining another level, each level adds 8 bytes for the pointer and 8 bytes for the span, totaling roughly 29 bytes of pointer and span overhead per node. Adding the 8‑byte score pushes raw overhead to about 37 bytes per node before the member string. This scattered layout inflates memory consumption and forces frequent, dependent cache fetches.

What is the fbtree and how does it work?

The fbtree—short for Feature B+ Tree—replaces the skiplist with a 61‑way fanout structure. Each node can hold up to 61 entries or child pointers, fitting neatly into jemalloc allocation classes: a 512‑byte leaf stores 61 value pointers, while inner nodes on 32‑bit builds round up to a 1280‑byte class. fbtree packs the normalized 8‑byte score together with the member bytes, eliminating a level of indirection. Leaf nodes link in a doubly‑linked list, enabling range scans without climbing back up the tree. Inner nodes store a four‑byte feature alongside each anchor, allowing SIMD‑parallel comparisons that often resolve the child selection before fetching the child node itself. The design retains O(log n) search complexity but with far fewer levels than the skiplist’s effective branching factor of about 4.

The fbtree slashes per‑member overhead by up to 43%, saving 109 MB on a 5‑million‑member set.

How does the new structure affect performance?

In a 5‑million‑member benchmark, fbtree cut per‑member memory overhead by 36–43%, saving up to 109 MB. The high fanout reduces pointer overhead dramatically: 61 members share a single leaf instead of each owning its own node. Fewer nodes mean fewer dependent memory accesses, which translates into fewer cache misses. A 2025 study of concurrent in‑memory indexes reported traditional skiplists suffering 2.4–4.8× more cache misses than comparable B‑trees, with 2–8× lower throughput. While the study did not test Valkey directly, the same principles apply. Modern CPUs can fetch adjacent cache lines efficiently; a 512‑byte leaf spans only a few lines, allowing prefetchers to load data in bulk. SIMD‑driven feature checks further trim the number of memory fetches per lookup.

What does this mean for the in‑memory database market?

Valkey’s move signals that memory efficiency is becoming a competitive edge in the in‑memory database space. Large sorted sets are common in real‑time analytics, leaderboards, and recommendation engines. Reducing overhead by up to 43% can lower infrastructure costs and improve latency, especially under heavy read‑write loads. The fbtree’s design also showcases how tailoring classic data structures to a specific workload—through packed values, SIMD features, and cache‑friendly node sizing—can yield measurable gains without altering the external API. Other vendors may follow suit, revisiting their own index implementations to stay viable in environments where every megabyte and nanosecond counts.

Frequently asked questions

How much memory does the new fbtree save compared to the skiplist?

In a 5‑million‑member test, fbtree reduces per‑member overhead by 36–43%, saving up to 109 MB.

What is the fanout of Valkey’s fbtree and why does it matter?

fbtree uses a 61‑way fanout, allowing up to 61 members to share a single node, which cuts pointer overhead and cache misses compared to the skiplist’s effective branching factor of about 4.

How does fbtree improve cache performance?

By storing many entries contiguously in 512‑byte leaf nodes and using SIMD‑enabled feature comparisons, fbtree reduces dependent memory fetches and the number of cache lines traversed, addressing the skiplist’s higher cache‑miss rate.

Valkey’s fbtree demonstrates that even mature data structures can be re‑engineered for modern hardware constraints. By marrying a 61‑way fanout with SIMD‑friendly features and contiguous leaf storage, the database trims memory waste and accelerates cache access. As workloads continue to scale, the industry will watch closely to see whether competitors adopt similar B+ tree strategies or devise new hybrids. The bottom line: memory‑efficient indexing is no longer optional—it’s a prerequisite for staying competitive in the high‑speed, data‑intensive arena.

Sources: Hacker News – Valkey kills the skiplist, cuts sorted set overhead by up to 43%