跳跃表是一种随机化的数据结构,在查找、插入和删除这些字典操作上,其效率可比拟于平衡二叉树(如红黑树),大多数操作只需要O(log n)平均时间,但它的代码以及原理更简单。
和链表、字典等数据结构被广泛地应用在Redis内部不同,Redis只在两个地方用到了跳跃表,一个是实现有序集合键,另一个是在集群结点中用作内部数据结构。除此之外,跳跃表在Redis里面没有其他用途。
/* ZSETs use a specialized version of Skiplists */
typedef struct zskiplistNode {
robj *obj;
double score;
struct zskiplistNode *backward;
struct zskiplistLevel {
struct zskiplistNode *forward;
unsigned int span;//代表该节点在每层到下一个节点所跨越的节点长度
} level[];
} zskiplistNode; typedef struct zskiplist {
struct zskiplistNode *header, *tail;
unsigned long length;
int level;
} zskiplist;
obj是该结点的成员对象指针,score是该对象的分值,是一个浮点数,跳跃表中的所有结点,都是根据score从小到大来排序的。
同一个跳跃表中,各个结点保存的成员对象必须是唯一的,但是多个结点保存的分值却可以是相同的:分值相同的结点将按照成员对象的字典顺序从小到大进行排序。
level数组是一个柔性数组成员,它可以包含多个元素,每个元素都包含一个层指针(level[i].forward),指向该结点在本层的后继结点。该指针用于从表头向表尾方向访问结点。可以通过这些层指针来加快访问结点的速度。
每次创建一个新跳跃表结点的时候,程序都根据幂次定律(power law,越大的数出现的概率越小)随机生成一个介于1和32之间的值作为level数组的大小,这个大小就是该结点包含的层数。
Redis中的跳跃表,与普通跳跃表的区别之一,就是包含了层跨度(level[i].span)的概念。
层跨度用于记录本层当前结点到下一个 结点之间的距离,举个例子,如下图的跳跃表:节点1在第0层的下一个节点是2,span=1;在第1层的下一个节点是3,span=2;在第2层的下一个节点是4,span=3;所以计算的节点在每层的跨度以跨越第0层上的节点数量为准。如果新节点的level要比整个表的level低,导致update[i].level[i]在本层的下一个节点为null的,循环结束后对此类节点的span++,所以此类节点的span代表的是到第0层最后一个节点的距离
插入节点的算法如图,先找到在每层的插入位置,并保存在update数组中,同时将头节点到该位置的跨度累加,保存在rank数组中。最后计算随机高度,在每层插入节点。
zskiplistNode *zslCreateNode(int level, double score, robj *obj) {
zskiplistNode *zn = zmalloc(sizeof(*zn)+level*sizeof(struct zskiplistLevel));
zn->score = score;
zn->obj = obj;
return zn;
} zskiplist *zslCreate(void) {
int j;
zskiplist *zsl; zsl = zmalloc(sizeof(*zsl));
zsl->level = ;
zsl->length = ;
zsl->header = zslCreateNode(ZSKIPLIST_MAXLEVEL,,NULL);
for (j = ; j < ZSKIPLIST_MAXLEVEL; j++) {
zsl->header->level[j].forward = NULL;
zsl->header->level[j].span = ;
}
zsl->header->backward = NULL;
zsl->tail = NULL;
return zsl;
}/* 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 = ;
while ((random()&0xFFFF) < (ZSKIPLIST_P * 0xFFFF))
level += ;
return (level<ZSKIPLIST_MAXLEVEL) ? level : ZSKIPLIST_MAXLEVEL;
} zskiplistNode *zslInsert(zskiplist *zsl, double score, robj *obj) {
zskiplistNode *update[ZSKIPLIST_MAXLEVEL], *x;
unsigned int rank[ZSKIPLIST_MAXLEVEL];
int i, level; redisAssert(!isnan(score));
x = zsl->header;
for (i = zsl->level-; i >= ; i--) {
/* store rank that is crossed to reach the insert position */
rank[i] = i == (zsl->level-) ? : rank[i+];
while (x->level[i].forward &&
(x->level[i].forward->score < score ||
(x->level[i].forward->score == score &&
compareStringObjects(x->level[i].forward->obj,obj) < ))) {
rank[i] += x->level[i].span;//累加本层从头节点到插入位置节点的跨度综合
x = x->level[i].forward;
}
update[i] = x;//得到每层的插入位置节点
}
/* we assume the key is not already inside, since we allow duplicated
* scores, and the re-insertion of score and redis object 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] = ;
update[i] = zsl->header;
update[i]->level[i].span = zsl->length;
}
zsl->level = level;
}
x = zslCreateNode(level,score,obj);
for (i = ; 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[] - rank[i]);//update[i]->level[i].span - 0层和i层的update[i]之间的距离
update[i]->level[i].span = (rank[] - rank[i]) + ;//新增一个节点在后面,所以跨度加一
} /* increment span for untouched levels */
for (i = level; i < zsl->level; i++) {//如果新节点的层数小于表的level,将updata[i]->level[i]的span++
update[i]->level[i].span++;
} x->backward = (update[] == zsl->header) ? NULL : update[];
if (x->level[].forward)
x->level[].forward->backward = x;
else
zsl->tail = x;
zsl->length++;
return x;
}