之前相关联文章：
redis学习之一SDS
redis学习之二链表
redis学习之三字典
一 经典的skiplist
咱们先来看看skiplist的一张示意图：
这是在一个有序列表{3，7，11，19，22，26，37}里查找23这个值的一个过程，它是从头节点的最上层开始，通过每个层的比拟判断来进行节点的定位。
skiplist个性：
- 由多层组成。
- 每一层都是有序的链表。
- 最底层(Level 1)的链表蕴含所有元素。
- 如果一个元素呈现在 Level i 的链表中，则它在 Level i 之下的链表也都会呈现。
- 每个节点蕴含两个指针，一个指向同一链表中的下一个元素，一个指向上面一层的元素。
skiplist是一种有序数据结构，反对均匀O(logN)、最坏O(n)复杂度的节点查找，其效率不低于均衡树，且skiplist的实现较于均衡树实现要更简略。redis应用skiplist次要是在有序汇合里。
skiplist定义
typedef struct zskiplist{ //表头节点和表尾节点 struct zskiplistNode *header,*tail; //表中节点数量 unsigned long length; //最大节点层数 int level;}zskiplist;二 redis里skiplist
redis里skiplist定义：
typeof struct zskiplistNode{ //后退节点，以后节点指向的前一个节点，从后向前遍历时应用 struct zskiplistNode *backward; //分值 double score; //成员对象 robj *obj; //层 strcut zskiplistLevle{ //后退指针 struct zskiplistNode *forward; //跨度 unsigned int span; }level[];}zskiplistNode;阐明：图中是redis里应用通过革新过的skiplist，BW是后退指针；1.0/2.0/3.0是分值；o1/o2/o3是对象。
redis里的skiplist与经典的skiplist之间的比拟，有如下特点：
- 分数(score)容许反复，也就是skiplist的key是充许反复的。
- 大比拟过程中，须要比拟score也须要比拟数据自身。score雷同时，数据自身是按字典有序的。
- 第一层是一个双向链表，不便由后向前遍历。
- 跨度span是用来计算排位(rank)的：在查找某个节点的过程中，将沿途拜访过的所有层的跨度累计起来，失去的后果就是指标节点在skiplist中的排位。
三 redis里的sorted set
Redis中的sorted set，是在skiplist, dict和ziplist根底上构建起来的:
- 当数据较少时，sorted set是由一个ziplist来实现的。
- 当数据多的时候，sorted set是由一个叫zset的数据结构来实现的，这个zset蕴含一个dict + 一个skiplist。dict用来查问数据到分数(score)的对应关系，而skiplist用来依据分数查问数据（可能是范畴查找）。
本文参考的有：
黄健宏的《Redis设计与实现》一书
张铁蕾对于skiplist的文章
其它文章