共计 569 个字符，预计需要花费 2 分钟才能阅读完成。
前言
跳跃表 (skiplist) 是一种有序的数据结构，是在 有序链表 的根底上进行了扩大，解决了有序链表查找某个值效率问题。跳跃表反对均匀 O(logn)、最坏 O(n) 复杂度的节点查找，大部分状况效率能够和均衡树相媲美，且实现更简略。Redis 应用跳跃表作为 有序汇合键 的底层实现之一。
根本介绍
跳跃表作为有序汇合的底层实现之一，咱们先来看有序汇合的简略用法。
> zadd fruit 10 banana
(integer) 1
> zadd fruit 12 apple
(integer) 1
> zadd fruit 8 cherry
(integer) 1
> zrange fruit 0 -1 #按 score 有序取出
1) "cherry"
2) "banana"
3) "apple"原理
有序链表的查找
如上面的有序链表
从该有序表中搜寻元素 < 5, 23, 40 >，须要比拟的次数别离为 < 2, 4, 6 >，总共比拟的次数为 2 + 4 + 6 = 12 次。
那有没有优化的算法呢?
思考链表是有序的，但不能应用二分查找。相似二叉搜寻树，咱们把一些节点提取进去，作为索引。失去如下构造：
这里咱们把 < 4, 8, 34, 45 > 提取进去作为一级索引，这样搜寻的时候就能够缩小比拟次数了。
咱们还能够再从一级索引提取一些元素进去，作为二级索引，变成如下构造：
因为相似二分查找，效率失去进步，查找均匀复杂度能够达到 O(logn)
跳跃表实现
结构图如下
正文完