深度拆解 Redis ZSet 底层实现：从“紧凑排队”到“多级瞬移”

在 Redis 的世界里为了把性能和内存利用率压榨到极致底层实现往往是“看人下菜碟”。今天咱们就揭开 ZSet 的底裤看看它到底是怎么从“紧凑排队”进化到“多级瞬移”的。一、 是什么ZSet 的“两副面孔”首先纠正一个小插曲ZSet有序集合是Redis的核心数据结构不是 MyBatis 的MyBatis 主要是做 ORM 映射。ZSet 最牛的地方在于它既能像Hash一样保证成员Member的唯一性又能给每个成员带个“分数值”Score并让它们自动排序。为了实现这个效果Redis 会根据数据量的大小在底层偷偷切换两套皮肤压缩列表 (ZipList / Listpack)像是一辆挤得满满当当的公交车。跳表 (SkipList) 哈希表 (Dict)像是一座带多部高速电梯的摩天大楼。底层逻辑当数据量小的时候内存最贵我们用“紧凑排列”换空间当数据量大的时候速度最贵我们用“空间索引”换时间。二、 怎么用极简实战别光说不练咱们直接看在代码里怎么操作它顺便看看它是怎么变换“皮肤”的。Javaimport redis.clients.jedis.Jedis; public class ZSetDemo { public static void main(String[] args) { // 1. 初始化连接假设本地已开启 Redis try (Jedis jedis new Jedis(127.0.0.1, 6379)) { String key rank:player; jedis.del(key); // 2. 插入数据member 是玩家 IDscore 是战力值 jedis.zadd(key, 100.0, Uzi); jedis.zadd(key, 99.0, Faker); jedis.zadd(key, 95.0, Rookie); // 3. 查看底层编码格式 (重点细节) System.out.println(当前底层编码: jedis.objectEncoding(key)); // 4. 获取前两名按分数从高到低 System.out.println(战力榜 Top 2:); jedis.zrevrangeWithScores(key, 0, 1).forEach(tuple - { System.out.println(tuple.getElement() - tuple.getScore()); }); } catch (Exception e) { e.printStackTrace(); } } } /* 运行输出 当前底层编码: ziplist (注Redis 7.0 可能会显示 listpack) 战力榜 Top 2: Uzi - 100.0 Faker - 99.0 */三、 重点细节深挖底层原理1. 压缩列表ZipList空间守财奴当你的 ZSet 满足以下两个条件时Redis 会使用 ZipList元素数量少默认 128 个。每个元素的长度短默认 64 字节。物理形态它在内存里是一块连续的字节数组。每个节点挨在一起不存储指向下一个节点的指针省下了 8 字节的指针空间。痛点找元素得从头往后挨个排查$O(N)$。但在数据量极小时CPU 缓存命中率极高这点耗时几乎可以忽略不计。2. 跳表SkipList空间换时间的艺术一旦数据多了ZipList 的 $O(N)$ 查找就会让 Redis 这种单线程架构慢得像蜗牛。这时候ZSet 会自动“进化”为跳表。物理形态多级索引跳表在普通链表的基础上随机向上提取了几层“索引”。瞬移查找找 100 号元素先从顶层大跨步跳发现跳过了再往下层切。这就像坐直达电梯先到 50 层再换乘到 55 层。时间复杂度平均 $O(\log N)$性能媲美平衡树但实现起来比红黑树简单得多。3. 为什么还配了一个 Dict哈希表跳表虽然找“范围”很快比如找 80-100 分的人但如果你只想查“Faker 多少分”跳表还是要 $O(\log N)$。Redis 追求极致所以额外配了一个Dict保存了Member - Score的映射直接把查询单个元素分数的复杂度降到了$O(1)$。四、 深度硬核跳表到底是怎样炼成的如果说平衡树如红黑树是靠复杂的旋转逻辑来维持平衡那跳表就是靠**掷硬币随机概率**来打天下。1. 结构拆解给链表装上“高速公路”普通的链表Level 0就像是一条每站必停的慢车轨道。我们要找第 100 个节点得从第 1 个老老实实数过去。跳表的做法是向上加层。L0 层原链表包含所有元素。L1 层一级索引每隔一个节点提拔一个“课代表”。L2 层二级索引在 L1 的基础上再提拔课代表。通俗类比这就像你在大城市找路。L2 层是大区地图上海 - 北京L1 层是街道地图朝阳区 - 海淀区L0 层是具体的门牌号。你先在大地图上瞬移到了附近再下站。2. 搜索逻辑从左上角开始的“Z字形”下楼梯跳表的查询逻辑非常简洁从顶层开始能往右走就往右走右边大了就往下走。从当前层的Head出发。比较右边节点的值如果右边 目标直接跳过去跳过了一大堆节点。如果右边 目标或右边为空对不起跳过头了原地下一层。重复上述过程直到在 L0 层找到目标或者没找到。由于每一层都过滤了大量的无效节点查找的时间复杂度直接从 $O(N)$ 砍到了 $O(\log N)$。3. 插入的灵魂随机层高Random Level这是跳表最精妙的地方。插入一个新元素时它到底该出现在哪几层索引里红黑树的做法插入后看颜色、看左右不平衡就旋转。太烧脑了跳表的做法“听天由命”。每插入一个新节点程序会调用一个随机函数类似掷硬币。50% 的概率停留在 L0 层。25% 的概率长到 L1 层。12.5% 的概率长到 L2 层……以此类推直到达到 Redis 规定的最高层通常是 32 或 64。为什么这么做从宏观上看这种概率分布保证了高层节点大约是底层节点的 $1/2$或者 $1/4$自然而然地形成了类似二分查找的结构完全不需要复杂的平衡算法五、 代码实现极简伪逻辑为了让你直观感受我写一段跳表核心查找逻辑的伪代码Javapublic Node find(int targetScore) { Node curr this.head; // 从左上角开始 // 从最高层向下爬 for (int i currentMaxLevel - 1; i 0; i--) { // 如果右边节点存在且分数小于目标就一直往右跳 while (curr.forward[i] ! null curr.forward[i].score targetScore) { curr curr.forward[i]; } // 到这说明右边没路了或者大了i-- 会让循环进入下一层 } // 最终在 L0 层判断一下 curr curr.forward[0]; return (curr ! null curr.score targetScore) ? curr : null; }