平衡树:为什么Redis内部实现用跳跃表
2023-02-18 15:36:19 时间
摘要:Redis使用跳跃表(skiplist)作为有序集合(zset)的底层实现之一。
本文分享自华为云社区《5分钟了解Redis的内部实现跳跃表(skiplist)》,作者:万猫学社。
跳跃表简介
跳跃表(skiplist)是一个有序的数据结构,它通过在每个节点维护不同层次指向后续节点的指针,以达到快速访问指定节点的目的。跳跃表在查找指定节点时,平均时间复杂度为,最坏时间复杂度为O(N)。
Redis使用跳跃表(skiplist)作为有序集合(zset)的底层实现之一。当有序集合的元素个数大于等于zset-max-ziplist-entries(默认为128个),或者每个元素成员的长度大于等于zset-max-ziplist-value(默认为64字节)的时候,使用跳跃表和哈希表作为有序集合的内部实现。
举个例子,我们使用zadd命令创建一个以跳跃表为实现的有序集合:
127.0.0.1:6379> zadd one-more-zset 1 long-long-long-long-long-long-long-long-long-long-long-long-long-long (integer) 1 127.0.0.1:6379> zrange one-more-zset 0 -1 1) "long-long-long-long-long-long-long-long-long-long-long-long-long-long" 127.0.0.1:6379> object encoding one-more-zset "skiplist"
跳跃表的实现
在Redis中的跳跃表是由zskiplist结构表示的,zskiplist结构包含由多个跳跃表节点组成的双向链表,每一个跳跃表节点都保存着元素成员和对应的分钟。下面我们一个一个地详细了解一下。
zskiplist结构
跳跃表是由zskiplist结构表示的,它包含以下几个属性:
- header属性: 指向头部跳跃表节点的指针。
- tail属性:指向尾部跳跃表节点的指针。
- level属性:表示跳跃表中层数最大的节点的层数,表头节点的层数不计算在内。
- length属性:表示跳跃表中的节点总数。
跳跃表节点的结构
跳跃表节点使用zskiplistNode结构表示,它包含以下几个属性:
- level属性:表示层的数组,数组中每个项使用zskiplistLevel结构表示,它包含以下两个属性:
- forward属性:指向位于表尾方向其他节点的指针。
- span属性:当前节点到forward指向的节点跨越了多少个节点。
- backward属性:指向当前节点的前一个节点的指针。
- obj属性:指向元素成员的指针。
- score属性:当前元素成员对应的分数。
图解跳跃表
说了这么多,都比较抽象不容易理解,我们来举个例子:
这就是一个跳跃表的内部结构,其中有4个元素,键分别是:万、猫、学、社。
为什么不使用平衡树?
跳跃表以有序的方式在层次化的链表中保存元素, 在大多数情况下,跳跃表的效率可以和平衡树媲美,查找、删除、添加等操作都可以在对数期望时间下完成, 并且比起平衡树来说, 跳跃表的实现要简单直观得多。所以在Redis中没有使用平衡树,而是使用了跳跃表。
相关文章
- 面试题 17.10. 主要元素
- 代码计算程序运行的时间
- 何为加速计算?加速计算为什么很重要?
- 隐私计算-Oblivious Transfer算法理论研究与实践
- 借助5G智能网关实现无人化智慧农业应用
- 代码要写到100岁--mysql之父monty见面会有感
- 【Java面试】毕业季高频面试题String,StringBuffer好和StringBuilder的区别
- 这道面试题难倒了80%的程序员:谈谈你对Netty中,Pipeline工作原理的理解?
- Java高频面试题,谈谈你对OAuth的理解,这道题你会了吗?
- 惊呆面试官的回答:HashMap和TreeMap的区别
- 这么回答面试通过率提高60%,谈谈你对RPC框架的理解
- 一次性带你搞明白面试必问题,谈谈你对ES的理解
- 级别太高,架构师面试题,谈谈你对IaaS、PaaS、SaaS的理解
- 遇到刁钻面试题如何回答Java中,4种对象引用之间的区别是什么?
- 面试官问:Spring中有几种依赖注入的方式?你能答出来吗
- 离谱!面试都这么问?那不得满分回答,谈谈你对Swagger工作流程的理解?
- flutter系列之:移动端手势的具体使用
- python字符串,用json.dumps后,转化为json字符串,里面存在转义字符了,咋整?
- web移动端实现打电话和保存到电话簿功能
- PHP设计模式 - 门面模式(Facade)通俗易懂 / 友好示例代码