当前位置:首页 > 数据库 > 正文内容

Redis的ZSet底层数据结构,ZSet类型全面解析

邻居的猫1个月前 (12-09)数据库919

文章目录

一、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值升序摆放

留意事项

  1. 有序调集中的元素是仅有的,但分数(score)能够重复。
  2. 刺进、删去、查找的时刻杂乱度都是 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底层数据结构,你真的懂了吗?

扫描二维码推送至手机访问。

版权声明:本文由51Blog发布,如需转载请注明出处。

本文链接:https://www.51blog.vip/?id=556

分享给朋友:

“Redis的ZSet底层数据结构,ZSet类型全面解析” 的相关文章

Sql根底

Sql根底

1. sql根底 1.1. 数据库常用的数据类型 1.2. 带n与不带n的差异 1.3. 带var与不带var的差异 1.4. 2.根底操作 1.4.1. 更新句子 1.4.2. 删去句子 1.4.3. 束缚 1.4.4. 修正表结构 1.4.5. 查询表 1.4.6. 含糊查询 _ % [...

一文聊清楚Redis主从复制原理

一文聊清楚Redis主从复制原理

本地缓存带来的应战 分布式缓存比较于本地缓存,在完结层面需求重视的点有哪些不同。整理如下: 维度 本地缓存 会集式缓存 缓存量 受限于单机内存巨细,存储数据有限 需求供给给分布式体系里边一切节点一同运用,关于大型体系而言,对会集式缓存的容量诉求十分的大,远超单机内存的容量巨细。 可靠性 影响有限,只...

oracle查看当前用户,Oracle数据库中查看当前用户的方法详解

oracle查看当前用户,Oracle数据库中查看当前用户的方法详解

在Oracle数据库中,你可以使用`USER`或`SYS_CONTEXT`来查看当前用户。下面是两个查询的示例:1. 使用`USER`:```sqlSELECT USER FROM DUAL;```2. 使用`SYS_CONTEXT`:```sqlSELECT SYS_CONTEXT FROM DU...

专科大数据就业前景,机遇与挑战并存

专科大数据就业前景,机遇与挑战并存

1. 人才需求旺盛: 大数据技术已经广泛应用于生活、工作及城市规划中,人才需求量不断增长。未来的人工智能、云计算、物联网等领域都与大数据紧密相关,大数据人才需求量将爆发式增长。2. 主要就业方向: 专科大数据专业的毕业生在大数据时代具备广泛的就业前景,可以从事数据分析、技术开发,以及与其他行...

数据库考试题,全面掌握数据库基础知识

数据库考试题,全面掌握数据库基础知识

1. 数据库设计: 请简述关系模型的基本概念,包括实体、属性、关系等。 请解释什么是第一范式、第二范式和第三范式,并举例说明它们在数据库设计中的应用。 请描述数据冗余和范式之间的关系,并解释为什么降低数据冗余可以提高数据库的性能。2. SQL语言: 请编写一个SQL查询语句,...

oracle数据库卸载,彻底清除系统痕迹

oracle数据库卸载,彻底清除系统痕迹

Oracle数据库的卸载过程可能因操作系统和Oracle版本的不同而有所差异。以下是一个通用的卸载步骤,适用于大多数情况:1. 停止所有Oracle服务: 打开命令提示符(Windows)或终端(Linux/Unix)。 输入 `services.msc`(Windows)或 `ps e...