之前相关联的文章：
redis学习之一SDS
redis学习之二双端链表
redis学习之三字典
redis学习之四skiplist
redis学习之五ziplist
redis学习之六对象
redis学习之七字符串对象
redis学习之八列表对象
redis学习之九哈希对象
redis学习之十汇合对象

先再看一下redisObject的定义：

typedef struct redisObject{    //类型    unsigned type:4;    //编码    unsigned encoding:4;    //lru缓存淘汰机制信息    unsigned lru:LRU_BITS;    //援用计数器    int refcount;    //指向底层实现数据结构的指针    void *ptr;}robj;

有序汇合的编码能够是ziplist或skiplist，当同时满足上面两个条件时应用ziplist编码，不满足的话会应用skiplist编码：

  1. 保留的元素不超过128个。
  2. 保留的元素成员长度不超过64字节。

这两个值也是能够通过zset-max-ziplist-value配置进行调整的。

先来说下ziplist编码无关的状况：每个元素应用两个紧挨在一起的压缩列表来保留数据，第一个节点保留元素的成员(member)，第二个节点保留的是分值(score)，分值从小到大排列，也就是分值较小的排在表头后面，较大的排在凑近表尾一侧。
看下上面的命令：

redis> ZADD price 8.5 apple 5.0 banana 6.0 cherry(integer) 3

存储示意图为：

能够看的进去元素是按分值递增排序的。上面来看下应用skiplist编码是如何存储的，先看下示意图：

skiplist编码的有序汇合对象应用zset构造作为底层实现，一个zset蕴含一个字典和一个跳表：

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

咱们分两局部别离说下dict与zsl，先看zsl:
zsl跳表按分值从小到大保留了所有汇合元素，跳表节点里的object保留了元素成员，跳表里的score属性保留的是元素的分值。
再来看看dict里的内容：
dict存的是元素成员到分值的映射关系：dict的健保留了元素的成员，dict的值则保留了元素分值，通过这个关系，能够用O(1)的复杂度找到给定的分值。
须要阐明下，只管zset同时应用dict与zskiplist两种数据结构保留元素，但这两种数据结构会通过指针来共享雷同元素的成员和分值，所以不会产生同一元素屡次存储，也就不会造成内存的节约。

最初，咱们来聊几个问题：

  • 为什么有序汇合会同时应用dict与ziplist两种数据结构呢？
    依据下面提到的两种数据结构的存储原理是很好答复的：
  1. 应用dict是为了利用hash算法，以O(1)的工夫复杂度查问成员的分值，这就是命令ZSCORE实现的根底。
  2. 应用skiplist让咱们能够以O(logN)的工夫复杂度进行依据分值查问成员、查问成员的排名操作，这就是命令ZRANK/ZRANGE实现的根底。
  • 剖析下命令ZRANGE key start stop命令的工夫复杂度
    咱们晓得这命令会返回有序汇合中指定区间内的成员，工夫复杂度为O(logN + M)，其中 N 为有序集的基数，而 M 为后果集的基数。是这样的：通过skiplist能够以O(logN)的工夫复杂度定位到范畴start开始的元素，而后再以M的工夫复杂度定位到stop完结的元素。有个阐明：zrange工夫复杂度的阐明
  • 剖析下ZRANK key member的工夫复杂度
    从文档上看这个命令是返回有序集 key 中成员 member 的排名，工夫复杂度为O(logN)，进行工夫复杂度的剖析咱们须要看下ziplist里跨度（redis学习之四skiplist）的含意：跨度是用于记录两个节点之间的间隔的，它是用来计算排位(rank)的，在查找某个节点过程中，将沿途拜访过的所有层的跨度累计起来，失去的后果就是指标结点在ziplist里的排位，计算排位其实就相当于依据分值进行元素的查找，在查找的过程中累加跨度的常量计算能够疏忽，这样整体工夫复杂度就是O(logN)了。

本文参考的有：
黄健宏的《Redis设计与实现》一书