Redis的跳跃表

在Redis中，有一种高效的数据结构叫做有序集合(zset)

它是一种集合，其中每个成员(member)都会关联一个分数(score)。
zset既可以快速地通过member找到该成员对应的分数，又可以按照分数的大小进行范围查询，这对于实现排行榜等功能非常有用。那么zset是如何实现这样的功能的呢？答案是跳跃表（skiplist）。

1. zset的底层实现

思考这么几个问题：

• zset是如何快速的根据成员取得对应的分数？
• zset是如何快速的取得指定排行区间的所有成员和分数？
• zset的zrevrange(逆序)又是如何实现的？
• zset如何计算一个成员的排位？
• …
  第一个问题我们很容易想到使用哈希表，实际上zset的底层实现，就是一个哈希表+跳跃表，看看结构：(对于元素数量少的情况，zset会使用另一种实现方式，我们这里不作讨论)

typedef struct zset {
    dict *dict;
    zskiplist *zsl;
} zset;

哈希表(dict)大部分人都了解，那么对于这个跳跃表(zskiplist)，又是怎样的结构呢？

2.跳跃表的结构和特性

跳跃表是一种有序链表+多层索引的结构，使得包含n个元素的有序序列的查找和插入操作的平均时间复杂度都是 $\Omicron \left(\log{n}\right)$ 。
跳跃表是按层建造的，最底层是一个普通的有序链表。
众所周知，如果是一个有序的数组，我们可以通过二分查找，很快的找到其中的某个元素。那么对于一个有序的链表，我们有没有办法也使用二分查找呢？
跳跃表的想法就是用空间换时间：在最底层的原始链表上面，加多一层索引，元素数量为原始链表的一半，如图所示：

这样查找的时候，原本要比较n个元素，通过使用索引，减少到 $\frac{n}{2}$ 。
但是这样还不够，所以我们在上面再多加几层索引，如图所示：

理论上，对于元素数量为n的链表，我们可以建立 $\log_{2}{n}$ 层索引。
这样，我们就能通过从最高层开始，通过二分查找的方式，快速的查找某个数值在链表中的位置。

3.实现细节

Redis的跳跃表实现主要有两个结构：zskiplistNode和zskiplist，其中zskiplistNode是跳跃表的结点，而zskiplist则记录整个表的一些信息，如结点的数量等。

上图展示了一个跳跃表的实例。左边代表着跳跃表的整体结构：zskiplist

zskiplist的代码如下：

typedef struct zskiplist {
    struct zskiplistNode *header, *tail;
    unsigned long length;
    int level;
} zskiplist;

header和tail：分别指向跳跃表头结点和尾结点，其中头结点在zskiplist创建时生成，并不实际存储数据。
length：跳跃表的长度，通过这个变量，可以在O(1)时间内获取长度。
level：当前跳跃表中最高的层，不包括头结点。

每次创建新结点的时候，redis根据幂次定律(越大的数出现概率越小)随机生成一个高度(介于1和32)，作为当前结点的level数组的长度，也就是这个结点的高度。

结点zskiplistNode的代码如下：

typedef struct zskiplistNode {
    sds ele;
    double score;
    struct zskiplistNode *backward;
    struct zskiplistLevel {
        struct zskiplistNode *forward;
        unsigned long span;
    } level[];
} zskiplistNode;

ele：每个结点的成员，sds是redis内置的简单动态字符串结构(Simple Dynamic String)
score：每个结点的分数，是double类型
backward：回退指针，用于从表尾向表头遍历。用来实现zrevrange。
level：每个层级上的索引。

注意level中的每一层，除了指向下一个结点的指针以外，还有一个span表示跨度，即下一个结点和当前结点的距离。(示例图中，箭头上面的数字)
这个跨度用来计算排行，由于redis的跳跃表并不是严格的按照每层数量减半的实现，所以在高层，每一次跨越几个原始结点，只能存储在这个span中，而在遍历的时候，通过计算跨度的和，就可以知道当前排在第几位了。

上图中红色和绿色都是zskiplistNode结构，其中header的backward/ele/score都是没用的，所以省略了没画出来

4 与其他结构的对比

和红黑树这类平衡树结构相比，跳跃表的算法复杂度一样，而主要优势在于实现简单，且在并发环境下更加高效；
与哈希表相比，跳跃表支持有序数据的快速检索和范围查询，但牺牲了一些插入和删除操作的性能。
总的来说，跳跃表是一种空间换时间，以及用随机化处理平衡的高效数据结构。

参考资料：

• 深入理解Redis跳跃表的基本实现和特性
• 维基百科：skip list
• 深入理解Redis Zset原理