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

南飓风 · 2024-11-3 18:08:22

文章目录
一、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，只能一个个遍历，效率仍没有很高效。

属性类型长度阐明zlbytesuint32_t4字节一个 4 字节的整数，表现整个压缩列表占用的字节数目，包括自身的大小zltailuint32_t4字节一个 4 字节的整数，记录压缩列表表尾节点距离压缩列表的起始所在有多少字节，通过这个偏移量，可以确定表尾节点的所在zllenuint16_t2字节一个 2 字节的整数，表现压缩列表中的节点数目。最大值为UINT16_MAX（65534），假如超过这个数，此处会记录为65535，但节点的真实数目需要遍历整个压缩列表才能盘算出entry列表节点不定压缩列表中的元素，每个元素都由一个或多个字节组成，节点的长度由节点生存的内容决定。每个元素的第一个字节（又称为"entry header"）用于表现这个元素的长度以及编码方式zlenduint8_t1字节一个字节，特别值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+树、跳表的比力

[table][tr]数据结构实现原理key查询方式查找效率存储大小插入、删除效率[/tr][tr][td]Hash[/td][td]哈希表[/td][td]支持单key[/td][td]接近O(1)[/td][td]小，除了数据没有额外的存储[/td][td]O(1)[/td][/tr][tr][td]B+树[/td][td]平衡二叉树扩展而来[/td][td]单key，范围，分页[/td][td]O(logn)[/td][td]除了数据，还多了左右指针，以及叶子节点指针[/td][td]O(logn)，需要调整树的结构，算法比力复杂[/td][/tr][tr][td]跳表[/td][td]有序链表扩展而来[/td][td]单key，分页[/td][td]O(logn)[/td][td]除了数据，还多了指针，但是每个节点的指针小于

		自动登录	找回密码
密码			立即注册

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

本帖子中包含更多资源

0 个回复

快速回复

楼主热帖

标签云

浏览过的版块

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

本帖子中包含更多资源

0 个回复

快速回复

楼主热帖

标签云

浏览过的版块

登录参与点评抽奖加入IT实名职场社区