跳表

二分查找是依赖数组随机访问的特性。如果数据是存储在链表中，则要对链表进行改造，支持类似二分的查找算法。改造后的数据结构叫做跳表。

跳表是一种各方面性能都比较优秀的动态数据结构。可以支持快速的插入删除查找，甚至可以替代红黑树。

Redis中的有序集合(Sorted Set)就是用跳表来实现的。

如何理解

对于单链表查找数据只能从头到尾遍历，O(n)。

加上一层索引之后，查找一个结点需要遍历的结点数减少了，也就是查找效率提高了。

当链表的长度比较大时，在构建索引之后，查找效率的提升就会非常明显。

这种链表加多级索引的结构就是跳表。

O(logn)

等比数列求和。空间复杂度还是O(n)。
在实际的软件开发中，原始链表存储的可能是很大的对象，索引结点只需要存储关键值和几个指针，并不需要存储对象，所以当对象比索引节点大很多时，索引占用的额外空间就可以忽略了。

插入操作时间复杂度也是O(logn)。先要查找要插入的位置，再插入结点。
删除操作是，如果这个结点在索引中也有出现，除了删除原始链表汇总的结点，还要删除索引中的。在查找要删除的结点的时候，一定要获取前驱结点。如果使用的是双向链表，就不用考虑这个问题。

如果不停插入数据而不更新索引，就有可能出现某两个索引节点之间数据非常多的情况，极端情况下，跳表会退化为单链表。

可以通过随机函数来维护平衡性。

随机函数生成了值K，那么久将这个结点添加到第一级到第K级这K级索引中。

Redis有序集合支持的核心操作包括：（1）插入（2）删除（3）查找（4）按照区间查找数据（5）迭代输出有序序列

其中,插入、删除、查找以及迭代输岀有序序列这几个操作,红黑树也可以完成,时间复杂度跟跳表是一样的。但是,按照区间来查找数据这个操作,红黑树的效率没有跳表高。