排行榜
懂行的老哥一看这个小标题，就知道我要以排行榜作为切入点，去讲 Redis 的 zset 了。
是的，经典面试题，请实现一个排行榜，大部分情况下就是在考验你知不知道 Redis 的 zset 结构，和其对应的操作。
当然了，排行榜我们也可以基于其他的解决方案。比如 mysql。
我曾经就基于 mysql 做过排行榜，一条 sql 就能搞定。但是仅限于数据量比较少，性能要求不高的场景（我当时只有 11 支队伍做排行榜，一分钟刷新一次排行榜）。
对于这种经典的面试八股文，网上一找一大把，所以本文就不去做相关解析了。
说好的只是一个切入点。
如果你不知道具体怎么实现，或者根本就不知道这题在问啥，那一定记得看完本文后要去看看相关的文章。最好自己实操一下。
相信我，八股文，得背，这题会考。
zset 的内部编码
众所周知，Redis 对外提供了五种基本数据类型。但是每一种基本类型的内部编码却是另外一番风景：
其中 list 数据结构，在 Redis 3.2 版本中还提供了 quicklist 的内部编码。不是本文重点，我提一嘴就行，有兴趣的朋友自己去了解一下。
本文主要探讨的是上图中的 zset 数据结构。
zset 的内部编码有两种：ziplist 和 skiplist。
实你也别觉得这个东西有多神奇。因为对于这种对外一套，对内又是一套的“双标党”其实你已经很熟悉了。
它就是 JDK 的一个集合类，来朋友们，大胆的喊出它的名字：HashMap。
HashMap 除了基础的数组结构之外，还有另外两个数据结构：一个链表，一个红黑树。
这样一联想是不是就觉得也不过如此，心里至少有个底了。
当链表长度大于 8 且数组长度大于 64 的时候， HashMap 中的链表会转红黑数。
对于 zset 也是一样的，一定会有条件触发其内部编码 ziplist 和 skiplist 之间的变化？
这个问题的答案就藏在 redis.conf 文件中，其中有两个配置：
上图中配置的含义是，当有序集合的元素个数小于 zset-max-ziplist-entries 配置的值，且每个元素的值的长度都小于 zset-max-ziplist-value 配置的值时，zset 的内部编码是 ziplist。
反之则用 skiplist。
理论铺垫上了，接下我给大家演示一波。
首先，我们给 memberscore 这个有序集合的 key 设置两个值，然后看看其内部编码：
此时有序集合的元素个数是 2，可以看到，内部编码采用的是 ziplist 的结构。
为了大家方便理解这个储存，我给大家画个图：
然后我们需要触发内部编码从 ziplist 到 skiplist 的变化。
先验证 zset-max-ziplist-value 配置，往 memberscore 元素中塞入一个长度大于 64字节（zset-max-ziplist-value默认配置）的值：
这个时候 key 为 memberscore 的有序集合中有 3 个元素了，其中有一个元素的值特别长，超过了 64 字节。
此时的内部编码采用的是 skiplist。
接下来，我们往 zset 中多塞点值，验证一下元素个数大于 zset-max-ziplist-entries 的情况。
我们搞个新的 key，取值为 whytestkey。
首先，往 whytestkey 中塞两个元素，这是其内部编码还是 ziplist：
那么问题来了，从配置来看 zset-max-ziplist-entries 128。
这个 128 是等于呢还是大于呢？
没关系，我也不知道，试一下就行了。
现在已经有两个元素了，再追加 126 个元素，看看：
通过实验我们发现，当 whytestkey 中的元素个数是 128 的时候，其内部编码还是 ziplist。
那么触发其从 ziplist 转变为 skiplist 的条件是 元素个数大于 128，我们再加入一个试一试：
果然，内部编码从 ziplist 转变为了 skiplist。
理论验证完毕，zset 确实是有两幅面孔。
本文主要探讨 skiplist 这个内部编码。
它就是标题说的：基于运气的数据结构。
什么是 skiplist？
这个结构是一个叫做 William Pugh 的哥们在 1990 年发布的一篇叫做《Skip Lists: A Probabilistic Alternative to Balanced Trees》的论文中提出的。
论文地址：ftp://ftp.cs.umd.edu/pub/skipLists/skiplists.pdf
我呢，写文章一般遇到大佬的时候我都习惯性的去网上搜一下大佬长什么样子。也没别的意思。主要是关注一下他们的发量稀疏与否。
在找论文作者的照片之前，我叫他 William 先生，找到之后，我想给他起个“外号”，就叫火男：
他的主页就只放了这一张放荡不羁的照片。然后，我点进了他的 website：
里面提到了他的丰功伟绩。
我一眼瞟去，感兴趣的就是我圈起来的三个地方。
- 第一个是发明跳表。
- 第二个是参与了 JSR-133《Java内存模型和线程规范修订》的工作。
- 第三个是这个哥们在谷歌的时候，学会了吞火。我寻思谷歌真是人才辈出啊，还教这玩意呢？
eat fire，大佬的爱好确实是不一样。
感觉他确实是喜欢玩火，那我就叫他火男吧：
火男的论文摘要里面，是这样的介绍跳表的：
摘要里面说：跳表是一种可以用来代替平衡树的数据结构，跳表使用概率平衡而不是严格的平衡，因此，与平衡树相比，跳表中插入和删除的算法要简单得多，并且速度要快得多。
论文里面，在对跳表算法进行详细描述的地方他是这样说的：
首先火男大佬说，对于一个有序的链表来说，如果我们需要查找某个元素，必须对链表进行遍历。比如他给的示意图的 a 部分。
我单独截取一下：
这个时候，大家还能跟上，对吧。链表查找，逐个遍历是基本操作。
那么，如果这个链表是有序的，我们可以搞一个指针，这个指针指向的是该节点的下下个节点。
意思就是往上抽离一部分节点。
怎么抽离呢，每隔一个节点，就抽一个出来，和上面的 a 示意图比起来，变化就是这样的：
抽离出来有什么好处呢？
假设我们要查询的节点是 25 。
当就是普通有序链表的时候，我们从头节点开始遍历，需要遍历的路径是：
head -> 3 -> 6 -> 7 -> 9 -> 12 -> 17 -> 19 -> 21 -> 25
需要 9 次查询才能找到 25 。
但是当结构稍微一变，变成了 b 示意图的样子之后，查询路径就是：
第二层的 head -> 6 -> 9 -> 17 -> 21 -> 25。
5 次查询就找到了 25 。
这个情况下我们找到指定的元素，不会超过 (n/2)+1 个节点：
