本文共 6176 字，大约阅读时间需要 20 分钟。

基于Redis5.0

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

跳跃表支持平均 O(log N) 最坏 O(N) 复杂度的节点查找， 还可以通过顺序性操作来批量处理节点。

在大部分情况下， 跳跃表的效率可以和平衡树相媲美， 并且因为跳跃表的实现比平衡树要来得更为简单， 所以有不少程序都使用跳跃表来代替平衡树。

Redis 使用跳跃表作为有序集合键的底层实现之一： 如果一个有序集合包含的元素数量比较多， 又或者有序集合中元素的成员（member）是比较长的字符串时， Redis 就会使用跳跃表来作为有序集合键的底层实现

为什么选择跳跃表

从该有序表中搜索元素 < 23, 43, 59 > ，需要比较的次数分别为 < 2, 4, 6 >，总共比较的次数为 2 + 4 + 6 = 12 次。链表是有序的，但不能使用二分查找。类似二叉搜索树，我们把一些节点提取出来，作为索引。得到如下结构：

这里我们把 < 14, 34, 50, 72 > 提取出来作为一级索引，这样搜索的时候就可以减少比较次数了。我们还可以再从一级索引提取一些元素出来，作为二级索引，变成如下结构：

Redis跳跃表的实现

最左边的是 zskiplist 结构：

• header ：指向跳跃表的表头节点。
• tail ：指向跳跃表的表尾节点。
• level ：记录目前跳跃表内，层数最大的那个节点的层数（表头节点的层数不计算在内）。
• length ：记录跳跃表的长度，也即是，跳跃表目前包含节点的数量（表头节点不计算在内）。

位于 zskiplist 结构右方的是四个 zskiplistNode 结构：

• level：节点中用 L1 、 L2 、 L3 等字样标记节点的各个层， L1 代表第一层， L2 代表第二层，以此类推。每个层都带有两个属性：前进指针和跨度。前进指针用于访问位于表尾方向的其他节点，而跨度则记录了前进指针所指向节点和当前节点的距离。在上面的图片中，连线上带有数字的箭头就代表前进指针，而那个数字就是跨度。当程序从表头向表尾进行遍历时，访问会沿着层的前进指针进行。
• backward：节点中用 BW 字样标记节点的后退指针，它指向位于当前节点的前一个节点。后退指针在程序从表尾向表头遍历时使用。
• score：各个节点中的 1.0 、 2.0 和 3.0 是节点所保存的分值。在跳跃表中，节点按各自所保存的分值从小到大排列。
• sds：各个节点中的 o1 、 o2 和 o3 是节点所保存的sds对象。

跳跃表节点：

//server.h/* ZSETs use a specialized version of Skiplists */typedef struct zskiplistNode {
       //保存的sds    sds ele;	//分值    double score;	// 后退指针    struct zskiplistNode *backward;	// 层    struct zskiplistLevel {
   		// 前进指针        struct zskiplistNode *forward;		/**         * 跨度实际上是用来计算元素排名(rank)的，         * 在查找某个节点的过程中，将沿途访过的所有层的跨度累积起来，         * 得到的结果就是目标节点在跳跃表中的排位         */        unsigned long span;    } level[];} zskiplistNode;

• 层

  跳跃表节点的 level 数组可以包含多个元素， 每个元素都包含一个指向其他节点的指针， 程序可以通过这些层来加快访问其他节点的速度， 一般来说， 层的数量越多， 访问其他节点的速度就越快。

  每次创建一个新跳跃表节点的时候， 程序都根据幂次定律 （power law，越大的数出现的概率越小） 随机生成一个介于 1 和 32 之间的值作为 level 数组的大小， 这个大小就是层的“高度”。

• 前进指针

  每个层都有一个指向表尾方向的前进指针（level[i].forward 属性）， 用于从表头向表尾方向访问节点。

• 跨度

  层的跨度（level[i].span 属性）用于记录两个节点之间的距离

  跨度是用来计算排位（rank）的： 在查找某个节点的过程中， 将沿途访问过的所有层的跨度累计起来， 得到的结果就是目标节点在跳跃表中的排位

• 后退指针

  节点的后退指针（backward 属性）用于从表尾向表头方向访问节点： 跟可以一次跳过多个节点的前进指针不同， 因为每个节点只有一个后退指针， 所以每次只能后退至前一个节点

• 分值和成员

  节点的分值（score 属性）是一个 double 类型的浮点数， 跳跃表中的所有节点都按分值从小到大来排序。

  节点的成员（sds属性）是一个字符串sds

跳跃表

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

• header 和 tail 指针分别指向跳跃表的表头和表尾节点， 通过这两个指针， 程序定位表头节点和表尾节点的复杂度为 O(1)
• length 属性来记录节点的数量， 程序可以在 O(1) 复杂度内返回跳跃表的长度
• level 属性则用于在 O(1) 复杂度内获取跳跃表中层高最大的那个节点的层数量， 注意表头节点的层高并不计算在内

跳跃表API实现：

创建一个跳跃表节点：

//t_zset.c/* Create a skiplist node with the specified number of levels. * The SDS string 'ele' is referenced by the node after the call. */zskiplistNode *zslCreateNode(int level, double score, sds ele) {
   	//给Node以及level数组分配内存    zskiplistNode *zn =        zmalloc(sizeof(*zn)+level*sizeof(struct zskiplistLevel));    zn->score = score;    zn->ele = ele;    return zn;}

创建一个跳跃表：

/* Create a new skiplist. */zskiplist *zslCreate(void) {
       int j;    zskiplist *zsl;    zsl = zmalloc(sizeof(*zsl));    zsl->level = 1;    zsl->length = 0;    zsl->header = zslCreateNode(ZSKIPLIST_MAXLEVEL,0,NULL);    for (j = 0; j < ZSKIPLIST_MAXLEVEL; j++) {
           zsl->header->level[j].forward = NULL;        zsl->header->level[j].span = 0;    }    zsl->header->backward = NULL;    zsl->tail = NULL;    return zsl;}

在跳跃表中插入一个节点：

/* Insert a new node in the skiplist. Assumes the element does not already * exist (up to the caller to enforce that). The skiplist takes ownership * of the passed SDS string 'ele'. */zskiplistNode *zslInsert(zskiplist *zsl, double score, sds ele) {
       zskiplistNode *update[ZSKIPLIST_MAXLEVEL], *x;    unsigned int rank[ZSKIPLIST_MAXLEVEL];    int i, level;    serverAssert(!isnan(score));    x = zsl->header;    for (i = zsl->level-1; i >= 0; i--) {
           /* store rank that is crossed to reach the insert position */        rank[i] = i == (zsl->level-1) ? 0 : rank[i+1];        while (x->level[i].forward &&                (x->level[i].forward->score < score ||                    (x->level[i].forward->score == score &&                    sdscmp(x->level[i].forward->ele,ele) < 0)))        {
               rank[i] += x->level[i].span;            x = x->level[i].forward;        }        update[i] = x;    }    /* we assume the element is not already inside, since we allow duplicated     * scores, reinserting the same element should never happen since the     * caller of zslInsert() should test in the hash table if the element is     * already inside or not. */    level = zslRandomLevel();    if (level > zsl->level) {
           for (i = zsl->level; i < level; i++) {
               rank[i] = 0;            update[i] = zsl->header;            update[i]->level[i].span = zsl->length;        }        zsl->level = level;    }    x = zslCreateNode(level,score,ele);    for (i = 0; i < level; i++) {
           x->level[i].forward = update[i]->level[i].forward;        update[i]->level[i].forward = x;        /* update span covered by update[i] as x is inserted here */        x->level[i].span = update[i]->level[i].span - (rank[0] - rank[i]);        update[i]->level[i].span = (rank[0] - rank[i]) + 1;    }    /* increment span for untouched levels */    for (i = level; i < zsl->level; i++) {
           update[i]->level[i].span++;    }    x->backward = (update[0] == zsl->header) ? NULL : update[0];    if (x->level[0].forward)        x->level[0].forward->backward = x;    else        zsl->tail = x;    zsl->length++;    return x;}

在跳跃表中删除一个节点：

/* Internal function used by zslDelete, zslDeleteByScore and zslDeleteByRank */void zslDeleteNode(zskiplist *zsl, zskiplistNode *x, zskiplistNode **update) {
       int i;    for (i = 0; i < zsl->level; i++) {
           if (update[i]->level[i].forward == x) {
               update[i]->level[i].span += x->level[i].span - 1;            update[i]->level[i].forward = x->level[i].forward;        } else {
               update[i]->level[i].span -= 1;        }    }    if (x->level[0].forward) {
           x->level[0].forward->backward = x->backward;    } else {
           zsl->tail = x->backward;    }    while(zsl->level > 1 && zsl->header->level[zsl->level-1].forward == NULL)        zsl->level--;    zsl->length--;}

转载地址：http://huhpi.baihongyu.com/