Valkey swaps skiplists for B+ trees, cutting sorted set memory overhead by up to 43%

Valkey kills the skiplist, cuts sorted set overhead by up to 43%

Valkey 9.2 replaces the skiplist backing large sorted sets with a 61-way B+ tree variant called fbtree, packing many members into shared nodes instead of one allocation per element. In a 5-million-member test, per-member overhead dropped from 50.3B to 28.5B for sequential inserts (43%) and 32.0B for random ones (36%), saving up to 109 MB. Commands are unchanged, but ZADD and ZREM throughput rose 105% and 76%.

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

    I have to say I was always on the fence about Bill Pugh (Mr Skiplist).

    Some of his concurrency ideas were pretty good but Skip Lists were about the same time I was realizing that theoretical and practical design for performance had diverged and skip lists were a huge cache miss liability.

    It didn't hurt that a few people I was aware had tried them had gone back to something else due to live performance analysis being negative or inconclusive (If you can't prove one thing is better than the other, you use the simpler one, and skiplists are not simple)

  2. jauntywundrkind

    Thanks Bill Pugh for skiplists, worked great for so long. Go terps. https://dl.acm.org/doi/10.1145/78973.78977

  3. tyre

    Tangentially related, the PR sections for the final PR in this feature is quite nice[0].

    There is a reviewing guide with suggested reading order, clear design decisions, and scope boundaries for what is intentionally not included.

    This is the type of thing LLMs are very good at and high ROI for human reviewers.

    [0]: https://github.com/valkey-io/valkey/pull/4206

  4. rsalus

    I've long since moved to the MultiQueue algorithm for CPQs, seems like SkipList has vanishingly few use cases now...

  5. dreamcompiler

    > Every node carries a backward pointer

    Curious. Skiplists don't need back pointers. You can traverse a skiplist backward almost as fast as forward if you keep the "finger" around. The finger is the set of nodes from level-n down to level-0 that point as close to the goal node as possible without going beyond it. The ideal place to keep these nodes is on the stack. To traverse backwards, you do a conventional search for the starting node but every time you go down a pointer level, you push the last pointer on the stack first. Then back traversal becomes stack pops together with appropriate forward recursive calls when you pop back to a pointer that was too far to the left.

    It's easier to convey the idea with code than english but I'm not typing the algorithm with my thumbs into my phone.

More from this day

2026-11-21