前言
时间复杂度O(logn)的二分查找很高效，但是依赖数组随机访问的特性，如果是链表，如何做到O(logn)？
跳表
原始链表查找时，需要遍历链表，时间复杂度就是O(n)，光靠原始链表是不行的。
我们可以增加辅助链表，达到索引的作用，使用起来类似二叉搜索树。
查找时，从上往下，一层一层的查找，类似二叉搜索树。索引层可以继续增加，效率会得到提升。
极限情况下，索引层高度为log2n-1，总高度为log2n。
每一层最多遍历3个节点（我认为遍历2个就够，k-1层的z是不用遍历的，在k 1层已经遍历过了，下面是老老师的解释），此时查找时间复杂度为O(logn)，和二分查找相同。
假设我们要查找的数据是x，在第k级索引中，我们遍历到y结点之后，发现x大于y，小于后面的结点z，所以我们通过y的down指针，从第k级索引下降到第k-1级索引。在第k-1级索引中，y和z之间只有3个结点（包含y和z），所以，我们在K-1级索引中最多只需要遍历3个结点，依次类推，每一级索引都最多只需要遍历3个结 点。
跳表是不是很浪费内存？
使用跳表时，要想效率高，就需要创建更多的索引层，也就是空间换时间的思想。在如何权衡空间与时间之前，我们得搞清楚，空间占用具体有多少，才好去做取舍。
假设原始链表大小为n，那第一级索引大约有n/2个结点，第二级索引大约有n/4个结点，以此类推，每上升一级就减少一半，直到剩下2个结点。也就是计算这棵二叉树的节点数 - 叶子节点数 - 根节点。索引层的结点总和就是n/2 n/4 n/8… 8 4 2=n-2。所以，跳表的空间复杂度是O(n)。
调整策略，两个节点取一个索引节点改为三个节点取一个索引节点，看看时间和空间复杂度变化。
总的索引结点大约就是n/3 n/9 n/27 … 9 3 1=n/2，空间占用减少一半。时间复杂度为3*log3n。
在实际开发中，一般不用太在意这里额外使用的内存，毕竟链表里保存的是元素指针，相对于元素所占的空间而言，微乎其微。
高效的动态插入和删除
已知插入节点，链表的插入时间复杂度为O(1)，但要找到插入节点需要O(n)，在跳表中，查询降到了O(logn)，所以插入和删除也是O(logn)。
跳表索引动态更新
当我们不停地往跳表中插入数据时，如果我们不更新索引，就有可能出现某2个索引结点之间数据非常多的情况。极端情况下，跳表还会退化成单链表。
作为一种动态数据结构，我们需要某种手段来维护索引与原始链表大小之间的平衡，也就是说，如果链表中结点多了，索引结点就相应地增加一些，避免复杂度退化，以及查找、插入、删除操作性能下降。当我们往跳表中插入数据的时候，我们可以选择同时将这个数据插入到部分索引层中。如何选择加入哪些索引层呢？ 我们通过一个随机函数，来决定将这个结点插入到哪几级索引中，比如随机函数生成了值K，那我们就将这个结点添加到第一级到第K级这K级索引中。随机函数的选择很有讲究，从概率上来讲，能够保证跳表的索引大小和数据大小平衡性，不至于性能过度退化。
为什么Redis要用跳表来实现有序集合，而不是红黑树？
Redis中的有序集合是通过跳表来实现的，严格点讲，其实还用到了散列表。
Redis中的有序集合支持的核心操作主要有下面这几个：
- 插入一个数据
- 删除一个数据
- 查找一个数据
- 按照区间查找数据（比如查找值在[100, 356]之间的数据）
- 迭代输出有序序列
其中，插入、删除、查找以及迭代输出有序序列这几个操作，红黑树也可以完成，时间复杂度跟跳表是一样的。但是，按照区间来查找数据这个操作，红黑树的效率没有跳表高，跳表可以做到O(logn)的时间复杂度定位区间的起点，然后在原始链表中顺序往后遍历就可以了。这样做非常高效。 当然，Redis之所以用跳表来实现有序集合，还有其他原因。
- 跳表相对于红黑树来说更简单。
- 跳表更加灵活，它可以通过改变索引构建策略，有效平衡执行效率和内存消耗。
Redis不同场景选择不同的底层数据结构
Redis的对象系统中的每种对象实际上都是基于使用场景选择多种底层数据结构实现的，体现了Redis对于性能极致的追求。
- ZSET就是基于【压缩列表】或者【跳跃表 字典】
- 字符串存储底层可能是int、embstr、raw，int 类型很好理解，整数类型对应的就是 int 类型，而字符串则对应是 embstr 类型，当字符串长度大于 44 字节时，会变为 raw 类型存储。
参考
数据结构与算法之美——极客时间
Redis 核心技术与实战——极客时间
Post Views: 6
