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