IT评测·应用市场-qidao123.com技术社区

标题: Redis的ZSet底层数据结构，ZSet类型全面解析 [打印本页]
作者: 南飓风    时间: 2024-11-3 18:08
标题: Redis的ZSet底层数据结构，ZSet类型全面解析
文章目录
一、ZSet有序聚集类型
二、ZSet底层结构详解
三、Redis跳表与MySQL B+树
四、Hash、B+树、跳表的比力

一、ZSet有序聚集类型

1.1 简介

详细先容：Redis五种数据类型、String、List、Set、Hash、ZSet
ZSet（有序聚集）即SortedSet，是一个主动根据元素score排序的有序聚集。它是一个可排序的set聚集，在 Set 的根本上增加了一个权重参数 score，使得聚会合的元素可以或许按 score 进行有序排列。在 Redis 中，有序聚集的最大成员数是 2^32 - 1。ZSet具备下列特性：
在 Zset 中，聚集元素的添加、删除和查找的时间复杂度都是 O(logn)，这得益于 Redis 利用跳表SkipList来实现 Zset。
由于ZSet的可排序特性，经常被用来实现排行榜这样的功能。

1.2 应用场景

以上只是 ZSet 的一些常见应用场景，实际上Zset 的应用非常广泛，只要是需要排序和排名功能的场景，都可以思量利用 ZSet。
1.3 底层结构

ZSet与Java中的TreeSet有些类似，但底层数据结构却差别很大。ZSet中的每一个元素都带有一个score属性，可以基于score属性对元素排序。底层实现有两种方式：当元素较少或总体元素占用空间较少时，利用压缩列表ZipList来实现；当不符合利用压缩列表的条件时，利用跳表SkipList+ 字典hashtable来实现。留意，聚集成员是唯一的，但是评分可以重复。



补充：ziplist自己没有排序功能，而且没有键值对的概念，因此需要有zset通过编码实现：

留意事项：
1.4 ZSet常用命令

ZSet的常见命令有：
留意：全部的排名默认都是升序，假如要降序则在命令的Z后面添加REV即可，比方：
  1. 127.0.0.1:6379>  zadd zset1 1 first 2 second 3 third 4 four  #往zset添中加一个或多个元素
  2. (integer) 4
  3. 127.0.0.1:6379> zrange zset1 0 -1                    #返回有序集合中、下标在<start> <end>之间的元素(有 WITHSCORES 会显示评分)。0 -1 表示所有元素
  4. 1) "first"
  5. 2) "second"
  6. 3) "third"
  7. 4) "four"
  8. 127.0.0.1:6379> zrevrange zset1 0 -1
  9. 1) "four"
  10. 2) "third"
  11. 3) "second"
  12. 4) "first"
  13. 127.0.0.1:6379> zscore zset1 third                #获取zset中的third元素的score值
  14. "3"
  15. 127.0.0.1:6379> zrank zset1 third                 #返回third在集合中的排名，从0开始
  16. (integer) 2
  17. 127.0.0.1:6379> zrevrank zset1 third
  18. (integer) 1
  19. 127.0.0.1:6379> zrangebyscore zset1 -inf +inf     #给zset集合中的元素从小到大排序，-inf：负无穷，+inf：正无穷。返回score值介于-inf到+inf之间（含两端）的成员（score从小到大）
  20. 1) "first"
  21. 2) "second"
  22. 3) "third"
  23. 4) "four"
  24. 127.0.0.1:6379> zrangebyscore zset1 -inf +inf withscores    #从小到大排序并输出键值
  25. 1) "first"
  26. 2) "1"
  27. 3) "second"
  28. 4) "2"
  29. 5) "third"
  30. 6) "3"
  31. 7) "four"
  32. 8) "4"
  33. 127.0.0.1:6379> zrangebyscore zset1 -inf 1 withscores      #指定负无穷到1的范围
  34. 1) "first"
  35. 2) "1"
  36. 127.0.0.1:6379> zrem zset1 four                            #移除zset集合中指定的元素
  37. (integer) 1
  38. 127.0.0.1:6379> zcard zset1                                #查看zset集合中元素个数
  39. (integer) 3
  40. 127.0.0.1:6379> zrangebyscore zset1 1 2 withscores         #根据score值从小到大排列
  41. 1) "first"
  42. 2) "1"
  43. 3) "second"
  44. 4) "2"
  45. 127.0.0.1:6379> zrevrangebyscore zset1 2 1 withscores      #根据score值从大到小排列
  46. 1) "second"
  47. 2) "2"
  48. 3) "first"
  49. 4) "1"
  50. 127.0.0.1:6379> zcount zset1 1 2                           #统计score值在1到2之间的元素个数
  51. (integer) 2
复制代码

二、ZSet底层结构详解

2.1 数据结构

有序聚集Zset底层实现会根据实际情况选择利用压缩列表（ziplist）或者跳跃表（skiplist）：当元素较少或总体元素占用空间较少时，利用压缩列表ZipList来实现；当不符合利用压缩列表的条件时，利用跳表SkipList+ 字典hashtable来实现。
详细细节可参考本文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），表现压缩列表的结束

留意：
2.3 跳表详解

学习一个新知识，从三方面分析：WHAT、WHY、HOW
2.3.1 跳表是什么（what）

**SkipList（跳表）**首先是链表，在有序链表的根本上，增加了多级索引，通过多级索引位置的转跳，实现了快速查找元素。但与传统链表相比有几点差异：

在 Redis 源码中，跳跃表的结构界说如下：
  1. typedef struct zskiplistNode {
  2.     robj *obj;
  3.     double score;
  4.     struct zskiplistNode *backward;
  5.     struct zskiplistLevel {
  6.         struct zskiplistNode *forward;
  7.         unsigned int span;
  8.     } level[];
  9. } zskiplistNode;
  11. typedef struct zskiplist {
  12.     struct zskiplistNode *header, *tail;
  13.     unsigned long length;
  14.     int level;
  15. } zskiplist;
复制代码
跳表查找、插入和删除操纵的时间复杂度都是 O(logN)。


SkipList的特点：
对于一个单链表来说，纵然链表中的数据是有序的，假如我们想要查找某个数据，也必须从头到尾的遍历链表，很显然这种查找效率是十分低效的，时间复杂度为O(n)。
普通链表想查找元素27，只能从链表头部一个个往后遍历，需要遍历6次 才能找到元素27

2.3.2 跳表怎么做的（how）

跳表怎么做的（how）：建立多级索引
如建立一级索引

假如以为慢，可以建立二级索引

当数据量特别大的时间，跳表的时间复杂度为 O(logN)。其自己利用的思想，有点类似于二分法。
2.3.3 为什么需要跳表（WHY）/跳表高效的动态插入和删除

由于普通链表查找一个元素 时间复杂度O(n)；而跳表查找的时间复杂度为O(logn)，查找速度更快。不仅云云，删除、插入等操纵的时间复杂度也是O(logn)
2.3.4 ZSet中的跳表

SkipList作为ZSet的存储结构，整体存储结构如下图，焦点点重要是包括一个dict对象和一个skiplist对象。dict生存key、value，key为元素，value为分值；skiplist生存的有序的元素列表，每个元素包括元素和分值。

上图中 zskiplist 结构包含以部属性：
位于 zskiplist 结构右侧是四个 zskiplistNode 结构，该结构包含以部属性：
2.4 什么时间采用压缩列表、什么时间采用跳表

什么时间采用压缩列表、什么时间采用跳表呢
上述 1且2的时间，采用压缩列表；否则采用跳表
三、Redis跳表与MySQL B+树

3.1 对比

Redis跳表：


B+Tree：

MySQL B+树：

相比于尺度的B+树，InnoDB利用的B+树有如下特点：
区别：
MySQL 的 B+ 树、Redis 的跳表都是用于存储有序数据的数据结构，但它们有一些关键的区别，使得它们在不同的场景和用途中各有优势。
因此，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+树，而用跳表
总的来说，Redis选择跳表作为有序聚集数据结构的底层实现，是基于跳表自己的优点：时间复杂度优势、简朴高效、空间利用率高和并发性能好。这使得Redis在处理有序聚集的操纵时可以或许获得较好的性能和并发能力。Redis是内存数据库、不存在IO的瓶颈，而B+树纯粹是为了MySQL这种IO数据库预备的。B+树的每个节点的数目都是一个MySQL分区页的大小。
2）ZSet为什么不消红黑树、二叉树
红黑树、二叉树查找一个元素的时间复杂度也是O(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]除了数据，还多了指针，但是每个节点的指针小于



欢迎光临 IT评测·应用市场-qidao123.com技术社区 (https://dis.qidao123.com/) Powered by Discuz! X3.4