Redis zset 底层数据结构之跳表

本文涉及的产品
Redis 开源版,标准版 2GB
推荐场景:
搭建游戏排行榜
云数据库 Tair(兼容Redis),内存型 2GB
简介: 0、zset数据结构1、zset底层的数据结构2、跳表介绍3、跳表增删查的时间复杂度4、什么时候使用压缩链表,什么时候使用跳表5、跳表的内部实现及原理6、为什么用跳表而不用红黑树或二叉树呢.........

参考:

0、zset数据结构

  • 【有序集合】
  • 【本质上是集合,所有元素不能重复】
  • 【分数可以重复(相同时根据member字典排序),member不能重复】
  • 【支持根据score的范围查找】

1、zset底层的数据结构是什么?

 zset底层包含 跳表压缩列表

2、跳表是什么?

 跳表(skiplist)是在链表的基础上,增加了多级索引,通过多级索引位置的跳转,实现了快速查找元素。

 跳表这一有序集合,底层是一个名为zset的结构体。而一个zset结构同时包含一个字典和一个跳跃表。跳跃表按score从小到大保存所有集合元素。而字典则保存着从member到score的映射,这样就可以用O(1)的复杂度来查找member对应的score值。虽然同时使用两种结构,但它们会通过指针来共享相同元素的member和score,因此不会浪费额外的内存。

3、跳表的时间复杂度:

 利用空间换时间,查找、新增、删除的时间复杂度都为:O(logN),类似于二分查找。

4、什么时候使用压缩列表,什么时候使用跳表呢?

  • 元素数量小于128
  • 所有member的长度都小于64字节

5、跳表的内部实现及原理:

在这里插入图片描述

  1. 当链表足够长的时候,这种多层链表的查找方式能让我们跳过很多下层节点,大大加快查找的速度。
  2. 跳表为了避免链表在新增/删除时,时间复杂度较低为O(n)的问题,它不要求链表相邻节点的上下层数之间有严格的对应关系,而是为每个节点随机出一个层数(level)
  3. 从跳表的创建和插入过程可以看出,每一个节点的层数(level)是随机出来的,而且新插入一个节点不会影响其它节点的层数。因此,插入操作只需要修改插入节点前后的指针,而不需要对很多节点都进行调整,这就降低了插入操作的复杂度。实际上,这是跳表的一个很重要的特性
  4. 跳表其实除了最下面第1层链表之外,它会产生若干层稀疏的链表,这些链表里面的指针故意跳过了一些节点(而且越高层的链表跳过的节点越多)。这使得我们在查找数据时能先在高层链表中查找,然后逐层降低,最终降到第1层链表来精确查找数据位置。在这个过程中,我们跳过了一些节点,从而也就加快了查找速度
  5. 实际应用中的跳表每个节点应该包含member和value两部分。实际上列表中是按照member对应的score值从小到大进行排序的(score值相同时按member字典序排列),查找过程也是根据member来比较。
  6. MaxLevel = 32,默认最大层数
  7. 实际上,Redis中sorted set的实现是这样的:
  • 当数据较少时:zset是由一个压缩列表来实现的
  • 当数据较多时:zset是由一个 字典 + 跳表 来实现的。简单来讲,dict用来查询数据到分数的对应关系,而skiplist用来根据分数查询数据(可能是范围查找)
  1. 第1层链表不是一个单向链表,而是一个双向链表,这是为了方便以倒序方式获取一个范围内的元素

6、为什么用跳表而不用红黑树或二叉树呢?

  1. 范围查找时,跳表效率比红黑树高。跳表可以通过查找区间的起点,然后依次往后遍历即可~
  2. 跳表的实现比红黑树简单(红黑树在新增/删除时,可能会面临反转等操作),更易理解与实现,且可以通过控制跳表的索引层级来控制内存的消耗。
相关实践学习
基于Redis实现在线游戏积分排行榜
本场景将介绍如何基于Redis数据库实现在线游戏中的游戏玩家积分排行榜功能。
云数据库 Redis 版使用教程
云数据库Redis版是兼容Redis协议标准的、提供持久化的内存数据库服务,基于高可靠双机热备架构及可无缝扩展的集群架构,满足高读写性能场景及容量需弹性变配的业务需求。 产品详情:https://www.aliyun.com/product/kvstore     ------------------------------------------------------------------------- 阿里云数据库体验:数据库上云实战 开发者云会免费提供一台带自建MySQL的源数据库 ECS 实例和一台目标数据库 RDS实例。跟着指引,您可以一步步实现将ECS自建数据库迁移到目标数据库RDS。 点击下方链接,领取免费ECS&RDS资源,30分钟完成数据库上云实战!https://developer.aliyun.com/adc/scenario/51eefbd1894e42f6bb9acacadd3f9121?spm=a2c6h.13788135.J_3257954370.9.4ba85f24utseFl
目录
相关文章
|
5天前
|
存储 消息中间件 NoSQL
Redis数据结构:List类型全面解析
Redis数据结构——List类型全面解析:存储多个有序的字符串,列表中每个字符串成为元素 Eelement,最多可以存储 2^32-1 个元素。可对列表两端插入(push)和弹出(pop)、获取指定范围的元素列表等,常见命令。 底层数据结构:3.2版本之前,底层采用**压缩链表ZipList**和**双向链表LinkedList**;3.2版本之后,底层数据结构为**快速链表QuickList** 列表是一种比较灵活的数据结构,可以充当栈、队列、阻塞队列,在实际开发中有很多应用场景。
|
5天前
|
存储 NoSQL 关系型数据库
Redis的ZSet底层数据结构,ZSet类型全面解析
Redis的ZSet底层数据结构,ZSet类型全面解析;应用场景、底层结构、常用命令;压缩列表ZipList、跳表SkipList;B+树与跳表对比,MySQL为什么使用B+树;ZSet为什么用跳表,而不是B+树、红黑树、二叉树
|
5天前
|
存储 NoSQL Redis
Redis常见面试题:ZSet底层数据结构,SDS、压缩列表ZipList、跳表SkipList
String类型底层数据结构,List类型全面解析,ZSet底层数据结构;简单动态字符串SDS、压缩列表ZipList、哈希表、跳表SkipList、整数数组IntSet
|
29天前
|
存储 缓存 NoSQL
数据的存储--Redis缓存存储(一)
数据的存储--Redis缓存存储(一)
65 1
|
29天前
|
存储 缓存 NoSQL
数据的存储--Redis缓存存储(二)
数据的存储--Redis缓存存储(二)
40 2
数据的存储--Redis缓存存储(二)
|
25天前
|
消息中间件 缓存 NoSQL
Redis 是一个高性能的键值对存储系统,常用于缓存、消息队列和会话管理等场景。
【10月更文挑战第4天】Redis 是一个高性能的键值对存储系统,常用于缓存、消息队列和会话管理等场景。随着数据增长,有时需要将 Redis 数据导出以进行分析、备份或迁移。本文详细介绍几种导出方法:1)使用 Redis 命令与重定向;2)利用 Redis 的 RDB 和 AOF 持久化功能;3)借助第三方工具如 `redis-dump`。每种方法均附有示例代码,帮助你轻松完成数据导出任务。无论数据量大小,总有一款适合你。
57 6
|
30天前
|
缓存 NoSQL 关系型数据库
redis和缓存及相关问题和解决办法 什么是缓存预热、缓存穿透、缓存雪崩、缓存击穿
本文深入探讨了Redis缓存的相关知识,包括缓存的概念、使用场景、可能出现的问题(缓存预热、缓存穿透、缓存雪崩、缓存击穿)及其解决方案。
138 0
redis和缓存及相关问题和解决办法 什么是缓存预热、缓存穿透、缓存雪崩、缓存击穿
|
2天前
|
缓存 NoSQL Redis
Redis 缓存使用的实践
《Redis缓存最佳实践指南》涵盖缓存更新策略、缓存击穿防护、大key处理和性能优化。包括Cache Aside Pattern、Write Through、分布式锁、大key拆分和批量操作等技术,帮助你在项目中高效使用Redis缓存。
45 22
|
1天前
|
缓存 NoSQL 中间件
redis高并发缓存中间件总结!
本文档详细介绍了高并发缓存中间件Redis的原理、高级操作及其在电商架构中的应用。通过阿里云的角度,分析了Redis与架构的关系,并展示了无Redis和使用Redis缓存的架构图。文档还涵盖了Redis的基本特性、应用场景、安装部署步骤、配置文件详解、启动和关闭方法、systemctl管理脚本的生成以及日志警告处理等内容。适合初学者和有一定经验的技术人员参考学习。
31 7
|
5天前
|
存储 缓存 监控
利用 Redis 缓存特性避免缓存穿透的策略与方法
【10月更文挑战第23天】通过以上对利用 Redis 缓存特性避免缓存穿透的详细阐述,我们对这一策略有了更深入的理解。在实际应用中,我们需要根据具体情况灵活运用这些方法,并结合其他技术手段,共同保障系统的稳定和高效运行。同时,要不断关注 Redis 缓存特性的发展和变化,及时调整策略,以应对不断出现的新挑战。
27 10