【Redis】14. 跳跃表（SkipList） — 为什么 Redis 使用跳跃表来实现有序集合（Sorted Set）而不是红黑树或者平衡二叉树呢？
Redis 的有序集合（Sorted Set）就是用跳表来实现的。跳跃表是一种随机化的数据结构。我们可以把他看做 Java 中 SortedSet 和HashMap 的结合体，set 保证了value 值就有唯一性，且可以保证每一个value 有一个自己的权重值 socre ，用socre 达到排序的目的。
问题
一个单链表的结构无论是不是有序的，遍历都是从头到尾进行遍历，时间复杂度为 O(n)，有的人说了，用二分法，二分法是针对数组进行查找的一种方法，而链表不可以，链表逻辑上是连续的，物理存储上是不连续的。数组不支持随机的插入和删除，所以我们选择采用链表的形式。那有没有一种可以提高有序链表查询效率的方法。—— 加索引
什么是跳表
不加索引 如果不加索引，我们找18这个节点，则需要遍历12个节点后才可以找到。
添加一级索引 ：我们先遍历一级索引，则只需要遍历8个节点后就可以找到。
添加二级索引：我们需要先遍历二级索引，在遍历一级索引，最终只需要 遍历7个节点
对有序链表加了多级索引的结构，就是跳表，我们通过加索引，减少了查询的次数，提高到了查询效率。
此时问题来了，加索引的间隔是多少呢？上述链表中每隔两个节点建一个索引，顶级索引是有两个结点的，加入链表长度为 n ，一级索引长度为 n/2，二级索引长度为 n/4,三级索引长度为n/8，k 级索引长度n/(2^k),顶级索引长度为2，索引总长度为它们之和,则空间复杂度为O(n),跳表的高度为 O(logn)。
有序链表加了索引就是跳表，它实际上用到了一种空间换时间的思想，其实我们无需考虑这些额外的额空间。
跳表更新
跳表可以实现动态的插入和删除，有一种这样的插入情况，在两个节点之间插入了大量的数据，此时跳表退化为单链表，那跳表是如何维护自己的平衡性的呢？— 随机函数
随机函数为2，则可以对该数据插入第一级和第二级索引。就是增加数据的时候，适当的增加索引。
为什么 redis 实现有序集合不用红黑树或者平衡二叉树呢？
- 在实现方面，红黑树实现更加复杂，跳跃表实现比较简单，也更加直观，更加灵活。
- 跳表区间查找数据的效率更高一些。
- 红黑树/平衡二叉树这种树形结构，每次每隔两个节点建一个索引，而跳跃表可以多个节点，不限于两个节点。
- 跳跃表插入或删除操作只需要修改节点前后的指针，而不需要对多个节点都进行调整，而平衡二叉树则需要左旋或者右旋实现平衡。
- 从内存占用上来说，skiplist比平衡树更灵活一些。一般来说，平衡树每个节点包含2个指针（分别指向左右子树），而skiplist每个节点包含的指针数目平均为1/(1-p)，具体取决于参数p的大小。如果像Redis里的实现一样，取p=1/4，那么平均每个节点包含1.33个指针，比平衡树更有优势。
参考博客