有序集合既要按 score 排序又要按成员查找,Redis 为何选择「跳表 + 哈希表(或 listpack)」的组合,而不是红黑树?
编码组成:元素少且小时用 listpack(紧凑);元素多时升级为「跳表 skiplist + 字典」双结构——字典以 member 查 score(O(1)),跳表维护有序以支持范围遍历。
为何不用平衡树:跳表的 range 操作(ZRANGEBYSCORE、排名)只需顺着前向指针走,实现简单、范围扫描效率高;红黑树做区间遍历需中序且缓存局部性更差。
范围与排名优势:跳表每层是链表,按 score 区间取 TopN、计算排名(ZRANK)非常自然,平均 O(log n);且插入/删除不需像平衡树那样频繁旋转,代码更直观。
代价:跳表平均空间略高于平衡树(多级指针),但工程收益(范围查询 + 实现简单)明显占优,因此成为 ZSet 主选。
题目与答案就在本页;收藏、批注和错题重练在应用内