一 摘要

Redis 的几种主要数据结构，大家应该都有所了解。例如最常用的五种：字符串，list，hash，set，zset。各自的适用场景也算是比较常见容易考察的内容。但再深入一点，zset 底层的数据结构是什么样子的，原理是什么？跳表和平衡树的选择，为什么没有用平衡树？zset 查找单一元素和范围查找的时间复杂度是多少？那么估计就有很多人无法给出准确、明确的回答了。

二 zset 基础

关于 redis 数据结构的解析文章，已经比较多了，这里不再赘述。但会阐述几个关键内容：

2.1 存储结构

zset 底层的存储结构有两种：ziplist 和 skiplist。其中，skiplist 就是“跳跃表”结构（简称跳表）。关于一个 zset 何时使用 ziplist，何时使用 skiplist，有如下的判断条件：

• 有序集合保存的元素数量小于 128 个

• 有序集合保存的所有元素的长度小于 64 字节

对应 redis 中的配置：

zset-max-ziplist-entries 128zset-max-ziplist-value 64

在上述两个条件同时满足时使用 ziplist，其他时候使用 skiplist。

 当 ziplist 作为 zset 的底层存储结构时候，每个集合元素使用两个紧挨在一起的压缩列表节点来保存，第一个节点保存元素的成员，第二个元素保存元素的分值。

 当 skiplist 作为 zset 的底层存储结构的时候，使用 skiplist 按序保存元素及分值，使用 dict 来保存元素和分值的映射关系。

2.2 跳表结构

跳表是 William Pugh 在其 1990 年的论文《Skip lists: A probabilistic alternative to balanced trees》中提出的。题目中即包含了两个关键理解：

1、跳表是概率型数据结构；

2、跳表是用来替代平衡树的数据结构。准确来说，是用来替代自平衡二叉查找树（self-balancing BST）的结构。

跳表示例：

可见，跳表由多层结构组成，仍然采用类似二分的思想和结构，来解决快速插入和查找问题。第 k 层可以视为第 k-1 级索引，用来加速查找。为了避免占用空间过多，第 1 层之上都不存储实际数据，只有指针（包含指向同层下一个元素的指针与同一个元素下层的指针）。

2.3 元素查找复杂度分析

二叉平衡树的查找性能，时间复杂度是 O(logn)，跳表具备相同的能力。接下来我们来看具体的查找过程：

当查找元素时，会从最顶层链表的头节点开始遍历。以升序跳表为例，如果当前节点的下一个节点包含的值比目标元素值小，则继续向右查找。如果下一个节点的值比目标值大，就转到当前层的下一层去查找。重复向右和向下的操作，直到找到与目标值相等的元素为止。下图中的蓝色箭头标记出了查找元素 21 的步骤。

2.4 元素插入过程

zskiplist()函数实现 zskiplist 中插入元素过程。源代码较长，这里只列举操作步骤：

1）与查找流程相同，找到合适的插入位置。注意 zset 允许分数 score 相同，这时会根据节点数据 obj 的字典序来排序。

2）调用 zslRandomLevel()方法，随机出要插入的节点的层数。

3）调用 zslCreateNode()方法，根据层数 level、分数 score 和数据 obj 创建出新节点。

4）每层遍历，修改新节点以及其前后节点的前向指针 forward 和跳跃长度 span，也要更新最底层的后向指针 backward。

其中维护了两个数组 update 和 rank。update 数组用来记录每一层的最后一个分数小于待插入 score 的节点，也就是插入位置。rank 数组用来记录上述插入位置的上一个节点的排名，以便于最后更新 span 值。

插入流程如下图所示：

三 详细数据结构

3.1 skiplist 的数据结构

我们重点看 skiplist 的数据结构，来自 server.h 文件：

#define ZSKIPLIST_MAXLEVEL 32#define ZSKIPLIST_P 0.25
typedef struct zskiplistNode {    robj *obj;    double score;    struct zskiplistNode *backward;    struct zskiplistLevel {        struct zskiplistNode *forward;        unsigned int span;    } level[];} zskiplistNode;
typedef struct zskiplist {    struct zskiplistNode *header, *tail;    unsigned long length;    int level;} zskiplist;

可以看到，zskiplistNode 这个结构体的定义中，在 zskiplistLevel 这个子结构体的定义内，有一个无符号整型字段"span"，它表示当前指针跨越了多少个节点，这个字段在 zset 的范围查找汇总至关重要。

3.2 范围查找性能分析

与单值查找不同，范围查找不能直接按照 score 从高到低排序后，通过比较缩小范围，最终定位到一个节点。我们需要的是类似 sql 中 limit 0,100 这类的效果。

有了 span 字段后，由于 span 记录了距离下一个节点的距离，所以也可以从高层开始利用 span 不断累加来判断是否小于或等于起始位置，如果不是就继续向下一层继续累加 span，一直到找到所有范围内的元素位置。

一个查找示例如下：

查找 > zrange key 5,2

那么就从最高层开始计算，首先

level4 -- score:0-span:1 + score:10-span:4 == 5

level3 -- ....

level2 -- ....

这样的话直接计算出来 score:20 是第 5 个节点，那么就确认了，也就代表直接定位到了第 5 个节点指针位置，那么最后就会在最低层以这个 score:20 节点指针作为开始位置不断向后获取 2 个节点然后返回结束.

时间复杂度平均是 O[(LogN)+M] M 是返回的元素个数。