一 摘要

   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 128
zset-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 是返回的元素个数。