我们会经常选择使用sorted set数据结构，是由于其提供的操作非常丰富，可以满足非常多的应用场景。sorted set数据结构是由skiplist（跳跃列表）、ziplist和dict实现的。
skiplist本质上是一种查找数据据结构，即根据给定的key，快速查到它所对应的value。
skiplist是一种链式数据结构，在外观表现上其具有两个属性：分值和保存的对象。
skiplist通过对每个节点的分值进行排序从而达到排序每个节点的目的。
skiplist为了实现跳跃表的快速修改和查询操作，其内部还在每个节点上都保存了一个用于指向其后节点的指针数组，以及一个指向前一个节点的指针；并且为了快速获取跳跃表的节点数目和指针数组的最大长度，其分别创建了一个length和一个level属性用于快速查询。
skiplist的平均时间复杂度为O(logN)，最坏复杂度为O(N)，其性能一般情况下可以与平衡树相媲美。
一、skiplist数据结构定义
我们看下server.h中代码
1、zskiplistNode定义了skiplist的节点结构
obj字段存放的是节点数据，它的类型是一个string robj。本来一个string robj可能存放的不是sds，而是long型，但zadd命令在将数据插入到skiplist里面之前先进行了解码，所以这里的obj字段里存储的一定是一个sds。这样做的目的应该是为了方便在查找的时候对数据进行字典序的比较，而且，skiplist里的数据部分是数字的可能性也比较小。
score字段是数据对应的分数。
backward字段是指向链表前一个节点的指针（前向指针）。节点只有1个前向指针，所以只有第1层链表是一个双向链表。
level[]存放指向各层链表后一个节点的指针（后向指针）。每层对应1个后向指针，用forward字段表示。另外，每个后向指针还对应了一个span值，它表示当前的指针跨越了多少个节点。span用于计算元素排名(rank)，这正是前面我们提到的Redis对于skiplist所做的一个扩展。需要注意的是，level[]是一个柔性数组（flexible array member），因此它占用的内存不在zskiplistNode结构里面，而需要插入节点的时候单独为它分配。也正因为如此，skiplist的每个节点所包含的指针数目才是不固定的，我们前面分析过的结论——skiplist每个节点包含的指针数目平均为1/(1-p)——才能有意义。
2、zskiplist定义了真正的skiplist结构，它包含：
头指针header和尾指针tail。
链表长度length，即链表包含的节点总数。注意，新创建的skiplist包含一个空的头指针，这个头指针不包含在length计数中。
level表示skiplist的总层数，即所有节点层数的最大值。
总结下跳跃表主要有以下几个部分构成：
1、表头head：负责维护跳跃表的节点指针
2、节点node：实际保存元素值，每个节点有一层或多层
3、层level：保存着指向该层下一个节点的指针
4、表尾tail：全部由null组成
跳跃表的遍历总是从高层开始，然后随着元素值范围的缩小，慢慢降低到低层。
二、skiplist基本操作
我们先来看下使用zskiplist保存数据的示例：
这里需要说明的是，跳跃表的节点数组的长度是随机的，其值为1到32之间的一个整数。
创建的操作
我们看下t_zsset.c的代码
从以上代码中看到，创建跳跃表过程比较简单, 初始化zskiplist数据结构, 跳跃表默认最大层数32层, 跳跃表是按score进行升序排列.
插入元素的操作
删除元素
删除元素需要精确匹配到分数和member
获取排名
排名其实就是元素在skiplist中排列的序号, 获取排名需要给出分数和成员member, 通过score查找, 匹配member成员, 时间复杂度log(N). 由于skiplist是升序排列的,因此函数返回的rank是score按升序排列的rank, 如果想获取降序rank应该是(length-rank).
三、Redis中的sorted set
前面我们提到过，Redis中的sorted set，是在skiplist, dict和ziplist基础上构建起来的:
当数据较少时，sorted set是由一个ziplist来实现的。
当数据多的时候，sorted set是由一个叫zset的数据结构来实现的，这个zset包含一个dict + 一个skiplist。dict用来查询数据到分数(score)的对应关系，而skiplist用来根据分数查询数据（可能是范围查找）。
我们先来讨论下基于ziplist实现的sorted set。在前面讲解ziplist的文章里，我们介绍过，ziplist就是由很多数据项组成的一大块连续内存。由于sorted set的每一项元素都由数据和score组成，因此当使用zadd命令插入一个(数据, score)对的时候，底层在相应的ziplist上就插入两个数据项：数据在前，score在后。
ziplist的主要优点是节省内存，但它上面的查找操作只能按顺序查找（可以正序也可以倒序）。因此，sorted set的各个查询操作，就是在ziplist上从前向后（或从后向前）一步步查找，每一步前进两个数据项，跨域一个(数据, score)对。
随着数据的插入，sorted set底层的这个ziplist就可能会转成zset的实现（转换过程详见t_zset.c的zsetConvert）。那么到底插入多少才会转呢？
还记得Redis中如下的两个配置：
zset-max-ziplist-entries 128
zset-max-ziplist-value 64这两个配置的意思是说，在如下两个条件之一满足的时候，ziplist会转成zset（具体的触发条件参见t_zset.c中的zaddGenericCommand相关代码）：
当sorted set中的元素个数，即(数据, score)对的数目超过128的时候，也就是ziplist数据项超过256的时候。
当sorted set中插入的任意一个数据的长度超过了64的时候。
最后，zset结构的代码定义如下：
typedef struct zset {
dict *dict;
zskiplist *zsl;
} zset;---EOF--