redis跳跃表

跳跃表（skiplist）是一种有序数据结果，它通过在每个节点中维持多个指向其他节点的指针，从而达到快速访问节点的目的。

跳跃表的实现

由zskiplistNode和zskiplist两个结构定义
zskiplist的组成：
header：指向跳跃表的表头节点。
tail：指向跳跃表的表尾节点。
level：记录目前跳跃表内，成熟最大的那个节点的层数。
length：记录跳跃表的长度。

typedef struct zskiplist{
    //表头节点和表尾节点
    structz skiplistNode *header, *tail;

    //表中节点数量
    unsigned long length;

    //表中层数最大的节点层数
    int level;
}

zskiplistNode的组成：
level：跳跃表节点的level数组可以包含多个元素，每个元素都包含一个指向其他节点的指针。
forward：前进指针，指向下一层级的指针。
span：跨度，用于记录两个节点之间的距离。
backward：后退指针，用于逆向遍历的指针。
分值：节点的分值是一个都变了类型的浮点数，跳跃表中的所有节点都按分值从小到大排序。
成员：节点的成员对象，指向一个保存的字符串对象，而字符串对象则保存着SDS值。

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

总结

跳跃表是有序集合的底层实现之一。
redis的跳跃表实现由zskiplist和zskiplistNode两个结构组成，其中zskiplist用于保存跳跃表信息（比如表头节点、表尾节点、长度），而zskiplistNode则用于表示跳跃表节点。
每个跳跃表节点的层高都是1至32之间的随机数
在同一个跳跃表中，多个节点可以包含相同的分值，但每个节点的成员对象必须是唯一的。
跳跃表中的节点按照分值大小进行排序，当分值相同时，节点按照成员对象的大小进行排序。