如何实现一个海量用户的实时排名系统?或许可以用mysql搞一个纠结的方案;但要是选择了redis，那绝对是既简单又优雅。Redis的zset本身就是一种支持排序的集合，而zset的实现，则使用了skip list数据结构。Skip list是一种多层次的有序链表，通过随机地选择层数来实现插入、查找和删除都是O(logn)的时间复杂度(和平衡树同样的效率，但实现比平衡树简单很多)。关于skip list的具体介绍可以参见William Pugh的论文：Skip Lists: A Probabilistic Alternative to Balanced Trees 。下面我们来分析一下redis中skip list的实现。

　　Redis中skip list主要有zskiplist和zskiplistNode两个数据结构：

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;

　　其中zskiplistNode中包含一个zskiplistLevel数组，数组的大小根据节点所在的层数(level)决定。backward指针是为了方便向后遍历而对skip list做的改进。

　　主要的API有：

　　zslCreate 创建一个zskiplist，并添加一个具有最高层数ZSKIPLIST_MAXLEVEL(代码中定义为32)的节点来管理分层的链表。

　　zslInsert 插入一个节点到zskiplist，并调整每一个层级的链表都是有序的。

　　zslDelete 从zskiplist删除一个节点，并调整剩余节点在每个层级都是有序的。

　　zslRandomLevel 为新加入的节点随机产生一个不超过ZSKIPLIST_MAXLEVEL的层数。

　　zslInsert和zslDelete函数都需要首先查找到合适的位置或节点，查找的代码很简单，直接包含在了这两个函数内：

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 && 　　compareStringObjects(x->level[i].forward->obj,obj) < 0))) { 　　rank[i] += x->level[i].span; 　　x = x->level[i].forward; 　　} 　　update[i] = x; 　　}

　　查找是从zskiplist现有的最高层开始向前，并在查找的过程中根据规则转向低层的链表继续，一直到skip list的最低层为止。同时看到redis的实现中允许相同的score存在(这时按对象的字符串进行比较)，但不允许具有相同值的对象并存(集合的特性)。

　　下面通过一个例子来说明skip list的建立过程。

　　按顺序执行下列语句：

zslInsert(zsl, 5, obj1); //level=1; 　　zslInsert(zsl, 3, obj2); //level=2; 　　zslInsert(zsl, 4, obj3); //level=1; 　　zslInsert(zsl, 1, obj4); //level=3; 　　zslInsert(zsl, 2, obj5); //level=1;

　　现在的zsl结构如下图所示，其中level array的数组下标是为了图例更直观，实际不占存储空间。为了保证图例的简洁，backward的指针没有画出，对应level 0红色指针相反方向的指针。