Redis数据库——ZSet的底层实现（跳表）

大家好，这里是编程Cookbook。本文详细介绍ZSet数据类型中跳表的底层实现，包括基本特点和常用操作。

ZSet（有序集合）

概述

ZSet（Sorted Set，有序集合） 是 Redis 提供的一个非常强大的数据结构。它是一个 没有重复成员 且每个成员都关联着一个 分数（score） 的集合，Redis 会根据成员的分数对它们进行 自动排序。这个数据结构在许多需要有序数据的场景中非常有用，如排行榜、带有优先级的任务队列等。

ZSet 提供了非常高效的操作支持，如按排名查询、按分数查询、获取范围内的元素等，且在执行这些操作时有着较低的时间复杂度。

基本特点

• 成员唯一性：ZSet 中的每个元素都是唯一的（没有重复的成员）。
• 分数（score）：每个成员都有一个与之关联的分数，分数通常是浮动的数值，用于排序。Redis 会根据分数值对成员进行升序排序。
• 有序性：ZSet 内部元素会根据分数（score）进行自动排序，成员可以通过分数排名进行快速查找。
• 按分数查询：可以根据成员的分数进行范围查询（例如，获取某个分数范围内的成员），也可以获取某个成员的排名。

底层实现

Redis 的 ZSet 在实现上确实有根据数据量和元素大小的不同，采用不同的内存优化方式。具体来说：

1. 使用 ziplist（压缩链表）：

   • 元素数量小于 128：当 ZSet 中的元素数量较少时，使用 ziplist 来优化内存。因为 ziplist 对小规模数据结构的存储是高效的，尤其是在内存有限的情况下。
   • 每个元素的长度小于 64 字节：如果 ZSet 中的元素比较小（成员和分数的长度合计小于 64 字节），ziplist 的压缩效果会比较好，从而进一步节省内存空间。

   在 ziplist 中，成员和分数（score）是交替存储的，并且以压缩的方式存储，减少了内存的开销。

2. 使用 skiplist（跳跃链表）和 hash table（哈希表）：

   • 当 ZSet 中的元素数量超过 128 个，或者 元素的长度超过 64 字节，Redis 会自动转而使用 跳跃链表（skiplist）和哈希表（hash table） 的组合来实现 ZSet。这是默认的实现方式，主要是因为跳跃链表和哈希表的组合在查找、范围查询、排序等操作上具有更好的性能。

   • 跳跃链表（Skiplist）：

     • 用于维护 ZSet 中元素的有序性。跳跃链表是一种多层次链表，每一层都是一个有序的链表，层数根据概率进行分配。跳跃链表的查询、插入、删除操作时间复杂度为 O(log N)。
     • 跳跃链表提供了非常高效的范围查询（按分数范围查询、按排名查询等）支持，因此非常适合用于 ZSet。

   • 哈希表（Hash Table）：

     • 用于存储每个元素的 成员 → 分数 映射，使得可以通过 O(1) 时间复杂度快速查找一个成员的分数。
     • 哈希表提供快速查找、插入和删除操作。

Skiplist跳表

跳表（Skiplist）是一种 概率型的数据结构，旨在提供与平衡二叉树类似的查找性能（O(log N)），但其实现相对更简单且更易于理解。跳表通过多层链表的方式，使用概率来决定每个元素出现在哪些层，从而加速查询、插入和删除操作。

Redis选择跳跃表而非红黑树作为有序集合实现方式的原因并非是基于并发上的考虑，因为redis是单线程的，选用跳跃表的原因仅仅是因为跳跃表的实现相较于红黑树更加简洁。

概述

跳表的核心思想是通过 多级索引（层级链表）来加速元素的查找。每一层都是一个有序链表，跳表通过多层次的链表来进行索引，从而大大降低了查找时需要遍历的节点数量。

• 第0层：包含了所有的元素，是最基础的有序链表。
• 第1层：每隔一定数量的元素出现一个节点，可以认为是对第0层链表的索引。
• 第2层、第三层...：随着层数的增加，每一层的节点数量逐渐减少。

跳表的查找是通过从顶部层开始，每层尝试跳跃多个元素，直到找到目标元素或到达链表的末尾。插入和删除操作也利用类似的跳跃方式来维持跳表的有序性和层级结构。

结构

上图用a,b,c,d,e五种有序链表说明了跳跃表的过程。

• [a]单链表：查询时间复杂度O(n)
• [b]level-2单链表：每隔一个节点为一个level-2节点，每个level-2节点有2个后继指针，分别指向单链表中的下一个节点和下一个level-2节点。查询时间复杂度为O(n/2)
• [c]level-3单链表：每隔一个节点为一个level-2节点，每隔4个节点为一个level-3节点，查询时间复杂度O(n/4)
• [d]指数式单链表：每隔一个节点为一个level-2节点，每隔4个节点为一个level-3节点，每隔8个节点为一个level-4节点（每2^i个节点的level为i+1），查询时间复杂度为O(log2N)
• [e]跳跃表：各个level的节点个数同指数式单链表，但出现的位置随机，查询复杂度是O(logN)

跳跃表和指数式单链表的最大区别在于，跳跃表中各层节点的分布是随机的，而不是按照固定的规律排列。这种随机性使得跳跃表非常灵活，且能够有效平衡性能。

• 查询操作：查询时，跳跃表根据层级结构，通过随机选择的高层节点来加速查找过程。虽然节点的分布是随机的，但由于层数与节点数的关系仍然保持对数增长，查询的时间复杂度保持为 O(log N)，这保证了跳跃表在查找操作上的高效性。

单/双向链表

其实上图的表示在链表的方向上有点问题。

在标准跳表实现中，最底层的链表通常是双向的（即节点包含前驱和后继指针），而上层链表是单向的（仅包含后继指针）：

• 最底层是双向链表（支持反向遍历和高效删除）；
• 上层是单向链表（节省内存，仅用于加速查找）。

源码

在 Redis 的跳表节点的源码实现大致如下：

typedef struct zskiplistNode {
    sds ele;                        // 成员对象（Redis 5.0+ 改为直接存储 sds 字符串）
    double score;                   // 分数
    struct zskiplistNode *backward; // 后退指针（双向链表支持）
    struct zskiplistLevel {
        struct zskiplistNode *forward;  // 前进指针
        unsigned long span;             // 跨度（Redis 3.2+ 改为 unsigned long）
    } level[];                       // 柔性数组（Flexible Array Member）
} zskiplistNode;

结构体字段解析

跳表的基本操作

1. 查找操作（Search）

功能：在跳表中查找指定成员（member）及其分数（score）。
时间复杂度：平均 O(log N)，最坏 O(N)。
步骤：

1. 从最高层开始：从头节点的最高层出发。
2. 向右遍历：
   • 若当前节点的 forward 节点 score < 目标 score，继续向右移动。
   • 若 score 相等，比较 member 是否匹配。
3. 向下移动：当无法继续向右时，向下移动一层，重复步骤 2。
4. 终止条件：
   • 找到 member 和 score 完全匹配的节点（返回节点）。
   • 到达底层仍未找到（返回 NULL）。

zskiplistNode 没有显式的 down 指针，但通过 柔性数组 level[] 的层级索引 隐式实现“向下”操作。

2. 插入操作（Insert）

功能：插入新成员（member）和分数（score）。
时间复杂度：平均 O(log N)。
步骤：

1. 查找插入位置：
   • 类似 Search，记录每一层的“前置节点”（update 数组）。
2. 随机生成层数：
   • 通过概率（如抛硬币）决定新节点的层数（Redis 默认 P=0.25）。
3. 创建新节点：
   • 分配内存并初始化各层的前后指针。
4. 更新指针：
   • 将新节点插入到每一层的链表中（基于 update 数组）。
5. 调整跨度（Span）：
   • 更新每一层的跨度值（用于排名计算）。

跨度（Span）是跳表实现排名计算（如 ZRANK、ZREVRANK）的核心机制，它记录了从当前节点到下一节点之间的逻辑距离（即跳过的节点数）：

• 每个跳跃表节点的每一层（Level）都有一个 span 字段。
• span 值：表示从当前节点的第 i 层到 forward[i] 节点之间的 节点数量（包含 forward[i]）。

3. 删除操作（Delete）

功能：删除指定成员（member）和分数（score）。
时间复杂度：平均 O(log N)。
步骤：

1. 查找待删节点：
   • 类似 Search，记录每一层的前置节点（update 数组）。
2. 验证节点存在：
   • 检查底层的前置节点的 forward[0] 是否匹配目标。
3. 更新指针：
   • 将每一层中指向待删节点的指针绕过（类似链表删除）。
4. 释放内存：
   • 回收节点内存（Redis 中可能延迟释放）。

4. 排名计算（ZRank）

功能：返回成员（member）的排名（即第几名，按 score 升序排序，从 0 开始）。
时间复杂度：平均 O(log N)。
步骤：

1. 查找成员：
   • 类似 Search，累计每一层的“跨度”（span）值。
2. 计算排名：
   • 排名 = 从头部到目标节点的路径跨度总和。