深入浅出Redis-redis底层数据结构(下)

概述:

学习使用Redis,其实并不需要去研究其底层数据的实现。我们只需要了解他有哪些常用的数据类型,然后熟练使用,就可以很好的掌握Redis 这个工具了。但是这样的学习方法只适合Redis 的入门,“工欲善其事必先利其器”,我们想要用好Redis,则必须深入了解Redis 的底层到底是如何实现的,我们在选择数据结构的时候才能做出正确的选择。

    在上一篇博客《深入浅出Redis-redis底层数据结构(上)》中,我们已经讲解了Redis 中的 动态字符串,链表,字典

    在这里我们简单回顾一下他们的特点:

      1、动态字符串SDS:区别于C语言字符串,具有良好的伸缩性,在获取字符串长度,字符串修改,防止缓存区溢出等性能都比C语言字符串好

      2、链表:顺序存储对象信息,有用于缓存链表长度的属性,在插入删除对象功能中有良好性能,避免环的产生

      3、字典:key-value 存储方式,通过hash值计算,判断key的存储,当容量过大,会通过rehash重新分配字典大小

 5、跳跃表


  5.1 概述

跳跃表(skiplist)是一种有序数据结构,它通过在每个节点中维持多个指向其他节点的指针,从而达到快速访问节点的目的。跳跃表是一种随机化的数据,跳跃表以有序的方式在层次化的链表中保存元素,效率和平衡树媲美 ——查找、删除、添加等操作都可以在对数期望时间下完成,并且比起平衡树来说,跳跃表的实现要简单直观得多。

    Redis 只在两个地方用到了跳跃表,一个是实现有序集合键,另外一个是在集群节点中用作内部数据结构

  5.2 跳跃表的定义

     我们先来看一下一整个跳跃表的完整结构:

     Redis 的跳跃表 主要由两部分组成:zskiplist(链表)和zskiplistNode (节点)

   5.2.1 zskiplistNode(节点) 数据结构:

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

    1、层:level 数组可以包含多个元素,每个元素都包含一个指向其他节点的指针。

    2、前进指针:用于指向表尾方向的前进指针

    3、跨度:用于记录两个节点之间的距离

    4、后退指针:用于从表尾向表头方向访问节点

    5、分值和成员:跳跃表中的所有节点都按分值从小到大排序。成员对象指向一个字符串,这个字符串对象保存着一个SDS值

   5.2. zskiplist 数据结构:

typedef struct zskiplist {
     //表头节点和表尾节点
     structz skiplistNode *header,*tail;
     //表中节点数量
     unsigned long length;
     //表中层数最大的节点的层数
     int level;

}zskiplist;

     从结构图中我们可以清晰的看到,header,tail分别指向跳跃表的头结点和尾节点。level 用于记录最大的层数,length 用于记录我们的节点数量。

  5.3 总结

  • 跳跃表是有序集合的底层实现之一
  •    主要有zskiplist 和zskiplistNode两个结构组成
  •    每个跳跃表节点的层高都是1至32之间的随机数
  •    在同一个跳跃表中,多个节点可以包含相同的分值,但每个节点的对象必须是唯一的
  •    节点按照分值的大小从大到小排序,如果分值相同,则按成员对象大小排序

 6、整数集合(Intset)


  6.1 概述

    《Redis 设计与实现》 中这样定义整数集合:“整数集合是集合建的底层实现之一,当一个集合中只包含整数,且这个集合中的元素数量不多时,redis就会使用整数集合intset作为集合的底层实现。”

     我们可以这样理解整数集合,他其实就是一个特殊的集合,里面存储的数据只能够是整数,并且数据量不能过大。

  6.2 整数集合的实现

typedef struct intset{
    //编码方式
    uint32_t enconding;
   // 集合包含的元素数量
    uint32_t length;
    //保存元素的数组    
    int8_t contents[];

}  

   我们观察一下一个完成的整数集合结构图:

    1、encoding:用于定义整数集合的编码方式

    2、length:用于记录整数集合中变量的数量

           3、contents:用于保存元素的数组,虽然我们在数据结构图中看到,intset将数组定义为int8_t,但实际上数组保存的元素类型取决于encoding

  6.3 整数集合的升级

    在上述数据结构图中我们可以看到,intset 在默认情况下会帮我们设定整数集合中的编码方式,但是当我们存入的整数不符合整数集合中的编码格式时,就需要使用到Redis 中的升级策略来解决

    Intset 中升级整数集合并添加新元素共分为三步进行:

      1、根据新元素的类型,扩展整数集合底层数组的空间大小,并为新元素分配空间

        2、将底层数组现有的所有元素都转换成新的编码格式,重新分配空间

      3、将新元素加入到底层数组中

   比如,我们现在有如下的整数集合:

    我们现在需要插入一个32位的整数,这显然与整数集合不符合,我们将进行编码格式的转换,并为新元素分配空间:

    第二步,将原有数据他们的数据类型转换为与新数据相同的类型:(重新分配空间后的数据)

    第三部,将新数据添加到数组中:

6.3.1 整数集合升级的好处

      1、提升灵活性

      2、节约内存

  6.4 总结

    整数集合是集合建的底层实现之一

    整数集合的底层实现为数组,这个数组以有序,无重复的范式保存集合元素,在有需要时,程序会根据新添加的元素类型改变这个数组的类型

    升级操作为整数集合带来了操作上的灵活性,并且尽可能地节约了内存

    整数集合只支持升级操作,不支持降级操作

7、压缩列表


  7.1 概述

    压缩列表是列表键和哈希键的底层实现之一。当一个列表键只把汗少量列表项,并且每个列表项要么就是小整数,要么就是长度比较短的字符串,那么Redis 就会使用压缩列表来做列表键的底层实现。

  7.2 压缩列表的构成

    一个压缩列表的组成如下:

    1、zlbytes:用于记录整个压缩列表占用的内存字节数

    2、zltail:记录要列表尾节点距离压缩列表的起始地址有多少字节

    3、zllen:记录了压缩列表包含的节点数量。

    4、entryX:要说列表包含的各个节点

    5、zlend:用于标记压缩列表的末端

  7.3 总结

    压缩列表是一种为了节约内存而开发的顺序型数据结构

    压缩列表被用作列表键和哈希键的底层实现之一

    压缩列表可以包含多个节点,每个节点可以保存一个字节数组或者整数值

    添加新节点到压缩列表,可能会引发连锁更新操作。

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏闪电gogogo的专栏

Python入门学习(一)

看完了莫烦Python的视频,对于Python有了一点感觉,接下来打算把小甲鱼的视频啃完,附上学习网址:http://blog.fishc.com/catego...

1878
来自专栏老马说编程

(92) 函数式数据处理 (上) / 计算机程序的思维逻辑

上节我们介绍了Lambda表达式和函数式接口,本节探讨它们的应用,函数式数据处理,针对常见的集合数据处理,Java 8引入了一套新的类库,位于包java.uti...

1706
来自专栏老九学堂

Java微课堂之数据类型转换

1 数据类型知识点微课笔记 碎片化的学习,注重积累,快乐学习。 Java的数据不同的数据类型的变量在编程过程中很多情况会遇到一些运算。我们知道,相同的数据类型进...

2143
来自专栏wOw的Android小站

[Objective-C] 常量和枚举

#define宏定义 #define是一条预编译指令, 编译器在编译阶段前期会将所有使用到宏的地方简单地进行替换.

332
来自专栏机器之心

资源 | 忘了Python关键语句?这份备忘录拯救你的记忆

Python 3 Cheat Sheet 一共包含两页,分成了多个框图,涉及基本的 Python 数据结构、数学运算、条件和循环语句、文件读写,以及异常值处理等...

903
来自专栏机器之心

资源 | 正则表达式的功法大全,做NLP再也不怕搞不定字符串了

正则表达式(regex 或 regexp)对于从文本中抽取信息极其有用,它一般会搜索匹配特定模式的语句,而这种模式及具体的 ASCII 序列或 Unicode ...

858
来自专栏轮子工厂

嘿~这里有一份超实用的 switch 教程,真的好想推荐给你

在上次推文中介绍了关系运算符和条件运算符,今天介绍它们的好搭档,分支结构。如下图所示,左侧是顺序结构,右侧是分支结构

501
来自专栏Golang语言社区

第四节 Go语言数据类型

干货来了!!!为了让更多的小伙伴喜欢Golang、加入Golang之中来,Golang语言社区发起人彬哥联合业界大牛共同推出了Go语言基础、进阶、提高课程,目前...

512
来自专栏极客慕白的成长之路

Python字符串格式化

格式化字符串时,Python使用一个字符串作为模板。模板中有格式符,这些格式符为真实值预留位置,并说明真实数值应该呈现的格式。Python用一个tuple将多个...

962
来自专栏老九学堂

这是谁做的作业!C语言编码太不规范了...

1) 程序应采用缩进风格编写,每层缩进使用一个制表位(TAB),类定义、方法都应顶格书写;

1232

扫码关注云+社区