首页 > 极客资料 博客日记
Redis的ZSet底层数据结构,ZSet类型全面解析
2024-11-03 20:00:08极客资料围观16次
文章目录
一、ZSet有序集合类型
- 1.1 简介
- 1.2 应用场景
- 1.3 底层结构
- 1.4 ZSet常用命令
二、ZSet底层结构详解
-
2.1 数据结构
-
2.2 压缩列表ZipList
-
2.3 跳表详解
- 2.3.1 跳表是什么(what)
- 2.3.2 跳表怎么做的(how)
- 2.3.3 为什么需要跳表(WHY)/跳表高效的动态插入和删除
- 2.3.4 ZSet中的跳表
-
2.4 什么时候采用压缩列表、什么时候采用跳表
三、Redis跳表与MySQL B+树
- 3.1 对比
- 3.2 MySQL为什么用B+树,而不是跳表
- 3.3 ZSet为什么用跳表,而不是B+树/红黑树/二叉树
四、Hash、B+树、跳表的比较
一、ZSet有序集合类型
1.1 简介
详细介绍:Redis五种数据类型、String、List、Set、Hash、ZSet
ZSet(有序集合)即SortedSet,是一个自动根据元素score排序的有序集合。它是一个可排序的set集合,在 Set 的基础上增加了一个权重参数 score,使得集合中的元素能够按 score 进行有序排列。在 Redis 中,有序集合的最大成员数是 2^32 - 1。ZSet具备下列特性:
- 可排序。根据score值排序,如果多个元素score相同 则会按照字典进行排序
- 元素不重复,member必须唯一。注意:集合成员是唯一的,但评分可以重复
- 查询速度快,也可以根据member查询分数
在 Zset 中,集合元素的添加、删除和查找的时间复杂度都是 O(logn),这得益于 Redis 使用跳表SkipList来实现 Zset。
因为ZSet的可排序特性,经常被用来实现排行榜这样的功能。
1.2 应用场景
- 排行榜应用:有序集合使得我们能够方便地实现排行榜,比如网站的文章排行、学生成绩排行等。
- 带权重的消息队列:可以通过 score 来控制消息的优先级。
- 时间线:使用 Zset 来实现时间线功能。例如将发布的消息作为元素、消息的发布时间作为分数,然后用 Zset 来存储和排序所有的消息。你可以很容易地获取到最新的消息,或者获取到任何时间段内的消息。
- 延时队列:你可以将需要延时处理的任务作为元素,任务的执行时间作为分数,然后使用 Zset 来存储和排序所有的任务。你可以定期扫描 Zset,处理已经到达执行时间的任务。
以上只是 ZSet 的一些常见应用场景,实际上Zset 的应用非常广泛,只要是需要排序和排名功能的场景,都可以考虑使用 ZSet。
1.3 底层结构
ZSet与Java中的TreeSet有些类似,但底层数据结构却差别很大。ZSet中的每一个元素都带有一个score属性,可以基于score属性对元素排序。底层实现有两种方式:当元素较少或总体元素占用空间较少时,使用压缩列表ZipList来实现;当不符合使用压缩列表的条件时,使用跳表SkipList+ 字典hashtable来实现。注意,集合成员是唯一的,但是评分可以重复。
-
Redis ZSet 的底层实现为跳跃列表和哈希表两种,跳跃列表保证了元素的排序和快速的插入性能,哈希表则提供了快速查找的能力。
-
当元素数量不多时,HT和SkipList的优势不明显,而且更耗内存。因此zset还会采用ZipList结构来节省内存,不过需要同时满足两个条件:
- 元素数量小于zset_max_ziplist_entries,默认值128
- 每个元素都小于zset_max_ziplist_value字节,默认值64
补充:ziplist本身没有排序功能,而且没有键值对的概念,因此需要有zset通过编码实现:
- ZipList是连续内存,因此score和element是紧挨在一起的两个entry,element在前,score在后
- score越小越接近队首,score越大越接近队尾,按照score值升序排列
注意事项:
- 有序集合中的元素是唯一的,但分数(score)可以重复。
- 插入、删除、查找的时间复杂度都是 O(log(N))。对于获取排名(排行榜)的操作,Redis 有序集合是非常高效的。
1.4 ZSet常用命令
ZSet的常见命令有:
- ZADD key [NX|XX] [CH] [INCR] score member [score member ...] :添加一个或多个元素到zset ,如果已经存在则更新其score值
- ZREM key member [member ...] :删除zset中的一个指定元素
- ZSCORE key member : 获取zset中的指定元素的score值
- ZRANK key member:获取指定元素在zset 中的排名(从0开始)
- ZCARD key:获取zset中的元素个数
- ZCOUNT key min max:统计score值在给定范围内的所有元素的个数
- ZINCRBY key increment member:让zset中的指定元素自增,步长为指定的increment值
- ZRANGE key start stop [WITHSCORES]:按返回有序集合中的,下标在
之间的元素(有 WITHSCORES 会显示评分) - zrevrange key start stop [WITHSCORES] :
- ZRANGEBYSCORE key min max [WITHSCORES] [LIMIT offset count]:返回score值介于
到 之间(含两端)的成员,limit offset count即是偏移数目(score从小到大) - zrevrangebyscore key max min [WITHSCORES] [LIMIT offset count] :根据score值从大到小排列
- ZDIFF、ZINTER、ZUNION:求差集、交集、并集
注意:所有的排名默认都是升序,如果要降序则在命令的Z后面添加REV即可,例如:
-
升序获取sorted set 中的指定元素的排名:ZRANK key member
-
降序获取sorted set 中的指定元素的排名:ZREVRANK key memeber
127.0.0.1:6379> zadd zset1 1 first 2 second 3 third 4 four #往zset添中加一个或多个元素
(integer) 4
127.0.0.1:6379> zrange zset1 0 -1 #返回有序集合中、下标在<start> <end>之间的元素(有 WITHSCORES 会显示评分)。0 -1 表示所有元素
1) "first"
2) "second"
3) "third"
4) "four"
127.0.0.1:6379> zrevrange zset1 0 -1
1) "four"
2) "third"
3) "second"
4) "first"
127.0.0.1:6379> zscore zset1 third #获取zset中的third元素的score值
"3"
127.0.0.1:6379> zrank zset1 third #返回third在集合中的排名,从0开始
(integer) 2
127.0.0.1:6379> zrevrank zset1 third
(integer) 1
127.0.0.1:6379> zrangebyscore zset1 -inf +inf #给zset集合中的元素从小到大排序,-inf:负无穷,+inf:正无穷。返回score值介于-inf到+inf之间(含两端)的成员(score从小到大)
1) "first"
2) "second"
3) "third"
4) "four"
127.0.0.1:6379> zrangebyscore zset1 -inf +inf withscores #从小到大排序并输出键值
1) "first"
2) "1"
3) "second"
4) "2"
5) "third"
6) "3"
7) "four"
8) "4"
127.0.0.1:6379> zrangebyscore zset1 -inf 1 withscores #指定负无穷到1的范围
1) "first"
2) "1"
127.0.0.1:6379> zrem zset1 four #移除zset集合中指定的元素
(integer) 1
127.0.0.1:6379> zcard zset1 #查看zset集合中元素个数
(integer) 3
127.0.0.1:6379> zrangebyscore zset1 1 2 withscores #根据score值从小到大排列
1) "first"
2) "1"
3) "second"
4) "2"
127.0.0.1:6379> zrevrangebyscore zset1 2 1 withscores #根据score值从大到小排列
1) "second"
2) "2"
3) "first"
4) "1"
127.0.0.1:6379> zcount zset1 1 2 #统计score值在1到2之间的元素个数
(integer) 2
二、ZSet底层结构详解
2.1 数据结构
有序集合Zset底层实现会根据实际情况选择使用压缩列表(ziplist)或者跳跃表(skiplist):当元素较少或总体元素占用空间较少时,使用压缩列表ZipList来实现;当不符合使用压缩列表的条件时,使用跳表SkipList+ 字典hashtable来实现。
-
Redis ZSet 的底层实现为跳跃列表和哈希表两种,跳跃列表保证了元素的排序和快速的插入性能,哈希表则提供了快速查找的能力。
-
当元素数量不多时,HT和SkipList的优势不明显,而且更耗内存。因此zset还会采用ZipList结构来节省内存,不过需要同时满足两个条件:
- 元素数量小于zset_max_ziplist_entries,默认值128
- 每个元素都小于zset_max_ziplist_value字节,默认值64
具体细节可参考本文1.3小节
2.2 压缩列表ZipList
ZipList是一种特殊的“双端链表”(并非链表),由一系列特殊编码的连续内存块组成,像内存连续的数组。可以在任意一端进行压入/弹出操作,并且该操作的时间复杂度为O(1)。
压缩列表 底层数据结构:本质是一个数组,增加了列表长度、尾部偏移量、列表元素个数、以及列表结束标识,有利于快速寻找列表的首尾节点;但对于其他正常的元素,如元素2、元素3,只能一个个遍历,效率仍没有很高效。
属性 | 类型 | 长度 | 说明 |
---|---|---|---|
zlbytes | uint32_t | 4字节 | 一个 4 字节的整数,表示整个压缩列表占用的字节数量,包括 <zlbytes> 自身的大小 |
zltail | uint32_t | 4字节 | 一个 4 字节的整数,记录压缩列表表尾节点距离压缩列表的起始地址有多少字节,通过这个偏移量,可以确定表尾节点的地址 |
zllen | uint16_t | 2字节 | 一个 2 字节的整数,表示压缩列表中的节点数量。最大值为UINT16_MAX(65534),如果超过这个数,此处会记录为65535,但节点的真实数量需要遍历整个压缩列表才能计算出 |
entry | 列表节点 | 不定 | 压缩列表中的元素,每个元素都由一个或多个字节组成,节点的长度由节点保存的内容决定。每个元素的第一个字节(又称为"entry header")用于表示这个元素的长度以及编码方式 |
zlend | uint8_t | 1字节 | 一个字节,特殊值0xFF(十进制255),表示压缩列表的结束 |
注意:
-
如果查找定位首个元素或最后1个元素,可以通过表头 “zlbytes”、“zltail_offset” 元素快速获取,复杂度是 O(1)。但是查找其他元素时,就没有这么高效了,只能逐个查找下去,比如 entryN 的复杂度就是 O(N)
-
ZipList虽然节省内存,但申请内存必须是连续空间,如果内存占用较多,申请效率较低。
2.3 跳表详解
学习一个新知识,从三方面分析:WHAT、WHY、HOW
2.3.1 跳表是什么(what)
**SkipList(跳表)**首先是链表,在有序链表的基础上,增加了多级索引,通过多级索引位置的转跳,实现了快速查找元素。但与传统链表相比有几点差异:
- 元素按照升序排列存储
- 节点可能包含多个指针,指针跨度不同
在 Redis 源码中,跳跃表的结构定义如下:
typedef struct zskiplistNode {
robj *obj;
double score;
struct zskiplistNode *backward;
struct zskiplistLevel {
struct zskiplistNode *forward;
unsigned int span;
} level[];
} zskiplistNode;
typedef struct zskiplist {
struct zskiplistNode *header, *tail;
unsigned long length;
int level;
} zskiplist;
- zskiplistNode 结构体表示跳跃表中的一个节点,包含元素对象(obj)、分数(score)、指向前一个节点的指针(backward)和一个包含多个层的数组(level)。每一层都包含一个指向下一个节点的指针(forward)和一个表示当前节点到下一个节点的跨度(span)。
- zskiplist 结构体表示一个跳跃表,包含头节点(header)、尾节点(tail)、跳跃表中的节点数量(length)和当前跳跃表的最大层数(level)。
跳表查找、插入和删除操作的时间复杂度都是 O(logN)。
SkipList的特点:
- 跳跃表是一个双向链表,每个节点都包含score和ele值
- 节点按照score值排序,score值一样则按照ele字典排序
- 每个节点都可以包含多层指针,层数是1到32之间的随机数
- 不同层指针到下一个节点的跨度不同,层级越高,跨度越大
- 增删改查效率与红黑树基本一致,实现却更简单
对于一个单链表来说,即使链表中的数据是有序的,如果我们想要查找某个数据,也必须从头到尾的遍历链表,很显然这种查找效率是十分低效的,时间复杂度为O(n)。
普通链表想查找元素27,只能从链表头部一个个往后遍历,需要遍历6次 才能找到元素27
2.3.2 跳表怎么做的(how)
跳表怎么做的(how):建立多级索引
如建立一级索引
如果觉得慢,可以建立二级索引
当数据量特别大的时候,跳表的时间复杂度为 O(logN)。其本身利用的思想,有点类似于二分法。
2.3.3 为什么需要跳表(WHY)/跳表高效的动态插入和删除
因为普通链表查找一个元素 时间复杂度O(n);而跳表查找的时间复杂度为O(logn),查找速度更快。不仅如此,删除、插入等操作的时间复杂度也是O(logn)
- 跳表这个动态数据结构,不仅支持查找操作,还支持动态的插入、删除操作,而且插入、删除操作的时间复杂度也是 O(logn)。
- 对于单纯的单链表,需要遍历每个结点来找到插入的位置。但是对于跳表来说,因为其查找某个结点的时间复杂度是 O(logn),所以这里查找某个数据应该插入的位置,时间复杂度也是 O(logn)。
2.3.4 ZSet中的跳表
SkipList作为ZSet的存储结构,整体存储结构如下图,核心点主要是包括一个dict对象和一个skiplist对象。dict保存key、value,key为元素,value为分值;skiplist保存的有序的元素列表,每个元素包括元素和分值。
上图中 zskiplist 结构包含以下属性:
- header:指向跳表的表头节点
- tail:指向跳表的表尾节点
- level:记录目前跳表内,层数最大的那个节点层数(表头节点的层数不计算在内)
- length:记录跳表的长度,也就是跳表目前包含节点的数量(表头节点不计算在内)
位于 zskiplist 结构右侧是四个 zskiplistNode 结构,该结构包含以下属性:
- 层(level):节点中用 L1、L2、L3 等字样标记节点的各个层,L1 代表第一层,L2 代表第二层,以此类推。每个层都带有两个属性:前进指针和跨度。前进指针用于访问位于表尾方向的其它节点,而跨度则记录了前进指针所指向节点和当前节点的距离。
- 后退(backward)指针:节点中用 BW 字样标识节点的后退指针,它指向位于当前节点的前一个节点。后退指针在程序从表尾向表头遍历时使用。
- 分值(score):各个节点中的 1.0、2.0 和 3.0 是节点所保存的分值。在跳跃表中,节点按各自所保存的分值从小到大排列。
- 成员对象(obj):各个节点中的 o1、o2 和 o3 是节点所保存的成员对象。
2.4 什么时候采用压缩列表、什么时候采用跳表
什么时候采用压缩列表、什么时候采用跳表呢
- 有序集合保存的元素数量小于128个
- 有序集合保存的所有元素的长度小于64字节
上述 1且2的时候,采用压缩列表;否则采用跳表
三、Redis跳表与MySQL B+树
3.1 对比
Redis跳表:
B+Tree:
MySQL B+树:
相比于标准的B+树,InnoDB使用的B+树有如下特点:
- B+ 树的叶子节点之间是用「双向链表」进行连接,既能向右遍历、也能向左遍历
- B+ 树点节点内容是数据页,数据页里存放了用户的记录以及各种信息,每个数据页默认大小是 16 KB
区别:
MySQL 的 B+ 树、Redis 的跳表都是用于存储有序数据的数据结构,但它们有一些关键的区别,使得它们在不同的场景和用途中各有优势。
-
结构差异:B+ 树是一种多路搜索树,每个节点可以有多个子节点,而跳表是一种基于链表的数据结构,每个节点只有一个下一个节点,但可以有多个快速通道指向后面的节点。
-
空间利用率:B+ 树的磁盘读写操作是以页(通常是 4KB)为单位的,每个节点存储多个键值对,可以更好地利用磁盘空间,减少 I/O 操作。而跳表的空间利用率相对较低。
-
插入和删除操作:跳表的插入和删除操作相对简单,时间复杂度为 O(logN),并且不需要像 B+ 树那样进行复杂的节点分裂和合并操作。
-
范围查询:B+ 树的所有叶子节点形成了一个有序链表,因此非常适合进行范围查询。而跳表虽然也可以进行范围查询,但效率相对较低。
因此,B+ 树和跳表不能简单地相互替换。在需要大量进行磁盘 I/O 操作和范围查询的场景(如数据库索引)中,B+ 树可能是更好的选择;而在主要进行内存操作,且需要频繁进行插入和删除操作的场景(如 Redis)中,跳表可能更有优势。
3.2 MySQL为什么用B+树,而不是跳表
MySQL是持久化数据库、即存储到磁盘上,因此查询时要求更少磁盘 IO,且 Mysql 是读多写少的场景较多,显然 B+ 树更加适合Mysql。
Redis是直接操作内存的、并不需要磁盘io;而MySQL需要去读取磁盘io,所以MySQL使用b+树的方式去减少磁盘io。B+树原理是 叶子节点存储数据、非叶子节点存储索引,每次读取磁盘页时就会读取一整个节点,每个叶子节点还要指向前后节点的指针,其目的是最大限度地降低磁盘io
数据在内存中读取 耗费时间是磁盘IO读取的百万分之一,而Redis是内存中读取数据、不涉及IO,因此使用了跳表,跳表模型是更快更简单的方式
3.3 ZSet为什么用跳表,而不是B+树/红黑树/二叉树
1)ZSet为什么不用B+树,而用跳表
-
时间复杂度优势:跳表是一种基于链表的数据结构,可以在O(log n)的时间内进行插入、删除和查找操作。而B树需要维护平衡,操作的时间复杂度较高,通常为O(log n)或者更高。在绝大多数情况下,跳表的性能要优于B树。
-
简单高效:跳表的实现相对简单,并且容易理解和调试。相比之下,B树的实现相对复杂一些,需要处理更多的情况,例如节点的分裂和合并等操作。
-
空间利用率高:在关键字比较少的情况下,跳表的空间利用率要优于B树。B树通常需要每个节点存储多个关键字和指针,而跳表只需要每个节点存储一个关键字和一个指针。
-
并发性能好:跳表的插入和删除操作比B树更加简单,因此在并发环境下更容易实现高性能。在多线程读写的情况下,跳表能够提供较好的并发性能。
总的来说,Redis选择跳表作为有序集合数据结构的底层实现,是基于跳表本身的优点:时间复杂度优势、简单高效、空间利用率高和并发性能好。这使得Redis在处理有序集合的操作时能够获得较好的性能和并发能力。Redis是内存数据库、不存在IO的瓶颈,而B+树纯粹是为了MySQL这种IO数据库准备的。B+树的每个节点的数量都是一个MySQL分区页的大小。
2)ZSet为什么不用红黑树、二叉树
红黑树、二叉树查找一个元素的时间复杂度也是O(logn)
- ZSet有个核心操作,范围查找:跳表效率比红黑树高,跳表可以做到 logn 时间复杂度内,快速查找,找到区间起点、依次往后遍历即可,但红黑树范围查找的效率没有跳表高(每一层加了指针)
- 跳表实现比红黑树及平衡二叉树简单、易懂:可以有效控制跳表的索引层级来控制内存的消耗,
四、Hash、B+树、跳表的比较
数据结构 | 实现原理 | key查询方式 | 查找效率 | 存储大小 | 插入、删除效率 |
---|---|---|---|---|---|
Hash | 哈希表 | 支持单key | 接近O(1) | 小,除了数据没有额外的存储 | O(1) |
B+树 | 平衡二叉树扩展而来 | 单key,范围,分页 | O(logn) | 除了数据,还多了左右指针,以及叶子节点指针 | O(logn),需要调整树的结构,算法比较复杂 |
跳表 | 有序链表扩展而来 | 单key,分页 | O(logn) | 除了数据,还多了指针,但是每个节点的指针小于<2,所以比B+树占用空间小 | O(logn),只用处理链表,算法比较简单 |
参考
标签:
上一篇:鸿蒙适配一多搭建首页框架
下一篇:《痞子衡嵌入式半月刊》 第 110 期
相关文章
最新发布
- Nuxt.js 应用中的 prerender:routes 事件钩子详解
- 【问题解决】Tomcat由低于8版本升级到高版本使用Tomcat自带连接池报错无法找到表空间的问题
- 【FAQ】HarmonyOS SDK 闭源开放能力 —Vision Kit
- 六、Spring Boot集成Spring Security之前后分离认证流程最佳方案
- 《JVM第7课》堆区
- .NET 8 高性能跨平台图像处理库 ImageSharp
- 还在为慢速数据传输苦恼?Linux 零拷贝技术来帮你!
- 刚毕业,去做边缘业务,还有救吗?
- 如何避免 HttpClient 丢失请求头:通过 HttpRequestMessage 解决并优化
- 让性能提升56%的Vue3.5响应式重构之“版本计数”