redis跳表

Redis跳表（Skip List）是一种基于概率的数据结构，用于有序集合的实现，它可以在O(log n)的时间复杂度下，实现插入、删除、查找等操作。

跳表的原理是通过在链表中添加一些随机层来加速查找，这些层称之为“跳跃层”。每个节点都包含多个指向下一节点的指针，其中跳跃层的指针指向下一个有值的节点。

查找时，从最高层直到底层沿着指针找到第一个大于等于目标值的节点，然后沿着该节点的下一层继续找到目标值。这样就可以在较短的时间内完成查找，同时相较于红黑树等数据结构，跳表的代码实现要相对简单，易于维护。

Redis的跳表实现分为两个部分，一个是跳表节点（zskiplistNode），一个是跳表结构（zskiplist）。其中，跳表节点有如下属性：

typedef struct zskiplistNode {
    // 层次指针，指向下一个节点
    struct zskiplistNode *backward;    // 后退指针
    struct zskiplistLevel {
        struct zskiplistNode *forward;    // 前进指针
        unsigned int span;                // 跨度
    } level[];
    double score;    // 排序分值
    robj *obj;       // 节点对象
} zskiplistNode;

可以看到，跳表节点由一个后退指针和多个前进指针组成。前进指针指向它的下一个节点，而后退指针指向前一个节点。跨度（span）指的是从当前节点到下一个目标节点之间跨越了多少个节点。由于节点的层数可能不同，因此zskiplistNode中包含了一个level数组，用以存储每个节点的指针信息。

而跳表结构（zskiplist）则由如下属性组成：

typedef struct zskiplist {
    struct zskiplistNode *header, *tail;    // 头尾节点
    unsigned long length;