这篇文章我们分析一下redis当中跳跃表的数据结构。
跳跃链表数据结构
跳跃链表是一种能够快速查找元素的数据结构，跳跃链表每个数据节点有随机的多层，每个节点不像传统的单层链表那样指向相邻的下一个，而是 指向相隔多个节点的后面的某一个节点，其数据结构如下图所示：
这样对于一个有序的链表来说，如果要查找其中的某一个元素，不用一个个节点向后遍历，在查找的时候可以跳过中间的一些节点，快速定位到想要查找的元素， 这样就可以把单层链表查找元素的时间复杂度从O(n)缩短到O(log n)。下面看一下redis当中跳跃链表的实现细节，
从809行可以看到跳跃链表当中有一个zskiplistNode的结构体，header指向的是表头节点，tail指向的表尾节点，length表示链表当中节点的数目， level指的是这个链表中层数最多的节点有多少层。以图1为例，length为7，level为4。对于单个节点，zskiplistNode这个数据中保存的是单个节点的信息。 ele当中保存的是这个节点的元素，score保存的是节点的分值，跳跃表当中的节点会按照这个score从小到大进行排列。backward是回退指针，指向后面的一个节点。 对于每个节点，节点的前进指针是有多个的，每一个zskiplistLevel结构体中都有一个前进指针，指向后面的某个节点。span表示指向的这个节点同当前这个节点的距离 是多少。图1当中存储7的节点指向存储37的节点的span为5。我们可以看到zskiplistNode有多个前进指针，但是只有一个后退指针。上图的代码是5.0版本的数据结构， 在此之前zskiplistNode的结构体当中存储的元素并不是sds动态字符串，而是一个指针，指向的是一个字符串对象，这个字符串对象当中保存的是sds的值。
插入节点
我们先看一下在一个跳跃链表当中插入一个节点的源码
/* 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. */
//计算节点的层数，其中ZSKIPLIST_P为0.25
int zslRandomLevel(void) {
int level = 1;
while ((random()&0xFFFF) < (ZSKIPLIST_P * 0xFFFF)) //有0.25的概率上升一层
level += 1;
return (level<ZSKIPLIST_MAXLEVEL) ? level : ZSKIPLIST_MAXLEVEL;
}
/* 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(); //获取插入节点的level
if (level > zsl->level) { //如果当前插入节点的level大于现有链表的最大level，就更新header大于这部分的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++) { //如果小于现有节点的level，就更新前驱节点的跨度
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;
}
上面这段代码当中，zslInsert为插入节点的函数，我们着重看下zslRandomLevel这个函数，我们可以看到在新插入一个节点需要确定该节点的最高level的时候， 采用的是一种随机概率的手段，每个节点都会有第一层，有ZSKIPLIST_P的概率会再高一层，这里ZSKIPLIST_P为0.25，这样做的好处是跳跃链表不用像其他数据结构 比如红黑树那样维持一个严格的结构规则，插入一个新的节点就不用对已有的节点进行调整。
如果插入的新的节点的level高于当前链表的最高level，就需要对于链表的header进行调整，让header中高于新节点level的那些指针指向这个节点。同时需要 做的是更新插入节点的前驱节点，让插入节点的前驱节点的forward指针指向自己，插入节点的forward指向后面一个节点。接下来更新插入节点对于前面节点span 造成的影响。下图是插入一个节点的示意图
删除操作和插入操作的原理类似，就不在这里展开了，感兴趣的可以去看下源码。
如果对你有帮助，请作者喝一杯牛奶吧
