Redis里跳表插入到底是咋回事，原理其实没那么复杂但挺有意思的

关于Redis里跳表插入到底是咋回事,咱们可以把它想象成一个多层的、带“快速通道”的链表，它之所以有意思，就是因为它在普通链表的基础上，玩了一个“抛硬币”的概率游戏，让查找和插入的速度都快了很多。

得知道跳表长啥样。

最基础的一层,就是一个普普通通的链表，每个节点都按顺序存储着数据，比如一些有序的数字，你从一头走到另一头，得一个一个节点挨着看，这就是O(n)的复杂度，数据多了就慢。

但跳表不甘心这么慢,它在普通链表上面，又建了好几层“索引”层，就像是给大楼建了电梯一样，第一层（最底层）是停靠每一户的慢速电梯，第二层可能隔几户停一次，第三层停的站更少，速度更快，这样，如果你想找顶楼的住户，就不用从一楼开始爬楼梯，可以先坐高速电梯到接近的楼层，再换乘慢速电梯，或者走几步楼梯。

在跳表里,这些“索引”就是一些额外的、稀疏的节点，它们也指向后续的节点，但跳过的距离更远，一个节点可能有很多“层”，层数越高，它能直接跳过的普通节点就越多。

重点来了，插入一个新节点的时候，到底发生了什么？

这个过程可以分成明确的两大步：

第一步：找到新节点应该坐哪儿。

这跟查字典找插入位置是一样的,你得先找到合适的位置，才能把新词条插进去，在跳表里，这个查找过程就充分利用了那些“快速通道”。

1. 从最高层开始找：我们从跳表当前拥有的最高层索引开始，比如从第5层开始（如果最高是5层的话）。
2. 向右摸索前进：在这一层，我们沿着指针向右走，比较下一个节点的值，如果下一个节点的值比我们要插入的值小，说明还能继续往前跳，我们就大胆地向右移动。
3. 下降一层：一旦发现下一个节点的值大于或等于我们要插入的值，好了，这一层不能再前进了，我们就“下降”一层，比如从第5层下到第4层。
4. 重复过程：在第4层，我们继续重复第2步：向右摸索，比较大小，直到找到下一个节点值大于插入值，然后再下降一层。
5. 直到最底层：我们就这样一层一层地下降，最终会到达最底层（第1层），在最底层，我们通过这种边走边记录的方式，已经精确地找到了新节点应该插入的位置——也就是它在前一个节点和后一个节点之间。

这个过程妙就妙在,它大部分时间都在高层索引上快速跳跃，只有必要的时候才降下来细找，大大减少了需要比较的节点数量，根据（资料来源：Redis设计与实现）这本书里的描述，Redis在实现这个查找路径时，会用一個数组来记录在每一层搜索时，最后一个值小于插入值的那个节点（也就是新节点在每一层的前驱节点），这个记录至关重要，因为下一步的链接全靠它。

第二步：把新节点“链入”名单，并决定它能不能上“快速通道”。

位置找到了,现在要把新节点插进去，这部分是跳表最核心、最有趣的地方，因为它引入了一个随机概率。

1. 先搞定最底层：毫无疑问，新节点肯定是要加入最底层链表的，就像普通人来公司，最起码得有个工位，我们根据第一步记录的信息，把新节点插入到最底层它该在的位置上，改变一下前后节点的指针指向，这一步和普通链表插入没区别。

2. 激动人心的“抛硬币”环节：现在要决定这个新节点能建多高的“塔”，也就是它能有几层索引，这不是预先定好的，而是通过一个类似抛硬币的随机过程决定的。

   • 规则很简单：我们先假设新节点现在只有第1层，然后我们开始“抛硬币”（在程序里就是生成一个随机数）。
   • 如果硬币是正面：恭喜，这个节点获得升级！我们给它加一层，比如从第1层升到第2层，我们继续抛硬币。
   • 如果硬币是反面：游戏结束，这个节点就保持当前层数，不再继续升高。

   （资料来源：Redis源码）Redis实际使用的随机方法更工程化一点，但核心思想就是这样一个概率为1/2的伯努利试验，这意味着，大约有一半的节点只有1层，四分之一的节点有2层，八分之一的节点有3层……以此类推，节点的层数会限制在一个最大值（Redis里是32层），防止无限高。

3. 连接高层索引：如果新节点通过“抛硬币”幸运地拥有了第2层或更高层，那么我们就需要把这些高层的索引也接入跳表的相应层次中，怎么接呢？这时候第一步记录的那个“前驱节点”数组就派上用场了，对于新节点的每一层i，我们找到在第一步中记录的第i层的前驱节点，然后像普通链表插入一样，把新节点的第i层指针指向后继节点，再让前驱节点的第i层指针指向新节点，这样就完成了在高层索引的插入。

总结一下为啥有意思：

你看,整个插入过程结合了确定的算法（二分查找思想的查找路径）和不确定的概率（随机决定节点层数），它不需要像平衡树那样在插入后进行复杂的旋转操作来维持平衡，而是通过“听天由命”的随机性，在概率上保证整个跳表的结构大致是平衡的，从而实现了接近平衡树的效率（平均O(logN)），但实现起来却简单直观得多，这种用随机性换取简洁和效率的思想，正是跳表设计的精妙和趣味所在，Redis选择它作为有序集合的底层实现之一，就是看中了它在性能和实现复杂度之间的完美权衡。