本文所引用的源码全部来自Redis2.8.2版本。

Redis中skiplist数据结构与API相关文件是：redis.h与t_zset.c。

http://blog.csdn.net/acceptedxukai/article/details/8923174 这是我之前写的关于skiplist最传统的实现，功能远不如Redis中跳表的强大，但是代码简短，比较容易理解。

一、跳跃表简介

跳跃表是一种随机化数据结构，基于并联的链表，其效率可以比拟平衡二叉树，查找、删除、插入等操作都可以在对数期望时间内完成，对比平衡树，跳跃表的实现要简单直观很多。

以下是一个跳跃表的例图(来自维基百科)：

从图中可以看出跳跃表主要有以下几个部分构成：

1、 表头head：负责维护跳跃表的节点指针

2、 节点node：实际保存元素值，每个节点有一层或多层

3、 层level：保存着指向该层下一个节点的指针

4、 表尾tail：全部由null组成

跳跃表的遍历总是从高层开始，然后随着元素值范围的缩小，慢慢降低到低层。

二、Redis中跳跃表的数据结构

Redis作者为了适合自己功能的需要，对原来的跳跃表进行了一下修改：

1、 允许重复的score值：多个不同的元素(member)的score值可以相同

2、 进行元素对比的时候，不仅要检查score值，还需要检查member：当score值相等时，需要比较member域进行比较。

3、 结构保存一个tail指针：跳跃表的表尾指针

4、 每个节点都有一个高度为1层的前驱指针，用于从底层表尾向表头方向遍历

跳跃表数据结构如下(redis.h):

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; 数据结构中可能span这个参数最不好理解了，下面简单解释一下：

参照上面跳跃表的例图，head节点的span所有level的值都将是1；node 1在level 0 span值为1，因为跨越1个元素都将走到下一个节点2，在level 1 span值为2，因为需要跨越2个元素(node 2,node 3)才能到达下一个节点3。

关于span的解释可以详看:
http://stackoverflow.com/questions/10458572/what-does-the-skiplistnode-variable-span-mean-in-redis-h

三、简单列出跳跃表的API，他们的作用以及算法复杂度:

约定O(N)表示对于元素个数的表达，O(L)表示对于跳表层数的表达

函数名
作用
复杂度

zslCreateNode
新建并返回一个跳表节点
O(1)

zslCreate
新建并初始化一个跳跃表
O(L)

zslFreeNode
释放给定的节点
O(1)

zslFree
释放给定的跳跃表
O(N)

zslRandomLevel
得到新节点的层数(抛硬币法的改进)
O(1)

zslInsert
将给定的score与member新建节点并添加到跳表中
O(logN)

zslDeleteNode
删除给定的跳表节点
O(L)

zslDelete
删除给定的score与member在跳表中匹配的节点
O(logN)

zslIsInRange
检查跳表中的元素score值是否在给定的范围内
O(1)

zslFirstInRange
查找第一个符合给定范围的节点
O(logN)

zslLastInRange
查找最后一个符合给定范围的节点
O(logN)

zslDeleteRangeByScore
删除score值在给定范围内的节点
O(logN)+O(M)

zslDeleteRangeByRank
删除排名在给定范围内的节点
O(logN)+O(M)

zslGetRank
返回给定score与member在集合中的排名
O(logN)

zslGetElementByRank
根据给定的rank来查找元素
O(logN)

四、上述API源码的简单解析

4.1 zslCreateNode

//建立一个skiplist节点，需要传入所在的level,score，以及保存的数值obj
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;
}zmalloc是Redis在系统函数malloc上自己封装的函数，主要为了方便对内存使用情况的计算。

4.2 zslCreate

//创建skiplist，header不存储任何数据
zskiplist *zslCreate(void) {
int j;
zskiplist *zsl;

zsl = zmalloc(sizeof(*zsl));
zsl->level = 1;
zsl->length = 0;
zsl->header = zslCreateNode(ZSKIPLIST_MAXLEVEL,0,NULL);//ZSKIPLIST_MAXLEVEL = 32
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;
}

4.3 zslRandomLevel

int zslRandomLevel(void) {//为新的skiplist节点生成该节点level数目
int level = 1;
while ((random()&0xFFFF) < (ZSKIPLIST_P * 0xFFFF))//0.25
level += 1;
return (level }

4.4 zslInsert

zskiplistNode *zslInsert(zskiplist *zsl, double score, robj *obj) {
zskiplistNode *update[ZSKIPLIST_MAXLEVEL], *x;
unsigned int rank[ZSKIPLIST_MAXLEVEL];
int i, level;