Reduce large sorted set memory with a packed B+ tree

Redis maintainer antirez proposed a draft pull request (#15635) that reimplements large sorted sets with a packed B+ tree, replacing the skiplist and dictionary to cut memory usage by 45–60% and speed up many operations by up to 70%, while keeping RDB/AOF formats unchanged. The PR, generated with AI assistance, is flagged as high risk because it alters core zset storage and hot paths across persistence, replication, modules, and defrag; Cursor Bugbot's automated review flagged a medium-severity issue where module iterator ranks can go stale after deletions or insertions.

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