Redis：跳表skiplist

数据结构

#define ZSKIPLIST_MAXLEVEL 32 //最大层数
#define ZSKIPLIST_P 0.25 //P

typedef struct zskiplistNode {
    robj *obj;//  成员对象
    double score;// 分值
    struct zskiplistNode *backward; //后向指针
    //层
    struct zskiplistLevel {
        //每一层中的前向指针
        struct zskiplistNode *forward;
        unsigned int span;//x.level[i].span 表示节点x在第i层到其下一个节点需跳过的节点数。注：两个相邻节点span为1
    } level[];
} zskiplistNode;

typedef struct zskiplist {
    struct zskiplistNode *header, *tail;
    unsigned long length;//节点总数
    int level;//总层数
} zskiplis;

层

跳跃表节点的level数组可以包含多个元素，每个元素都包含一个指向其他节点的指针，程序可以通过这些层来加快访问其他节点的速度，一般来说，层的数量越多，访问其他节点的速度就越快。
每次创建一个新跳跃表节点的时候，程序根据幂次定律(power law，越大的数出现的概率越小)随机生成一个介于0和31之间的值作为level数组的大小，这个大小就是层的“高度”。

前进指针

每个层都有一个指向表尾方向的前进指针(level[i].forward属性)，用于从表头向表尾方向访问节点。下图用虚线表示出了程序从表头向表尾方向，遍历跳跃表中所有节点的路径：
遍历步骤:

1) 迭代程序首先访问跳跃表的第一个节点(表头)，然后从第四层的前进指针移动到表中的第二个节点。
2) 在第二个节点时，程序沿着第二层的前进指针移动到表中的第三个节点。
3) 在第三个节点时，程序同样沿着第二层的前进指针移动到表中的第四个节点。
4) 当程序再次沿着第四个节点的前进指针移动时，它碰到一个NULL，程序知道这时已经到达了跳跃表的表尾，于是结束这次遍历。

跨度

层的跨度(level[i].span属性)用于记录两个节点之间的距离：
两个节点之间的跨度越大，它们相距得就越远。
指向NULL的所有前进指针的跨度都为0，因为它们没有连向任何节点。
初看上去，很容易以为跨度和遍历操作有关，但实际上并不是这样的，遍历操作只使用前进指针就可以完成了，跨度实际上是用来计算排位(rank)的：在查找某个节点的过程中，将沿途访问过的所有层的跨度累计起来，得到的结果就是目标节点在跳跃表中的排位。
举个例子，下图用虚线标记了在跳跃表中查找分值为3.0、成员对象为o3的节点时，沿途经历的层：查找的过程只经过了一个层，并且层的跨度为3，所以目标节点在跳跃表中的排位为3。