Redis跳跃列表究竟怎么跳 _Redis

压缩列表ziplist的zset内部有两种存储结构，一种是ziplist，另一种是跳跃列表skiplist 。为了彻底理解zset的内部结构，我们就再来介绍一下skiplist 。
skiplist介绍
顾名思义，skiplist本质上是一个有序的多维的list 。我们先回顾一下一维列表是如何进行查找的。

文章插图

如上图，我们要查找一个元素，就需要从头节点开始遍历，直到找到对应的节点或者是第一个大于要查找的元素的节点（没找到）。时间复杂度为O(N) 。
这个查找效率是比较低的，如果我们把列表的某些节点拔高一层，例如把每两个节点中有一个节点变成两层。那么第二层的节点只有第一层的一半，查找效率也就会提高。

文章插图

查找的步骤是从头节点的顶层开始，查到第一个大于指定元素的节点时，退回上一节点，在下一层继续查找。
例如我们要在上面的列表中查询16 。

从头节点的最顶层开始，先到节点7 。
7的下一个节点是39，大于16，因此我们退回到7
从7开始，在下一层继续查找，就可以找到16 。

这个例子中遍历的节点不比一维列表少，但是当节点更多，查找的数字更大时，这种做法的优势就体现出来了。还是上面的例子，如果我们要查找的是39，那么只需要访问两个节点（7、39）就可以找到了。这比一维列表要减少一半的数量。
为了避免插入操作的时间复杂度是O(N)，skiplist每层的数量不会严格按照2:1的比例，而是对每个要插入的元素随机一个层数。
随机层数的计算过程如下：

每个节点都有第一层
那么它有第二层的概率是p，有第三层的概率是p*p
不能超过最大层数

redis中的实现是
/* Returns a random level for the new skiplist node we are going to create. * The return value of this function is between 1 and ZSKIPLIST_MAXLEVEL * (both inclusive), with a powerlaw-alike distribution where higher * levels are less likely to be returned. */int zslRandomLevel(void) { int level = 1; while ((random()&0xFFFF) < (ZSKIPLIST_P * 0xFFFF)) level += 1; return (level}复制代码其中ZSKIPLIST_P的值是0.25，存在上一层的概率是1/4，也就是说相对于我们上面的例子更加扁平化一些。ZSKIPLIST_MAXLEVEL的值是64，即最高允许64层。
Redis中的skiplist
Redis中的skiplist是作为zset的一种内部存储结构
/* ZSETs use a specialized version of Skiplists */typedef struct zskiplistNode { sds ele; double score; struct zskiplistNode *backward; struct zskiplistLevel { struct zskiplistNode *forward; unsigned long span; } level[];} zskiplistNode;typedef struct zskiplist { struct zskiplistNode *header, *tail; unsigned long length; int level;} zskiplist;typedef struct zset { dict *dict; zskiplist *zsl;} zset;复制代码可以看到zset是由一个hash和一个skiplist组成。
skiplist的结构包括头尾指针，长度和当前跳跃列表的层数。
而在zskiplistNode，也就是跳跃列表的节点中包括

ele，即节点存储的数据
节点的分数score
回溯指针是在第一层指向前一个节点的指针，也就是说Redis的skiplist第一层是一个双向列表
节点各层级的指针level[]，每层对应一个指针forward，以及这个指针跨越了多少个节点span 。span用于计算元素的排名

【Redis跳跃列表究竟怎么跳】了解了zset和skiplist的结构之后，我们就来看一下zset的基本操作的实现。
插入过程
前面我们介绍压缩列表的插入过程的时候就有提到过skiplist的插入，在zsetAdd函数中，Redis对zset的编码方式进行了判断，分别处理skiplist和ziplist 。ziplist的部分前文已经介绍过了，今天就来看一下skiplist的部分。
if (zobj->encoding == OBJ_ENCODING_SKIPLIST) { zset *zs = zobj->ptr; zskiplistNode *znode; dictEntry *de; de = dictFind(zs->dict,ele); if (de != NULL) { /* NX? Return, same element already exists. */ if (nx) { *flags |= ZADD_NOP; return 1; } curscore = *(double*)dictGetVal(de); /* Prepare the score for the increment if needed. */ if (incr) { score += curscore; if (isnan(score)) { *flags |= ZADD_NAN; return 0; } if (newscore) *newscore = score; } /* Remove and re-insert when score changes. */ if (score != curscore) { znode = zslUpdateScore(zs->zsl,curscore,ele,score); /* Note that we did not removed the original element from * the hash table representing the sorted set, so we just * update the score. */ dictGetVal(de) = &znode->score; /* Update score ptr. */ *flags |= ZADD_UPDATED; } return 1; } else if (!xx) { ele = sdsdup(ele); znode = zslInsert(zs->zsl,score,ele); serverAssert(dictAdd(zs->dict,ele,&znode->score) == DICT_OK); *flags |= ZADD_ADDED; if (newscore) *newscore = score; return 1; } else { *flags |= ZADD_NOP; return 1; }}复制代码