【Redis系列】那有序集合为什么要同时使用字典和跳跃表

本文涉及的产品
云原生内存数据库 Tair,内存型 2GB
云数据库 Redis 版,社区版 2GB
推荐场景:
搭建游戏排行榜
云数据库 Redis 版,经济版 1GB 1个月
简介: 面试官问:那有序集合为什么要同时使用字典和跳跃表来实现?我:这个设计主要是考虑了性能因素。1. 如果单纯使用字典,查询的效率很高是O(1),但执行类似ZRANGE、ZRNK时,排序性能低。每次排序需要在内存上对字典进行排序一次,同时消耗了额外的O(n)内存空间

在这里插入图片描述

面试官:听说你精通Redis,那我就考考你吧


面试官:不用慌尽管说,错了也没关系😊。。。


以【面试官面试】的形式来分享技术,本期是《Redis系列》,感兴趣就关注我吧❤️

面试官:你说说Redis有什么底层数据结构支持

好的,我了解的主要有:

  1. 字典
  2. 跳跃表
  3. 链表,Redis采用了有前置后置节点的双端链表列表键List就是采用这种结构。


面试官思考中…


面试官:先讲讲你对字典的理解

好的,字典其实是一个集合里包含了多个键值对,类似于Java的HashMap

它的底层包含了两个哈希表,一个平常使用,一个在迁移扩展哈希表rehash时使用。

迁移完成后,原先日常使用的旧哈希表会被清空,新的哈希表变成日常使用的。


面试官思考中…


面试官:那字典和Redis的哈希对象不是没什么区别?

有区别的,面向对象不同。

字典是Redis内部的底层数据结构支持,而Redis的哈希对象是对外提供的一种对象。


面试官思考中…


面试官:跳跃表呢

它的底层结构类似于一个值 + 保存了指向其他节点的level数组(层),而这个level数组就是用来加快访问其他节点的速度。

typedef struct zskiplistNode {
   
   
    // level数组
    struct zskiplistLevel {
   
   
        //前进指针
        struct zskiplistNode *forward;
        //跨度
        unsigned int span;
    } level[];
    // 后退指针
    struct zskiplistNode *backward;
    // 分值
    double score;
    // 成员对象
    robj *obj;
} zskiplistNode;

在这里插入图片描述


面试官思考中…


面试官:那有序集合为什么要同时使用字典和跳跃表来实现

这个设计主要是考虑了性能因素。

  1. 如果单纯使用字典,查询时的效率很高是O(1),但执行类似ZRANGE、ZRNK时,排序性能低。每次排序需要在内存上对字典进行排序一次,同时消耗了额外的O(n)内存空间
  2. 如果单纯使用跳跃表,查询性能又会从O(1)上升到了O(logN)

所以Redis集合了两种数据结构,同时这两种数据结构通过指针来共享变量也不会浪费内存。

typedef struct zset {
   
    // 有序集合
    zskiplist *zsl; // 跳跃表
    dict *dict; // 字典
} zset;


面试官思考中…


面试官:Redis为了节约内存采用了什么数据结构知道吗

噢噢知道的。我了解的有两种。

  1. 列表键只有少数几个且都是整数型的话,Redis会改用整数集合进行存储。
  2. 当列表键只有少数几个,且都是整数型或长度短的字符型的话,Redis会改用压缩列表进行存储。
# 可以看到创建了列表键类型,但实际存储类型是ziplist

redis> RPUSH lst 1 3 5 10086 "hello" "world"
(integer)6
redis> OBJECT ENCODING lst
"ziplist"

面试官抓抓脑袋,继续看你的简历......


得想想考点你不懂的😰

未完待续。。。。。。

好了,今天的分享就先到这,我们下期【Redis系列】继续。

创作不易,不妨点赞、收藏、关注支持一下,各位的支持就是我创作的最大动力❤️

相关实践学习
基于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
相关文章
|
8月前
|
存储 NoSQL API
【Redis 系列】redis 学习四,set 集合,hash 哈希,zset 有序集合初步认知
【Redis 系列】redis 学习四,set 集合,hash 哈希,zset 有序集合初步认知
|
9月前
|
缓存 NoSQL 数据建模
【Redis源码】dict字典学习(三)
【Redis源码】dict字典学习(三)
63 0
|
2月前
|
存储 缓存 NoSQL
【Redis技术进阶之路】「底层源码解析」揭秘高效存储模型与数据结构底层实现(字典)(一)
【Redis技术进阶之路】「底层源码解析」揭秘高效存储模型与数据结构底层实现(字典)
67 0
|
8月前
|
缓存 NoSQL Redis
【Redis 系列】redis 学习十六,redis 字典(map) 及其核心编码结构
【Redis 系列】redis 学习十六,redis 字典(map) 及其核心编码结构
|
19小时前
|
NoSQL Redis
Redis 中的跳跃表是什么?
Redis 中的跳跃表(Skiplist)是一种可以替代平衡树的数据结构,它主要用于实现有序集合(Sorted Set)功能。跳跃表通过在多个层级的链表上增加索引来提高查询效率,其效率可以与平衡树相媲美,但实现起来更简单。
10 1
|
2月前
|
存储 NoSQL 算法
【Redis技术进阶之路】「底层源码解析」揭秘高效存储模型与数据结构底层实现(字典)(二)
【Redis技术进阶之路】「底层源码解析」揭秘高效存储模型与数据结构底层实现(字典)
87 0
|
6天前
|
消息中间件 存储 NoSQL
Redis数据结构—跳跃表 skiplist 实现源码分析
Redis 是一个内存中的数据结构服务器,使用跳跃表(skiplist)来实现有序集合。跳跃表是一种概率型数据结构,支持平均 O(logN) 查找复杂度,它通过多层链表加速查找,同时保持有序性。节点高度随机生成,最大为 32 层,以平衡查找速度和空间效率。跳跃表在 Redis 中用于插入、删除和按范围查询元素,其内部节点包含对象、分值、后退指针和多个前向指针。Redis 源码中的 `t_zset.c` 文件包含了跳跃表的具体实现细节。
|
8天前
|
存储 NoSQL Redis
Redis数据结构—跳跃表 skiplist
Redis数据结构—跳跃表 skiplist
|
14天前
|
存储 Java
Redis08命令-Hash类型,也叫散列,其中value是一个无序字典,类似于java的HashMap结构,Hash结构可以将对象中的每个字段独立存储,可以针对每字段做CRUD
Redis08命令-Hash类型,也叫散列,其中value是一个无序字典,类似于java的HashMap结构,Hash结构可以将对象中的每个字段独立存储,可以针对每字段做CRUD
|
1月前
|
NoSQL Java Redis
【Redis】 Java操作客户端命令——集合操作与有序集合操作
【Redis】 Java操作客户端命令——集合操作与有序集合操作