zset底层数据结构(zset的数据结构)
本篇文章给大家谈谈zset底层数据结构,以及zset的数据结构对应的知识点,希望对各位有所帮助,不要忘了收藏本站喔。
本文目录一览:
Redis ZSet底层实现
有序集合对象是有序的。与列表使用索引下标作为排序依据不同,有序集合为每个元素设置一个分数(score)作为排序依据
字典的键保存元素的值,字典的值则保存元素的分值;跳跃表节点的 object 属性保存元素的值,跳跃表节点的 score 属性保存元素的分值。
假如我们单独使用 字典,虽然能以 O(1) 的时间复杂度查找成员的分值,但是因为字典是以无序的方式来保存集合元素,所以每次进行范围操作的时候都要进行排序;假如我们单独使用跳跃表来实现,虽然能执行范围操作,但是查找操作有 O(1)的复杂度变为了O(logN)。因此Redis使用了改扮两种数据结构来共同实现有序集合。
字典中的键是唯一的,可以通过key来查找值
跳跃表(skiplist)是一种有序数据结构,它通搭游过在每个节点中维持多个指向其它节点的指针,知歼销从而达到快速访问节点的目的。
转自:
[img]Redis中hash、set、zset的底层数据结构原理
Redis-哈希对象(hash)
Redis-集合对象(set)
其中hashtable的key为set中元素的值氏族,而value为null
inset为可慎雹以理解为数组,使用inset数据结构需要满足下述两个条件:
intset的底层结构
查询方式一般采用二分查找法,实际查询复杂度也就在log(n)
Redis-有序集合对象(zset)
底层实现为 字典(dict) + 跳歼孝弊表(skiplist),当数据比较少的时候用ziplist编码结构存储。
同时满足以下两个条件采用ziplist存储:
ziplist存储方式
总结
Redis - zset底层数据结构实现
zset为有序的,自动去重的集合数据类型,zset数据结构底层实现为字典(dict) + 跳表(skiplist),当数据比较少时,用ziplist编码结构存储,element和score各占一个entry.
ele1 - score1 - ele2 - score2 ...
redis.conf有以下两个参数控制
zset-max-ziplist-entries 128 // 元素个数超过128,将用skiplist编码
zset-max-ziplist-value 64 // 单个元素大小超过64byte,将用skiplist编码
加入的元素个数较少,且key的长度小于64byte时,使用ziplist有序存储元素。
往zset添加一个长度为65byte的key,此时底层选用skiplist存储元素。
利用dict可以以O(1)时间复杂度判断某个key'是否存在,以及取出key的分值。
skiplist是一个有多个索引层,一个数据层的数据结构,索引层和数据层都是有序的双向列表。
每个索引层的元素,都有两个指针字段,分别指向当前索引层下一个元素,以及下一索引层的本元素。
索引层1: 23 ----------- 52 ----------- 65 --------------- 76 ---------- null
索引层2: 23 ----43---- 52 ----59---- 65 -----70------- 76 ----84---- null
数据层: 23 -32-43-47- 52 -55-59-61- 65 --67-70-74- 76 -79-84--86-null
N: 节点数量
index: 1 --- N/2^1
index: 2 --- N/2^2
index: 3 --- N/2^3
index: k --- N/2^k
顶层只有两个首答元素: 2^k = N / 2 --- k = log2(N-1)
时间者瞎慧复杂度:神尘每一个索引层最多查找两次,层数为 log2(N-1) --- 2 * log2(N-1) = log(N),与二分查找时间复杂度一样。
搞懂Redis(二)-5:Zset数据结构
Zset有序集合和set相同在于成员不重复. 不同的是,有序集合的元素是可以排序的.但是它和列表使用的索引下标作为排序依据不同,它给每个元素设置一个分数,作为排序依据.
Zset底层数据结构:zipList和skipList
Zset也使用zipList做了手团排序.
每个集合元素使用两个紧挨在一起的压缩列表节点来保存,第一个节点保存元素的成员(member),第二个保存元素的分值(score)
结构图如下:
与dict结合使用,结构较复杂
我们先看下链表
如果要查找到node5,需要从node1查到node5,查询旅搜耗时.
如果在node上加上索引:
Redis的跳表结构
右侧是4个zskiplistNode结构,包含毕镇橘以下属性
关于zset底层数据结构和zset的数据结构的介绍到此就结束了,不知道你从中找到你需要的信息了吗 ?如果你还想了解更多这方面的信息,记得收藏关注本站。