# Reduce large sorted set memory with a packed B+ tree

> Source: <https://github.com/redis/redis/pull/15635>
> Published: 2026-08-13 11:21:22+00:00

# Reduce large sorted set memory with a packed B+ tree - #15635

[antirez](/antirez)wants to merge 1 commit into

## Conversation

Hi, this is a draft implementation that reimplements large sorted sets by replacing the skiplist and general-purpose dictionary with one packed B+ tree (score ordered) and a compact member index, that is, a specialized hash table.

No changes to RDB / AOF. Memory drops between 45 - 60% in many common use cases. Many operations are now faster, sometimes *much* faster (70% faster). ZSCAN can be slower, but not much slower.

Please tell me if you like this direction, I'll do more QA and refine the PR more.

**AI Disclaimer** This PR was generated with massive AI help.

Note

**High Risk**

Core zset storage and hot paths change across persistence, replication, modules, and defrag; regressions would affect data integrity, memory, and latency at scale despite extensive QA described in the PR.

**Overview**

**Large sorted sets** no longer default to skiplist + dictionary once they exceed listpack limits. They use a new ** OBJ_ENCODING_BTREE** (

`btree`

in `OBJECT ENCODING`

): a score-ordered B+ tree with a compact open-addressing member index (hash tag + leaf id), packed scores in leaves, and **external allocation for members ≥320 bytes** so one huge member does not force a whole-key skiplist fallback.

** zset_btree.c** is wired into the server build;

**routes create/convert/add/del/rank/range/set-ops through the btree API, with skiplist retained for explicit conversion and temporary bulk-command paths.**

`t_zset.c`

**RDB** still writes

`RDB_TYPE_ZSET_2`

; loads large sets via **into btree (or listpack) instead of building skiplist first.**

`zsetAdd`

**AOF rewrite**,

**ZSCAN**,

**active defrag**,

**fork dismiss**,

**modules**(range/scan iterators),

**geo**,

**sort**, and

**DEBUG DIGEST** gain btree branches.

A large ** ZSET_MEMSAVING_ALT_REPORT.md** documents design, benchmarks (~45–60% memory on cited workloads), review fixes (ZSCAN cursor/reply, scan completeness), and follow-ups (direct bulk B+ build, compaction). Observable command results and on-disk types stay compatible; encoding,

`MEMORY USAGE`

, ZSCAN order/cursors, and internal scan behavior can differ within SCAN’s contract.Reviewed by Cursor Bugbot for commit

`5b1e9dd`. Bugbot is set up for automated code reviews on this repo. Configure here.

**reviewed**

[cursor](/apps/cursor)BotAug 13, 2026

###
**
**[cursor](/apps/cursor)
Bot
left a comment

**left a comment**

[cursor](/apps/cursor)Bot

There was a problem hiding this comment.

Cursor Bugbot has reviewed your changes using high effort and found 1 potential issue.

Reviewed by Cursor Bugbot for commit

`5b1e9dd`. Configure here.

[src/module.c](/redis/redis/pull/15635/files/5b1e9dd012b2959093351d6c92160430730b0347#diff-6109c354d7e009093f811238069b581bcb9bdbfc638d7d089814031776801632)

| if (!valid) goto end; | ||
| } | ||
| key->u.zset.current = (void *)(uintptr_t)(rank + 1); | ||
| return 1; |

There was a problem hiding this comment.

### Module iterator ranks go stale

**Medium Severity**

B+ tree module range iteration stores a numeric rank in `current`

. After a module callback deletes or inserts members with a lower rank, that saved rank still looks valid but now names a different element. `RM_ZsetRangeCurrentElement`

can therefore return the wrong member, and `RM_ZsetRangeNext`

/ `RM_ZsetRangePrev`

can skip survivors. Out-of-range ranks end cleanly, but in-range shifted ranks do not.

## Additional Locations (2)

Reviewed by Cursor Bugbot for commit

`5b1e9dd`. Configure here.

[Learn more about bidirectional Unicode characters](https://github.co/hiddenchars)