共计 1727 个字符，预计需要花费 5 分钟才能阅读完成。
之前相关联的文章：
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 编码：
- 保留的元素不超过 128 个。
- 保留的元素成员长度不超过 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 两种数据结构呢？
依据下面提到的两种数据结构的存储原理是很好答复的：
- 应用 dict 是为了利用 hash 算法，以 O(1)的工夫复杂度查问成员的分值，这就是命令 ZSCORE 实现的根底。
- 应用 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 设计与实现》一书
