了解过Redis的都知道,Redis有一个非常有用的数据结构:SortSet,基于它,我们可以很轻松的实现一个Top N的应用。那么,这个SortSet底层到怎么样实现的?怎么样实现才能既保证有序并提供插入,查询的最优时间复杂度呢?这里,便就是我将要给大家介绍的跳表

跳表的具体定义,请参考wikipedia跳表定义,跳表也是链表的一种,只不过它在链表的基础上增加了跳跃功能,正是这个跳跃的功能,使得在查找元素时,跳表能够提供O(log n)的时间复杂度。(通常,像红黑树等这样的数据结构查找的时间复杂度也是O(log n),但是正确实现一颗红黑树是比正确实现一个跳表是要复杂很多很多的)

跳跃

那么,这个跳跃的功能是怎么实现的呢?为什么能够提供跟查找树一样的O(log n)的时间复杂度呢?下边我将借助Redis中的代码来分析这些原理。(redis的完整代码,参看 redis

redis代码中,跳表主要实现在 t_zset.c,跳表节点的定义,则在redis.h中,我们首先来看跳表节点的定义:

typedef struct zskiplistNode {
    robj *obj;
    double score;
    struct zskiplistNode *backward;
    struct zskiplistLevel {
        struct zskiplistNode *forward;
        unsigned int span;
    } level[];
} zskiplistNode;  

暂时先不关心robj *obj和unsigned int span这两个属性,robj是redis内部对象的定义, span是redis内部在计算节点的排名使用的。

在定义普通链表节点的时候(双向链表)

struct ListNode 
{
    void *data;
    ListNode *prev;
    ListNode *next;
};  

prev为前向指针,next为后向指针。
那么我们再来看redis中跳表节点的前向节点指针的定义,

struct zskiplistNode *backward;  

backward指针表示其也是一个双向链表,指向某个节点前向节点,这点跟普通链表的prev指针的含义是一样的。
再看后向节点指针的定义:

struct zskiplistLevel {
        struct zskiplistNode *forward;
        unsigned int span;
} level[];  

很奇怪是不是?后向节点指针变成了一个数组,这正是跳表可以实现跳跃的实质,这个数组中的forward元素不仅可以指向这个节点的直接后继元素,也可以指向后继元素的后继元素,或者是后继后继后继元素,依此类推。这也就是说,从当前的这个节点,可以以O(1)的时间复杂度跨过其直接后继节点查找其后的某个节点,这样就实现了跳跃。(普通链表需要查找某个节点的话,必须要进行遍历操作,这对于有查询性能要求的应用场景来说,是不能接受的!)

O(log n)

现在我们再来看看跳表为什么能提供O(log n)的时间复杂度。
一般,我们会在插入元素的时候,就保持跳表的有序排列。请看下图:
enter image description here

可以看到,正式这样一种结构,我们每次在进行查询操作的时候,都会从最高一层开始找,由于链表是有序的,所以期望的时间复杂度是O(log n),当然最坏情况下的时间复杂度是o(n),不过这种情况应该不太会遇到。

需要指出的是,实际的存储结构,并不是像上图这样有这么多节点,跟普通链表相比,跳表额外的存储空间只有那个前向节点数组花费的,当然,这是一种以空间换取时间的策略。与它提供的特性相比,这点额外的空间我们是可以接受的。

redis跳表实现解析

首先我们看下redis实现中几个我们可以自己拿出来用的api:

/** 创建一个skiplist */ 
zskiplist *zslCreate(void)

/** 创建一个skiplist节点 */
zskiplistNode *zslCreateNode(int level, double score, robj *obj);

/** 释放一个节点的内存 */
void zslFreeNode(zskiplistNode *node);

/** 释放整个skiplist */
void zslFree(zskiplist *zsl);

/** 插入一个节点 */
zskiplistNode *zslInsert(zskiplist *zsl, double score, robj *obj)

/** 删除一个节点,根据score删除 */
int zslDelete(zskiplist *zsl, double score, robj *obj);

/** 这个函数是查询某个节点对应的排名,其实就是在跳表中位置 */
unsigned long zslGetRank(zskiplist *zsl, double score, robj *o);  

上边这些使我们可以从redis源代码中抠出来自己用的代码(当然还需要在封装封装),对于跳表来说,重点需要关注的就是插入,查找,删除这几个操作。

(下篇分析redis代码中skiplist插入,查找,删除的实现)