redis源码阅读--跳跃表

对于跳跃表之前已经简单说明了下，那么redis的跳跃表又是如何实现应用的呢？这次就来看看。

redis跳跃表的实现

数据结构定义：(server.h/zskiplist)

typedef struct zskiplist {
    //头节点，尾节点
    struct zskiplistNode *header, *tail;
    //节点数量
    unsigned long length;
    //目前表内节点的最大层数
    int level;
} zskiplist;

节点定义如下：

typedef struct zskiplistNode {
    sds ele;
    //分值
    double score;
    //后退指针，用于从表尾方向向表头方向迭代：当需要逆序处理有序集的命令时，就会用到这个属性
    struct zskiplistNode *backward;
    //层
    struct zskiplistLevel {
        struct zskiplistNode *forward;
        unsigned long span;
    } level[];
} zskiplistNode;

redis跳跃表的应用

跳跃表在redis中的唯一作用，就是实现有序集数据类型。跳跃表将指向有续集的score值和meber域的指针作为元素，并且以score值作为索引，对有序元素进行排序。
举例子来说：

redis> ZADD s 6 x 10 y 15 z
(integer) 3
redisZRANGE s 0-1 WITHSCORES

在redis的底层实现中，其为x、yh和z三个member分别创建了三个字符串，值分别为double类型的6，10，和15，然后用跳跃表将这些指针有序地保存起来，形成这样一个跳跃表：

总结

• redis的跳跃表是一种随机化的数据结构，查找、添加、删除操作都可以在对数期望时间下完成。
• 跳跃表目前在redis的唯一作用，就是作为有序集类型的底层数据结构（另一个是字典）。
• 为了满足自身需要，redis基于william pugh 论文中的描述的跳跃表进行了修改，包括:
  1.score值可重复。
  2.对比一个元素与同时需要检查它的score和member。
  3.每个节点带有高度为1层的后退指针，用于从表尾方向向表头方向迭代。