zset 的底层实现是什么？跳表是什么？

直接回答

zset（有序集合）底层有两种编码：元素少且小时用 listpack（压缩列表），元素多后转为 hashtable + skiplist（跳表） 双结构——哈希表负责 O(1) 按成员查分数，跳表负责 O(log N) 按分数排序和范围查询。跳表是在有序链表上加多级索引的数据结构，通过"以空间换时间"把链表的查找从 O(N) 降到 O(log N)。

展开解析

跳表原理：最底层是包含全部元素的有序链表；每个节点以随机概率向上建立更高层"快捷指针"（Redis 中层数按幂次随机：每层晋升概率 1/4，上限 32 层）。查找时从最高层开始向右走，遇到更大的值就下降一层，直到最底层定位，期望复杂度 O(log N)。

Redis 的跳表节点（zskiplistNode）还带两个增强：score 和回退指针（支持 ZREVRANK 反向遍历）、span 跨度（记录每层指针跨越的节点数，从而支持 O(log N) 求排名 ZRANK）。

为什么 Redis 不用平衡树？常考回答：① 跳表实现远比红黑树简单，插入删除只需局部调整，无需旋转/变色；② 范围查询（ZRANGEBYSCORE）在跳表上是天然友好的——定位起点后顺着底层链表顺序走即可，平衡树要做中序遍历；③ 内存占用和 cache 友好性在同等数据量下不差。平均每个节点指针数约 1.33（概率 1/4 时），空间代价可接受。