共计 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)
跳跃表实现
结构图如下
正文完