链表
跳表是指建立了多层索引的链表，首先来看一下链表的结构：
跳表
在链表的基础上增加多级索引：
上图中，每一级索引都是在前一级中每隔两个节点抽一个作为索引。
n复杂度分析
mO(m*log n)1011018O(log n)n| 第一层 | 第二层 | 第三层 | …… | 第n-1层 | 第n层 | |
|---|---|---|---|---|---|---|
| 节点数 | n 2 \frac{n}{2} 2n | n 4 \frac{n}{4} 4n | n 8 \frac{n}{8} 8n | …… | 4 | 2 |
n-2O(n)动态数据处理
①插入数据，为了维持有序性，首先找到插入位置，O(logn)，在执行插入操作 O(1)
②删除数据，查找到要删除的节点（也要查找它的前驱节点），若在索引中存在，则也要删除索引中的节点。
思考：当频繁的进行插入和删除后，可能导致某级索引两个节点之间数据量很大，而部分索引节点间没有数据，导致查询性能下降，如何避免？
更新索引
类似红黑树、AVL 树，在插入删除操作后需要对树进行平衡。
跳表中插入一个数据，可以采用随机数来选择是否要添加所引，并且添加到第几级索引
Redis 有序集合
Redis 中的有序集合是采用跳表实现的，为什么不用红黑树而要使用跳表实现呢？
首先：Redis 中的有序集合操作有插入，删除，查找，按区间查找，迭代输出有序集合
可以发现一个特殊的操作：按区间查找，红黑树效率没有跳表高。
另外，跳表实现简单，可读性比红黑树好，但缺点是实际开发中需要自己实现。