专栏首页服务端思维Redis中hash、set、zset的底层数据结构原理

Redis中hash、set、zset的底层数据结构原理

Redis-哈希对象(hash)

hash的底层存储有两种数据结构,一种是ziplist,另外一种是hashtable,这两种数据结构我们之前都有讲解,ziplist就是上文提到的结构,hashtable之前讲解的redis结构,hash对象只有同时满足以下条件,才会采用ziplist编码:

  • hash对象保存的键和值字符串长度都小于64字节
  • hash对象保存的键值对数量小于512 ziplist存储的结构如下

上图中可以看到,当数据量比较小的时候,我们会将所有的key及value都当成一个元素,顺序的存入到ziplist中,构成有序。

hashtable存储的结构

字符串的set key value 和 hash 的区别是什么

  1. 过期时间,hash没有过期时间
  2. set不断的加值有一个问题,dict中有一个属性是dictht ht[2],主要是> 扩容用的,如果不断的加key,则整体redis内存就需要扩容,扩容就需要基于原有内存增加一倍,内存消耗很大

Redis-集合对象(set)

set是一个无序的、自动去重的集合数据类型,Set底层用两种数据结构存储,一个是hashtable,一个是inset。

其中hashtable的key为set中元素的值,而value为null

inset为可以理解为数组,使用inset数据结构需要满足下述两个条件:

  • 元素个数不少于默认值512
  set-max-inset-entries 512
  • 元素可以用整型表示

intset的底层结构

typedef struct intset {
    
    // 编码类型
    uint32_t encoding;

    // 集合包含的元素数量
    uint32_t length;

    // 保存元素的数组
    int8_t contents[];

} intset;

查询方式一般采用二分查找法,实际查询复杂度也就在log(n)

Redis-有序集合对象(zset)

zset为有序(有限score排序,score相同则元素字典序),自动去重的集合数据类型,其底层实现为 字典(dict) + 跳表(skiplist),当数据比较少的时候用ziplist编码结构存储。

同时满足以下两个条件采用ziplist存储:

  • 有序集合保存的元素数量小于默认值128个
  • 有序集合保存的所有元素的长度小于默认值64字节

ziplist存储方式

当ziplist作为zset的底层存储结构时候,每个集合元素使用两个紧挨在一起的压缩列表节点来保存,第一个节点保存元素的成员,第二个元素保存元素的分值

字典(dict) + 跳表(skiplist)的存储方式

zset底层的存储结构包括ziplist或skiplist,在同时满足以下两个条件的时候使用ziplist,其他时候使用skiplist,两个条件如下:

有序集合保存的元素数量小于128个 有序集合保存的所有元素的长度小于64字节

跳表的数据结构

首先我们理解一下什么是跳表同种可以看到我们通过分等级,从最高等级向低等级查询,效率提高,其时间复杂度为logn(类似于二分查找)

dict+skiplist的最终的存储结构如下

基于上图我们看一下skiplist几个关键对象的数据结构,方便大家理解

zset

  /*
 * 有序集合
 */
typedef struct zset {

    // 字典,键为成员,值为分值
    // 用于支持 O(1) 复杂度的按成员取分值操作
    dict *dict;

    // 跳跃表,按分值排序成员
    // 用于支持平均复杂度为 O(log N) 的按分值定位成员操作
    // 以及范围操作
    zskiplist *zsl;

} zset;

可以看到一个是dict结构,主要key是其集合元素,而value就是对应分值,而zkiplist作为跳跃表,按照分值排序,方便定位成员

zskiplist

 * 跳跃表
 */
typedef struct zskiplist {

    // 表头节点和表尾节点
    struct zskiplistNode *header, *tail;

    // 表中节点的数量
    unsigned long length;

    // 表中层数最大的节点的层数
    int level;

} zskiplist;

zskiplistNode

  /*
 * 跳跃表节点
 */
typedef struct zskiplistNode {

    // 成员对象
    robj *obj;

    // 分值
    double score;

    // 后退指针
    struct zskiplistNode *backward;

    // 层
    struct zskiplistLevel {

        // 前进指针
        struct zskiplistNode *forward;

        // 跨度
        unsigned int span;

    } level[];

} zskiplistNode;

zskiplistNode中的robj指针指向具体元素,注意这个指针和dict中key指针指向同一个元素,其中backward后腿指针便于回溯

总结

本节内容主要讲解了Redis中hash、set、zset的底层原理,其中hash底层采用两种,分别是ziplist和hashtable,set底层也分别采用两种hashtable和inset,其中inset也可以理解为数组,zset底层分别是ziplist和dict+skiplist,我们可以看到在节省内存、提高查询效率方面都体现了优秀的设计,这些都可以作为我们日后设计及开发中的宝贵经验,下一节我们将带领大家学习Redis在数据安全及性能保障方面的特点,下课!

本文分享自微信公众号 - 服务端思维(gh_c3775931ac9d)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-10-02

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 系统CPU飙高和频繁GC,你会怎么排查?

    处理过线上问题的同学基本上都会遇到系统突然运行缓慢,CPU 100%,以及Full GC次数过多的问题。当然,这些问题的最终导致的直观现象就是系统运行缓慢,并且...

    用户2781897
  • 深入探讨 MySQL 的 order by 优化

    为什么是再说呢?因为前面已经写过 《order by 原理以及优化》 ,介绍 order by 的基本原理以及优化。如果觉得对 order by 原理了解不透彻...

    用户2781897
  • Apache Dubbo 反序列化漏洞通告及解决方案

    近日检测到Apache Dubbo官方发布了CVE-2019-17564漏洞通告,360灵腾安全实验室判断漏洞等级为高,利用难度低,威胁程度高,影响面大。建议使...

    用户2781897
  • 互联网公司数据安全保护新探索

    美团技术团队
  • 程序员必备数据结构:栈

    栈有很多用途,也分很多种类,顺序栈、双端栈、单调栈、链栈等。让哥哥带你,深入浅出堆栈系列。坐好上车咯。

    看、未来
  • hive表被误删后如何恢复?

    week
  • Spring周边:日志——下

    门面设计模式是面面向对象设计模式中的一种,日志框架采用的就是这种模式,类似JDBC的设计理念。它只提供一套接口规范,自身不负责日志功能的实现,目的是让使用者不需...

    WEBJ2EE
  • 12.18 ssl原理

    ssl原理 https的相关知识点 要配置nginx和https,就需要首先去了解https是什么? 在访问一些网站的时候,会自动加上了https前标 http...

    运维小白
  • react 和 redux 入门

    本文作者:IMWeb 王少飞 原文出处:IMWeb社区 未经同意,禁止转载 react的核心思想:组件封装。 页面的所有元素都是可以封装成组件 rea...

    IMWeb前端团队
  • 学界 | 把酱油瓶放进菜篮子:UC Berkeley提出高度逼真的物体组合网络Compositional GAN

    生成对抗网络(GAN)是在给定输入的条件下生成图像的一种强大方法。输入的格式可以是图像 [9,37,16,2,29,21]、文本短语 [33,24,23,11]...

    机器之心

扫码关注云+社区

领取腾讯云代金券