Redis入门到通关之数据结构解析-QuickList

本文涉及的产品
云数据库 Redis 版,社区版 2GB
推荐场景:
搭建游戏排行榜
简介: Redis入门到通关之数据结构解析-QuickList


Redis
中的 QuickList 是一种特殊的数据结构,用于存储列表类型的数据。它的设计目的是在内存中高效地存储和操作大量的列表元素,尤其是当列表长度很大时。

QuickList的内部结构是一个由多个节点组成的双向链表,每个节点包含一个小的连续内存块,这些内存块被称为ziplist(压缩列表)。每个ziplist中存储了一个不定长度的元素序列,这些元素可以是字符串或整数。QuickList的每个节点都维护了指向上一个节点和下一个节点的指针,这样整个QuickList就形成了一个链表。


☃️前提概要


问题1:ZipList虽然节省内存,但申请内存必须是连续空间,如果内存占用较多,申请内存效率很低。怎么办?

答:为了缓解这个问题,我们必须限制ZipList的长度和entry大小。

问题2:但是我们要存储大量数据,超出了ZipList最佳的上限该怎么办?

答:我们可以创建多个ZipList来分片存储数据。

问题3:数据拆分后比较分散,不方便管理和查找,这多个ZipList如何建立联系?

答:Redis在3.2版本引入了新的数据结构QuickList,它是一个双端链表,只不过链表中的每个节点都是一个ZipList。


☃️ 配置项相关


为了避免QuickList中的每个ZipList中entry过多,Redis提供了一个配置项:list-max-ziplist-size来限制。

如果值为正,则代表ZipList的允许的entry个数的最大值

如果值为负,则代表ZipList的最大内存大小,分5种情况:

  • -1:每个ZipList的内存占用不能超过4kb
  • -2:每个ZipList的内存占用不能超过8kb
  • -3:每个ZipList的内存占用不能超过16kb
  • -4:每个ZipList的内存占用不能超过32kb
  • -5:每个ZipList的内存占用不能超过64kb

其默认值为 -2:


☃️简要源码


以下是QuickList的和QuickListNode的结构源码:

我们接下来用一段流程图来描述当前的这个结构


☃️总结


QuickList的一些特点和优势:

分段存储: QuickList将列表分成多个节点,每个节点都包含一定数量的元素,这样可以降低内存碎片化的程度,提高内存利用率。

支持快速尾部插入和删除操作: 由于QuickList是一个双向链表,因此在列表的两端进行插入和删除操作的性能都很高,时间复杂度为O(1)。

压缩列表优化: QuickList中使用的ziplist是一种紧凑的数据结构,它可以在一定程度上减少内存的消耗。另外,ziplist还支持一些特殊的操作,比如在固定时间内查找元素、在固定时间内插入元素等。

灵活性: QuickList可以根据需要动态地调整节点的大小,从而适应不同大小的列表。这种灵活性可以帮助Redis在不同的工作负载下提供更好的性能。

总的来说,QuickList是Redis中用于存储列表类型数据的一种高效数据结构,它结合了双向链表和压缩列表的优点,在内存占用和性能方面都具有很好的表现。

QuickList的特点:

  • 是一个节点为ZipList的双端链表
  • 节点采用ZipList,解决了传统链表的内存占用问题
  • 控制了ZipList大小,解决连续内存空间申请效率问题
  • 中间节点可以压缩,进一步节省了内存
相关实践学习
基于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
相关文章
|
7天前
|
存储 NoSQL Java
【面试宝藏】Redis 常见面试题解析
Redis 是内存数据结构存储系统,用作数据库、缓存和消息中间件,支持字符串、哈希、列表等数据类型。它的优点包括高性能、原子操作、持久化和复制。相比 Memcached,Redis 提供数据持久化、丰富数据结构和发布/订阅功能。Redis 采用单线程模型,但通过 I/O 多路复用处理高并发。常见的面试问题涉及持久化机制、过期键删除、回收策略、集群和客户端等。
34 4
|
2天前
|
JavaScript 安全 前端开发
【Node.js】从入门到精通(一)—— fs 模块全解析
【Node.js】从入门到精通(一)—— fs 模块全解析
6 0
|
6天前
|
存储 缓存 NoSQL
rodert单排学习redis入门【黑铁】2
rodert单排学习redis入门【黑铁】
11 0
|
6天前
|
存储 缓存 NoSQL
rodert单排学习redis入门【黑铁】1
rodert单排学习redis入门【黑铁】
12 0
|
7天前
|
存储 缓存 NoSQL
【面试宝藏】Redis 常见面试题解析其二
Redis 高级面试题涵盖了哈希槽机制、集群的主从复制、数据丢失可能性、复制机制、最大节点数、数据库选择、连通性测试、事务操作、过期时间和内存优化等。Redis 使用哈希槽实现数据分布,主从复制保障高可用,异步复制可能导致写操作丢失。集群最大支持1000个节点,仅允许单数据库。可通过 `ping` 命令测试连接,使用 `EXPIRE` 设置过期时间,`MULTI/EXEC` 等进行事务处理。内存优化包括合理数据类型、设置过期时间及淘汰策略。Redis 可用作缓存、会话存储、排行榜等场景,使用 `SCAN` 查找特定前缀键,列表实现异步队列,分布式锁则通过 `SET` 命令和 Lua 脚本实现。
21 5
|
8天前
|
机器学习/深度学习 算法
数据结构入门 时间 空间复杂度解析
数据结构入门 时间 空间复杂度解析
8 0
|
9天前
|
存储 算法 大数据
深入解析力扣170题:两数之和 III - 数据结构设计(哈希表与双指针法详解及模拟面试问答)
深入解析力扣170题:两数之和 III - 数据结构设计(哈希表与双指针法详解及模拟面试问答)
|
10天前
|
存储 数据挖掘 数据处理
【python源码解析】深入 Pandas BlockManager 的数据结构和初始化过程
【python源码解析】深入 Pandas BlockManager 的数据结构和初始化过程
|
10天前
|
存储 算法 数据挖掘
数据结构面试常见问题:解锁10大关键问题及答案解析【图解】
数据结构面试常见问题:解锁10大关键问题及答案解析【图解】
|
10天前
|
存储 监控 NoSQL
Redis中的LRU淘汰策略深入解析
Redis的内存管理关键在于处理数据增长与有限内存的矛盾,LRU策略被广泛用于此。LRU基于“不常访问的数据未来访问可能性小”的假设,淘汰最近最少使用的数据。Redis通过双向链表实现,但并非严格LRU,而是采样算法以平衡性能和精度。用户可通过调整`maxmemory-samples`等参数优化。尽管LRU简单高效,但无法区分数据重要性和访问频率,可能误淘汰重要数据。合理设置参数、结合其他策略、监控调优是优化LRU使用的关键。
13 1

推荐镜像

更多