Redis的ZSet底层数据结构,ZSet类型全面解析
文章目录
一、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),只用处理链表,算法比较简略 |
参阅
Redis常见面试题:ZSet底层数据结构,SDS、紧缩列表ZipList、跳表SkipList
Redis数据结构:Zset类型全面解析
redis的zset底层数据结构,你真的懂了吗?