rediszset底层数据结构（redis底层数据如何实现）

本篇文章给大家谈谈rediszset底层数据结构，以及redis底层数据如何实现对应的知识点，希望对各位有所帮助，不要忘了收藏本站喔。

本文目录一览：

• 1、redis数据结构
• 2、Redis - zset底层数据结构实现
• 3、Redis ZSet底层实现
• 4、搞懂Redis（二）-5：Zset数据结构
• 5、Redis中hash、set、zset的底层数据结构原理

redis数据结构

redis数据结构

Redis是一种存储key-value的内存型数据库，它的key都是字符串类型，value支持存储5种类型的数据：String（字符串类型）、List（列表类型）、Hash（哈希表类型、即key-value类型）、Set（无序集合类型，元素不可重复）、Zset（有序集合类型，元素不可重复）。

针对这5种数据类型，Redis在底层都是使用的redisObject对象表示的。redisObject有3个重要的属性：type、encoding、ptr。

其中，type表示value的数据类型，也就是我们上面说的5种数据类型（REDIS_STRING、REDIS_LIST、REDIS_HASH、REDIS_SET、REDIS_ZSET）；encoding表示value的编码，即底层使用了哪种数据结构；ptr是一个指向保存value的底层数据结构的指针。

其中type和ptr属性不用做过多的解释，一看就知道什么意思，本篇文章主要分析value的encoding编码，也就是不同数据类型的value对应的底层数据结构是什么以及数蔽余据结构的原理分析。

Redis（Remote Dictionary Server )，即远程字典服务，是一个开源的使用ANSI C语言编写、支持网络、磨清可基于内存亦可持久瞎并前化的日志型、Key-Value数据库，并提供多种语言的API。

redis是一个key-value存储系统。和Memcached类似，它支持存储的value类型相对更多，包括string(字符串)、list(链表)、set(集合)、zset(sorted set --有序集合)和hash（哈希类型）。这些数据类型都支持push/pop、add/remove及取交集并集和差集及更丰富的操作，而且这些操作都是原子性的。

在此基础上，redis支持各种不同方式的排序。与memcached一样，为了保证效率，数据都是缓存在内存中。区别的是redis会周期性的把更新的数据写入磁盘或者把修改操作写入追加的记录文件，并且在此基础上实现了master-slave(主从)同步。

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 ZSet底层实现

有序集合对象是有序的。与列表使用索引下标作为排序依据不同，有序集合为每个元素设置一个分数（score）作为排序依据

字典的键保存元素的值，字典的值则保存元素的分值；跳跃表节点的 object 属性保存元素的值，跳跃表节点的 score 属性保存元素的分值。

假如我们单独使用 字典，虽然能以 O(1) 的时间复杂度查找成员的分值，但是因为字典是以无序的方式来保存集合元素，所以每次进行范围操作的时候都要进行排序；假如我们单独使用跳跃表来实现，虽然能执行范围操作，但是查找操作有 O(1)的复杂度变为了O(logN)。因此Redis使用了改扮两种数据结构来共同实现有序集合。

字典中的键是唯一的，可以通过key来查找值

跳跃表（skiplist）是一种有序数据结构，它通搭游过在每个节点中维持多个指向其它节点的指针，知歼销从而达到快速访问节点的目的。

转自：

搞懂Redis（二）-5：Zset数据结构

Zset有序集合和set相同在于成员不重复. 不同的是,有序集合的元素是可以排序的.但是它和列表使用的索引下标作为排序依据不同,它给每个元素设置一个分数,作为排序依据.

Zset底层数据结构:zipList和skipList

Zset也使用zipList做了手团排序.

每个集合元素使用两个紧挨在一起的压缩列表节点来保存,第一个节点保存元素的成员(member),第二个保存元素的分值(score)

结构图如下:

与dict结合使用,结构较复杂

我们先看下链表

如果要查找到node5,需要从node1查到node5,查询旅搜耗时.

如果在node上加上索引:

Redis的跳表结构

右侧是4个zskiplistNode结构,包含毕镇橘以下属性

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存储方式

总结

[img]

关于rediszset底层数据结构和redis底层数据如何实现的介绍到此就结束了，不知道你从中找到你需要的信息了吗 ？如果你还想了解更多这方面的信息，记得收藏关注本站。