Redis跳表介绍（redis为什么使用跳表而不是红黑树）

跳表的诞生可以简单用下面的例子来看：假设一个有序链表，查询某个节点的时间复杂度是O（n），那接下来在链表上层再建立一条链表，每两个结点提取一个结点到上一级，形成L1级缓存链表，如下：

这样当我们要找寻8时，先通过L1索引链表找到7，然后在向下一级链表遍历就找了8，这比直接遍历链表的效率提高了不少，同理，再添加一级L2索引，如图：

查找8的时候先从L2级索引链表开始遍历，遍历的节点个数进一步减少，查找的时间复杂度比单纯的链表遍历进一步提升。

以上是跳表的一个思想，实现起来不同的应用实现的方式不尽相同，这里看一下在Redis中是如何设计并实现跳表。

在Redis中，有序集合的实现方式采用了跳表。跳表是由zskiplistNode和skiplist两个结构定义,其中 zskiplistNode结构表示跳表节点, zskiplist结构则用于保存跳表节点的相关信息,比如节点的数量,以及指向表头节点和表尾节点的指针等等。结构图如下：

其中zskiplist和zskiplistNode结构如下：

typedef struct zskiplist {

    // 头节点，尾节点
    struct zskiplistNode *header, *tail;

    // 节点数量
    unsigned long length;

    // 目前表内节点的最大层数
    int level;

} zskiplist;

typedef struct zskiplistNode {

    // member 对象
    robj *obj;

    // 分值
    double score;

    // 后退指针
    struct zskiplistNode *backward;

    // 层
    struct zskiplistLevel {

        // 前进指针
        struct zskiplistNode *forward;

        // 这个层跨越的节点数量
        unsigned int span;

    } level[];

} zskiplistNode;

当一个节点插入时，首先要计算出这个节点所在的level数，这是一个概率型的数据结构，元素的插入层数是随机指定的。Willam Pugh在论文中描述了它的计算过程如下：

1. 指定节点最大层数 MaxLevel，指定概率 p， 默认层数 lvl 为1
2. 生成一个0~1的随机数r，若r<p，且lvl<MaxLevel ，则lvl ++
3. 重复第 2 步，直至生成的r >p 为止，此时的 lvl 就是要插入的层数。

论文中生成随机层数的伪码：

具体的加入、删除等操作源码自行撸代码吧！