关于redis:redis源码跳跃表

30次阅读

共计 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)

跳跃表实现

结构图如下

正文完
 0