redis的跳跃表实现

跳跃表(zskiplist)是一种有序的数据结构，通过在一个节点中维持多个指向其他节点的指针，从而达到从当前节点快速访问其他节点的目的。

跳跃表支持平均O(lgN)的时间查找复杂度。最坏O(N)时间复杂度的节点查找。大部分情况下，跳跃表的查找效率可以达到平衡二叉树的查找效率，而且跳跃表的结构实现较为简单。

redis使用跳跃表作为有序集合的底层实现之一：当有序集合包含的元素数量较多，或者有序集合里面的成员是比较长的字符串时，redis就会使用跳跃表来作为有序集合的底层实现结构。

zskiplist的结构定义如下：

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

其中每个节点(包括表头和表尾节点)是zskiplistNode 结构的，此结构的定义为：

typedef struct zskiplistNode {
    robj *obj;          //成员对象
    double score;       //分值
    struct zskiplistNode *backward;     //后退指针
    
    //层
    struct zskiplistLevel {
        struct zskiplistNode *forward;  //前进指针
        unsigned int span;              //跨度
    } level[];
} zskiplistNode;

下面对一个跳跃表节点结构zskiplistnode中的各属性成员进行说明：

1. obj 是节点的成员对象，是一个指针，指向一个字符串对象，而字符串对象保存着一个sds值；
2. score是节点的分数，是一个double类型的浮点数，跳跃表中的所有节点的分值都按从小到大排序好了。
   --各节点保存的成员对象必须是唯一的，但是多个节点的score可以是一样的。分值相同的节点按照成员对象在字典中的大小来排序，成员对象较小的节点会排在前面--
3. backward后退指针，用来指向当前节点的上一个节点的位置
4. 层level：跳跃表的level数组可以包含多个元素，每个元素都包含一个指向其他节点的指针，程序可以通过这些指针加快访问速度。一般来说，层越多，访问速度越快。

ps:每次创建一个新跳跃表节点时，程序会根据幂次定律(越大的数出现的概率越小)，随机生成一个1-32之间的随机数作为当前节点的层数。

跳跃表的示意图：

Paste_Image.png

参考1
参考2