学习笔记之跳表
[学习笔记] - 跳表
二分查找底层依赖的是数组随机访问的特性，所以只能用数组来实现。针对对链表可以稍加改造，就可以支持类似“二分”的查找算法 - 跳表（Skip list） ，支持快速地插入、删除、查找操作，时间复杂度都是 O(logn)。
跳表 SkipList - 空间换时间
Redis有序集合（ZSET）常用操作：
插入一个数据；删除一个数据；查找一个数据；按照区间查找数据（比如查找值在[100, 356]之间的数据）；迭代输出有序序列。
插入、删除、查找以及迭代输出有序序列这几个操作，红黑树也可以完成，时间复杂度跟跳表是一样的。但是，按照区间来查找数据这个操作，红黑树的效率没有跳表高。
上述结构只能遍历链表进行查找，O(n)
对链表建立索引，从底层数据提前节点到上一级，down指针指向下一级节点。
建立多级索引提高查询效率。
- 比较 21， 比 21 大，往后面找
- 比较 37, 比 37大，比链表最大值小，从 37 的下面一层开始找
- 比较 71, 比 71 大，比链表最大值小，从 71 的下面一层开始找
- 比较 85， 比 85 大，从后面找
- 比较 117， 等于 117， 找到了节点。
缺点： 占用多余存储空间。
索引更新
插入数据的时候，我们可以选择同时将这个数据插入到部分索引层中，可 通过一个随机函数，来决定将这个结点插入到哪几级索引中，比如随机函数生成了值 K，那我们就将这个结点添加到第一级到第 K 级这 K 级索引中。
漫画：什么是跳表？
https://zhuanlan.zhihu.com/p/53975333
面试题之跳表
https://mp.weixin.qq.com/s/sYFejeczLqE3PbmpiRLzkQ
Redis 跳表（一种高性能的动态数据结构）
https://yq.aliyun.com/articles/701175