3.2 跳跃表节点与结构

由3.1节我们知道，跳跃表由多个节点构成，每个节点由很多层构成，每层都有指向本层下个节点的指针。那么，Redis中的跳跃表是如何实现的呢？

3.2.1 跳跃表节点

下面我们来看跳跃表节点的zskiplistNode结构体。

    typedef struct zskiplistNode {
        sds ele;
        double score;
        struct zskiplistNode ＊backward;
        struct zskiplistLevel {
            struct zskiplistNode ＊forward;
            unsigned int span;
        } level[];
    } zskiplistNode;

该结构体包含如下属性。

1）ele：用于存储字符串类型的数据。

2）score：用于存储排序的分值。

3）backward：后退指针，只能指向当前节点最底层的前一个节点，头节点和第一个节点——backward指向NULL，从后向前遍历跳跃表时使用。

4）level：为柔性数组。每个节点的数组长度不一样，在生成跳跃表节点时，随机生成一个1～64的值，值越大出现的概率越低。

level数组的每项包含以下两个元素。

❏ forward：指向本层下一个节点，尾节点的forward指向NULL。

❏ span:forward指向的节点与本节点之间的元素个数。span值越大，跳过的节点个数越多。

跳跃表是Redis有序集合的底层实现方式之一，所以每个节点的ele存储有序集合的成员member值，score存储成员score值。所有节点的分值是按从小到大的方式排序的，当有序集合的成员分值相同时，节点会按member的字典序进行排序。

3.2.2 跳跃表结构

除了跳跃表节点外，还需要一个跳跃表结构来管理节点，Redis使用zskiplist结构体，定义如下：

    typedef struct zskiplist {
        struct zskiplistNode ＊header, ＊tail;
        unsigned long length;
        int level;
    } zskiplist;

该结构体包含如下属性。

1）header：指向跳跃表头节点。头节点是跳跃表的一个特殊节点，它的level数组元素个数为64。头节点在有序集合中不存储任何member和score值，ele值为NULL, score值为0；也不计入跳跃表的总长度。头节点在初始化时，64个元素的forward都指向NULL, span值都为0。

2）tail：指向跳跃表尾节点。

3）length：跳跃表长度，表示除头节点之外的节点总数。

4）level：跳跃表的高度。

通过跳跃表结构体的属性我们可以看到，程序可以在O(1)的时间复杂度下，快速获取到跳跃表的头节点、尾节点、长度和高度。