【Redis】细说Redis之zset底层数据结构

本文涉及的产品
Redis 开源版,标准版 2GB
推荐场景:
搭建游戏排行榜
云数据库 Tair(兼容Redis),内存型 2GB
简介: 面试官:有了解过Redis中zset数据结构底层是怎样实现的吗?没有是吧,没关系,那感谢参加今天的面试哈。

Redis相关文章


zset | socreset

Redis中的Set结构与Java中的HashSet如出一辙,可一看做一个value为null的HashTable,本质上也是通过Hash表实现去重。


ZSet或者叫SocreSet,是基于set数据结构基础之上增加score属性并按score排序的数据结构。因为可排序且元素不重复的特性通常用作排行榜等功能。


本质上是依赖两个核心数据结构,ziplist压缩链表skiplist跳跃链表实现。


ziplist

  • ziplist本质上是字节数组,每个元素可以是一个字节数组或一个整数。占用一块完整的内存,空间连续,避免内存碎片,节省内存
  • 对值存储采用变长形式,根据大小调整存储字节大小


  • 基础结构
  1. zlbytes:记录整个ziplist的大小。
  2. zltail:ziplist开始指针与最后一个entry之间的偏移量,通过该偏移量可以获得最后一个entry。
  3. zllen:entry数量。
  4. entry:存储具体数据的节点。
  • prelen:上一个entry的大小。
  • encoding:记录content的类型以及长度。
  • content:一个整形或者字节数组。
  1. zlend:ziplist结尾标识。


image.png

  • 总结
  • 本质为占用一段完整内存字节数组,空间连续避免内存碎片
  • 每个节点通过保存特殊节点位置实现双向链表特性
  • 新增元素可能会引起连锁更新(类似数组,引发后续下标变动)



skiplist

  • 本质上由Node节点构造成的多层链表结构,每层都是有序链表,最底层包含所有元素,上下层元素比例约为1:2
  1. 通过空间换时间的思想,在原有的有序链表中增加多级索引,每个元素包含多指针,指针个数通过"丢硬币"的方式实现基本满足二分概率1/2,每丢一次指针个数+1,指向下一层的元素,直到扔到反面为止
  2. 新增删除操作需要把后面的节点都更新一遍
  3. redis为什么使用跳表而不是用红黑树
  1. 内存占用更少,自定义参数化决定使用多少内存
  2. 查询性能至少不比红黑树差
  3. 简单更容易实现和维护

image.png


总结

  1. 基于ziplist或skiplist
  2. 符合以下条件使用ziplist
  1. 服务器属性server.zset_max_ziplist_entries 的值大于 0
  2. 元素的member长度(成员长度)小于服务器属性server.zset_max_ziplist_value的值(默认64)
  1. 不符合使用skiplist


相关实践学习
基于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 数据结构与对象
【10月更文挑战第15天】在实际应用中,需要根据具体的业务需求和数据特点来选择合适的数据结构,并合理地设计数据模型,以充分发挥 Redis 的优势。
37 8
|
4天前
|
存储 NoSQL Java
介绍下Redis 的基础数据结构
本文介绍了Redis的基础数据结构,包括动态字符串(SDS)、链表和字典。SDS是Redis自实现的动态字符串,避免了C语言字符串的不足;链表实现了双向链表,提供了高效的操作;字典则类似于Java的HashMap,采用数组加链表的方式存储数据,并支持渐进式rehash,确保高并发下的性能。
介绍下Redis 的基础数据结构
|
20天前
|
消息中间件 存储 缓存
redis支持的数据结构
redis支持的数据结构
28 2
|
存储 NoSQL 算法
Redis之zset实现滑动窗口限流
Redis之zset实现滑动窗口限流
1982 0
Redis之zset实现滑动窗口限流
|
24天前
|
存储 缓存 NoSQL
数据的存储--Redis缓存存储(一)
数据的存储--Redis缓存存储(一)
58 1
|
24天前
|
存储 缓存 NoSQL
数据的存储--Redis缓存存储(二)
数据的存储--Redis缓存存储(二)
37 2
数据的存储--Redis缓存存储(二)
|
20天前
|
消息中间件 缓存 NoSQL
Redis 是一个高性能的键值对存储系统,常用于缓存、消息队列和会话管理等场景。
【10月更文挑战第4天】Redis 是一个高性能的键值对存储系统,常用于缓存、消息队列和会话管理等场景。随着数据增长,有时需要将 Redis 数据导出以进行分析、备份或迁移。本文详细介绍几种导出方法:1)使用 Redis 命令与重定向;2)利用 Redis 的 RDB 和 AOF 持久化功能;3)借助第三方工具如 `redis-dump`。每种方法均附有示例代码,帮助你轻松完成数据导出任务。无论数据量大小,总有一款适合你。
55 6
|
25天前
|
缓存 NoSQL 关系型数据库
redis和缓存及相关问题和解决办法 什么是缓存预热、缓存穿透、缓存雪崩、缓存击穿
本文深入探讨了Redis缓存的相关知识,包括缓存的概念、使用场景、可能出现的问题(缓存预热、缓存穿透、缓存雪崩、缓存击穿)及其解决方案。
122 0
redis和缓存及相关问题和解决办法 什么是缓存预热、缓存穿透、缓存雪崩、缓存击穿
|
1天前
|
缓存 监控 NoSQL
Redis 缓存穿透的检测方法与分析
【10月更文挑战第23天】通过以上对 Redis 缓存穿透检测方法的深入探讨,我们对如何及时发现和处理这一问题有了更全面的认识。在实际应用中,我们需要综合运用多种检测手段,并结合业务场景和实际情况进行分析,以确保能够准确、及时地检测到缓存穿透现象,并采取有效的措施加以解决。同时,要不断优化和改进检测方法,提高检测的准确性和效率,为系统的稳定运行提供有力保障。
19 5
|
1天前
|
存储 缓存 监控
利用 Redis 缓存特性避免缓存穿透的策略与方法
【10月更文挑战第23天】通过以上对利用 Redis 缓存特性避免缓存穿透的详细阐述,我们对这一策略有了更深入的理解。在实际应用中,我们需要根据具体情况灵活运用这些方法,并结合其他技术手段,共同保障系统的稳定和高效运行。同时,要不断关注 Redis 缓存特性的发展和变化,及时调整策略,以应对不断出现的新挑战。
19 10