前面讲了这么多数据结构，但是仍不如我讲述Zset如此让人激动：
- 它是set，但是居然有序
- 在有序的情况下，单点查找还能保持O(1)
- 单点查找O(1)的情况下，范围查找还能保持O(logN)
为什么会有这样完美的数据结构呢？在这样复杂的内部结构中，它要如何保证它的主线程不被阻塞呢？
Zset的渐进式编码
- 如果有序集合的元素个数小于
128个，并且每个元素的值小于64字节时，Redis 会使用压缩列表作为 Zset 类型的底层数据结构； - 如果有序集合的元素不满足上面的条件，Redis 会使用跳表作为 Zset 类型的底层数据结构；
4.1 Zset的数据结构
压缩列表我们就不说了，当数据规模较小时，各种数据结构的速度差异并不大，此时我们首要的任务时降低其占用空间，这是压缩表存在的首要意义。
我们往往可以知道，索引的概念是时间换空间的关键，Zset能如此迅速的关键也就在于它在此方面做了一定的取舍，但是维护索引实际上是一个比较费力的操作，尤其是维护那些和有序相关的索引，比如MySQL的页分裂，这往往对于引擎是比较大的负担，如何在建立规模庞大的索引同时不阻塞主线程？是我们今天在审视Zset的同时需要抱着的问题。
Zset的常用接口
//返回有序集合key中元素member的分值
//复杂度:O(1)
ZSCORE key member
//正序获取有序集合key从start下标到stop下标的元素
//复杂度:O(logN)
ZRANGE key start stop [WITHSCORES]
//倒序获取有序集合key从start下标到stop下标的元素
//复杂度:O(logN)
ZREVRANGE key start stop [WITHSCORES]
//返回指定成员区间内的成员，按字典正序排列, 分数必须相同。
//复杂度:O(m) m为与key元素分数相同的元素数目
ZRANGEBYLEX key min max [LIMIT offset count]看到这里，相信我们大家对于Zset的结构已经呼之欲出，其实，类比来看，Zset的结构就是对value建立索引的LinkedHashMap。
这个索引的形式是怎么样的呢？会像MySQL那样是多层树吗？
显然不是，MySQL建立一个那样的树是有着巨大的维护成本的，页分裂和页合并是一种巨大的开销，因此B+树对于频繁增删的系统并不友好，而对于Redis更是灭顶之灾，如果主线程要在这样一种结构中消耗这么多实现，那么业务需求马上就会被阻塞，高并发也就无从谈起了，这是Redis绝对不容许的情况，我们来看一下，Redis是如何巧妙地解决这个问题的。
4.1.1 skipList
无论是何种索引，如果要支持范围查找，那就逃脱不了排序+多级查找的情况，跳表也不例外，我们先来观察在Zset中，各个节点如何组织
上图中我们可以看到三个元素”banana” “cherry” “apple” 他们各自的分数是5.0 6.0 8.5，并且已经按照分数大小进行了排序
这种结构是如何实现查询的？
一板一眼的讲可能不太好明白，我们用一个比喻来说，每一个如上所示的节点，都比作一棵高大的灌木或者树木，它的高度就是层高，如今我们需要查找此Zset，获取到header之后，从上往下遍历，相当于在一座高楼上从上往下行走，如果极目远眺，没有任何树木的话，它就会往下走一层，直到他下到了L2….
对于两个长得十分高大地灌木，由于指向的是它的整个节点的指针，我们可以直接获取它的score，和自己需要查询的score比对后，比自己的大，那么将会直接跳到下一个拥有26层高度的灌木上进行查询，如果下一颗灌木上的比要查询的大，那么将会把层高改成25层，并且通过BW指针往回查找，我们姑且假设，我们需要寻找的是分数为51的树，那么我们最终会通过如上的遍历方式，最终在第二颗高度为L24的灌木上寻找到它
而如果我们要寻找的是51.5，那么最终，查询者会在中间两颗灌木上横跳，直到跳到L1层，发现无处可跳时，查询将会终止，返回没有此结果
这些灌木索引，是如何维护的？
我们查询者所在的观察楼，实际就是一组链表数组，每一个元素都是一个链表，index为24的链表，实际上就是层高为25的所有节点，按照score从小到大组成的指针链表
- 当我们向跳表加入一个高度为5的灌木时，我们首先要做的，就是通过score找到它在链表中的该有的位置，这个环节需要O(logN)的开销，在那之后，就是改变各个层数的与自己的关系，这个过程我们可以理解为，在每一层往左往右观察(往左：通过BW向前寻找存在我这个层高的灌木；往右：通过L1指针向后寻找存在我这个层高的灌木），每层观察到的两株灌木都需要改变相互的索引关系，由于自己有5层，故最多需要改变5个前驱灌木对自己的指针，以及自己对至多5个后继灌木的指针，这个环节往往是最大的隐患，因为遍历的缘故开销达到O(N)也是时有发生的
为何要采用概率的方式控制这些灌木的高度？
在索引中采用概率是一个新鲜事，但是我们也可以想想如果不用这种自增长，而采取严格的二分式索引，维护成本是怎样的，采用BST+节点保存地址的方式来构建索引似乎是个可行的方案，但是二叉搜索树是需要通过旋转来保持平衡的，所以维持平衡的开销也是我们难以接受的
关于BST+节点保存地址的尝试
- 通过BST查找到需要插入的位置，开销O(logN)
- 为了维持严格的平衡，我们还需要把此score插入到一个不会使左右子树高度差大于1的子树上
这样的设想是跳表的完美实现，就像是非聚簇索引一样的优雅，但是它的缺陷往往在不起眼处：
难道地址的寻址就不需要时间吗？这跟内存的时序有关，但是也是很难忽略的常数开销，如果score和member是聚簇在一起的，寻址的时间将会非常短暂。当然我不是说此道幻灭了，但是远没有它看起来这么美好，然而，如果采用聚簇式的BST，它仍然是在空间和性能上都不占优势的选择
- 从内存占用上来比较，跳表比非聚簇平衡树更灵活一些。平衡树每个节点包含 2 个指针（分别指向左右子树），而跳表每个节点包含的指针数目平均为 1/(1-p)，具体取决于参数 p 的大小。如果像 Redis里的实现一样，取 p=1/4，那么平均每个节点包含 1.33 个指针，比平衡树更有优势。
- 在做范围查找的时候，跳表比非聚簇平衡树操作要简单。在平衡树上，我们找到指定范围的小值之后，还需要以中序遍历的顺序继续寻找其它不超过大值的节点。如果不对平衡树进行一定的改造，这里的中序遍历并不容易实现。而在跳表上进行范围查找就非常简单，只需要在找到小值之后，对第 1 层链表进行若干步的遍历就可以实现。
- 从算法实现难度上来比较，跳表比非聚簇平衡树要简单得多。平衡树的插入和删除操作可能引发子树的调整，逻辑复杂，而跳表的插入和删除只需要修改相邻节点的指针，操作简单又快速。
4.1.2 Zset总结
说到这里，Zset的结构我们的大致就介绍完了，我们来总结一下：
- 在数据规模不大时，Zset为了减少空间占用，采用的是压缩列表的存储方式，毕竟繁多的索引空间占用不菲，但效率却并没比遍历查询提高多少，但要注意，此时Zset仍然是排序的，每次我们加入Member都会按照其Score排序插入
- 随着数据规模增长，Zset会改用skipList为基础的的方式存储元素，skipList是一种带索引的双向链表结构，它采用了巧妙的方式维护了索引的结构，从而极大程度降低了它的复杂程度，这一定程度上遵循了redis非阻塞式设计的初衷
- 为了迅速的定位Member，Zset引入了map来定位每一个Node，这样我们可以实现O(1)的复杂度以查询到Member的分数
至此Zset便没有什么神秘的了，跳表+字典是它的底层实现，随机式的索引构建方式是它避免阻塞的秘诀。Redis的单线程设计是它被认为简单的原因，但它的种种设计又在告诉我们它为了维持单线程的鲁棒性做出了远比它表面看起来的复杂的努力，这些设计或经过实践考验或经过数学证明，都给Redis留下了不可磨灭的烙印。
4.2 Zset In Action
4.2.1 排行榜
Zset比较典型的使用场景就是排行榜。例如学生成绩的排名榜、游戏积分排行榜、视频播放排名、电商系统中商品的销量排名等。
以帖子点赞为例，TJD发表了五个帖子，点赞数分别为5、15、20、50、100
对某个帖子点赞了
> ZINCRBY user:tjd:rank 1 arcticle:4
"51"获取赞数最多的帖子
> ZREVRANGE user:tjd:rank 0 2 WITHSCORES
1) "arcticle:3"
2) "20"
3) "arcticle:4"
4) "50"
5) "arcticle:5"
6) "100"服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net
