Redis跳表到底怎么排序的，里面原理其实挺有意思也不简单

关于Redis跳表的排序原理，其实它并不是一个完全陌生的概念，你可以把它想象成一种“多层地铁线路图”，这个比喻来自一位知乎上的技术博主（@程序员小灰）的生动解释，Redis的有序集合（zset）底层就用到了跳表来实现快速的范围查询和排序。

核心思想：给链表加上“快速通道”

我们想想一个最简单的数据结构：有序链表，假如所有数据都按照分数（score）从小到大排好队在一个链表里，我们要查找某个值，只能从头一个一个往后找，效率很低，是O(N)级别。

跳表的聪明之处在于，它觉得这样太慢了，于是给这个“排好的长队”修建了几层“快速通道”（索引层）,具体是怎么建的呢？

1. 底层是基础：最底层（L1）就是那个完整的有序链表,包含了所有的节点。
2. 随机建索引：那么上面的索引层怎么来？这里有个非常巧妙的设计——随机决定，对于底层链表中的每一个节点，它都有一定的概率（比如50%）被“提拔”到上一级索引层，这就像抛硬币，抛到正面，这个节点就在上一层也出现；抛到反面,就停止提拔。
3. 索引之上再建索引：对刚刚建好的第一级索引层（L2），再用同样的抛硬币方法，决定其中的哪些节点能继续晋升到第二级索引层（L3），如此往复，直到产生一个足够高的索引层（通常不会太高，因为概率是指数级下降的）。

这样最终形成的结构，就是一个多层的有序链表，最上层（Ln）的节点最少，相当于最快的“特快线路”；越往下，节点越多，速度越慢，直到最底层的“普通线路”（所有节点）。

查找过程：从快车道换乘到慢车道

现在我们要查找一个分数为89的节点，是怎么做的呢？（这个查找过程的描述在很多技术博客,比如阮一峰的网络日志中也有类似阐述）

• 起点在顶层：搜索不会傻傻地从底层开始,而是从最高层的索引链表开始。
• 向右摸索，遇到大的就下楼：在顶层索引上，从左向右遍历，如果下一个节点的分数比89小，就继续向右走（因为链表是有序的），一旦发现下一个节点的分数大于89，说明“开过头了”,89肯定不在当前这个区间。
• 下降一层：这时，我们就“下电梯”，回到当前节点,然后下降到下一层索引。
• 重复过程：在下一层索引中，继续重复“向右摸索，遇到大的就下楼”这个过程。
• 最终抵达：当我们下降到底层（L1）链表时，再向右稍微走几步，就能精确地找到分数为89的那个节点,或者确定它不存在。

这个过程就像坐地铁：你先坐最快的特快线，坐到离你目的地最近的那个大站，然后换乘慢线，再坐几站，最后出站走几步就到了，这比从头到尾坐慢线要快得多，由于索引是分层的，查找过程可以跳过大量不必要的节点，效率可以提升到O(logN),接近二叉搜索树的水平。

插入和删除：动态维护“快速通道”

跳表更厉害的地方在于，它不仅能高效查找，还能高效地插入和删除节点，并且动态地维护这些“快速通道”。

• 插入：我们要找到新节点应该插入到底层链表的哪个位置（用上面的查找方法），找到位置后，把它插入到底层链表，关键一步来了：这时候要开始为这个新节点“抛硬币”，根据抛硬币的结果，决定它是否要晋升到L2层，如果晋升了，再抛一次硬币，决定是否晋升到L3层……直到某次抛硬币失败为止，这个过程保证了索引的建立是随机的,不需要全局调整。
• 删除：删除更简单，只要找到这个节点在所有层中的出现（从底层开始找，然后顺着指针找到它在各层的索引）,然后像普通链表一样把它从每一层中摘除即可。

为什么Redis选择跳表？

你可能问，已经有像平衡树（如红黑树）这样高效的排序结构了，为什么Redis还要用跳表？这在Redis的作者Salvatore Sanfilippo的博客和访谈中提到过几个原因：

1. 实现简单：跳表的实现代码比红黑树等平衡树要简单得多，bug更少,容易维护和调试。
2. 范围查询极快：这是跳表的一个巨大优势，因为在底层，所有节点还是一个有序链表，一旦找到了范围查询的起点，要获取这个范围的所有节点，只需要在底层链表上向后遍历即可，非常高效,而在平衡树中实现范围查询则相对麻烦。
3. 灵活调整：通过调整“抛硬币”的概率，可以灵活地在索引密度（占用空间）和查询速度之间做权衡。

Redis跳表的排序原理，本质是通过一种随机化的方式，给一个有序链表添加了多级索引，把单向遍历变成了“多层换乘”，从而极大地提升了查找、插入、删除和范围查询的效率，它用一种听起来简单甚至有点“随意”的方法（抛硬币），达到了媲美复杂算法的高性能,这正是其设计巧妙和有趣的地方。