在有序链表中查询某个数据需要遍历链表，时间复杂度为O(n)。跳表可以提升有序链表的查询性能。
跳表是有序链表加多级索引的结构，通过空间换时间的思路，将有序链表查询的时间复杂度降低到O(logn)。
跳表
在上图的跳表中查找值为10的数据，首先会在第二级索引中的[1]开始查找，找到[7]和[13]，确认10 在[7,13]范围内；继续在第二级索引的[7]开始查找，找到[9]和[13]，确认10 在[9,13]范围内；继续在原始链表从[9]开始查找，找到[10]。
为了保证链表的有序性，在插入和删除时，需要先查找，所以跳表的插入和删除操作的时间复杂度是O(logn)。
为什么Redis要用跳表实现有序集合？
首先看下有序集合常见的操作
- 插入一个数据；
- 删除一个数据；
- 查找一个数据；
- 按照区间查找数据；
- 迭代输出有序序列；
跳表的优势
- 按照区间查找数据的操作，跳表比其他数据结构（比如红黑树）性能高，时间复杂度O(logn)。
- 跳表代码实现比较简单。
- 跳表比较灵活，可以通过改变索引构建策略，有效平衡执行效率和内存消耗。
