Redis 的基础数据结构(二) 整数集合、跳跃表、压缩列表

上篇文章写了 Redis 基础数据结构的可变字符串、链表、字典。大家可以点击链接查看。今天我们继续研究 Redis 的基础数据结构。

  • 整数集合
  • 跳跃表
  • 压缩列表

整数集合

当一个集合只包含整数,且这个集合的元素不多的时候,Redis 就会使用整数集合 intset 。首先看 intset 的数据结构:

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

其实 intset 的数据结构比较好理解。一个数据保存元素,length 保存元素的数量,也就是contents的大小,encoding 用于保存数据的编码方式。

通过代码我们可以知道,encoding 的编码类型包括了:

#define INTSET_ENC_INT16 (sizeof(int16_t))
#define INTSET_ENC_INT32 (sizeof(int32_t))
#define INTSET_ENC_INT64 (sizeof(int64_t))

实际上我们可以看出来。 Redis encoding的类型,就是指数据的大小。作为一个内存数据库,采用这种设计就是为了节约内存。

既然有从小到大的三个数据结构,在插入数据的时候尽可能使用小的数据结构来节约内存,如果插入的数据大于原有的数据结构,就会触发扩容。

扩容有三个步骤:

  1. 根据新元素的类型,修改整个数组的数据类型,并重新分配空间
  2. 将原有的的数据,装换为新的数据类型,重新放到应该在的位置上,且保存顺序性
  3. 再插入新元素

整数集合不支持降级操作,一旦升级就不能降级了。

跳跃表

跳跃表是链表的一种,是一种利用空间换时间的数据结构。跳表平均支持 O(logN),最坏O(N)复杂度的查找。

跳表是由一个zskiplist 和 多个 zskiplistNode 组成。我们先看看他们的结构:

/* ZSETs use a specialized version of Skiplists *//*
 * 跳跃表节点
 */

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

    } zskiplistNode;
        
/*
 * 跳跃表
 */

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

} zskiplist;

所以根据这个代码我们可以画出如下的结构图:

其实跳表就是一个利用空间换时间的数据结构,利用 level 作为链表的索引。

之前有人问过 Redis 的作者 为什么使用跳跃表,而不是 tree 来构建索引?作者的回答是:

  1. 省内存。
  2. 服务于 ZRANGE 或者 ZREVRANGE 是一个典型的链表场景。时间复杂度的表现和平衡树差不多。
  3. 最重要的一点是跳跃表的实现很简单就能达到 O(logN)的级别。

压缩列表

压缩链表 Redis 作者的介绍是,为了尽可能节约内存设计出来的双向链表。

对于一个压缩列表代码里注释给出的数据结构如下:

zlbytes 表示的是整个压缩列表使用的内存字节数

zltail 指定了压缩列表的尾节点的偏移量

zllen 是压缩列表 entry 的数量

entry 就是 ziplist 的节点

zlend 标记压缩列表的末端

这个列表中还有单个指针:

ZIPLIST_ENTRY_HEAD 列表开始节点的头偏移量

ZIPLIST_ENTRY_TAIL 列表结束节点的头偏移量

ZIPLIST_ENTRY_END 列表的尾节点结束的偏移量

再看看一个 entry 的结构:

/*
 * 保存 ziplist 节点信息的结构
 */

typedef struct zlentry {
    // prevrawlen :前置节点的长度
    // prevrawlensize :编码 prevrawlen 所需的字节大小
    unsigned int prevrawlensize, prevrawlen;
    // len :当前节点值的长度
    // lensize :编码 len 所需的字节大小  
    unsigned int lensize, len;
    // 当前节点 header 的大小
    // 等于 prevrawlensize + lensize
    unsigned int headersize;
    // 当前节点值所使用的编码类型
    unsigned char encoding;
    // 指向当前节点的指针
    unsigned char *p;

} zlentry;

依次解释一下这几个参数。

prevrawlen 前置节点的长度,这里多了一个 size,其实是记录了 prevrawlen 的尺寸。Redis 为了节约内存并不是直接使用默认的 int 的长度,而是逐渐升级的。 同理 len 记录的是当前节点的长度,lensize 记录的是 len 的长度。 headersize 就是前文提到的两个 size 之和。 encoding 就是这个节点的数据类型。这里注意一下 encoding 的类型只包括整数和字符串。 p 节点的指针,不用过多的解释。

需要注意一点,因为每个节点都保存了前一个节点的长度,如果发生了更新或者删除节点,则这个节点之后的数据也需要修改,有一种最坏的情况就是如果每个节点都处于需要扩容的零界点,就会造成这个节点之后的节点都要修改 size 这个参数,引发连锁反应。这个时候就是 压缩链表最坏的时间复杂度 O(n^2)。不过所有节点都处于临界值,这样的概率可以说比较小。

总结

至此Redis的基本数据结构就介绍完了。我们可以看到 Redis 对内存的使用真是“斤斤计较”,对于内存是使用特别节约。同时 Redis 作为一个单线程应用,不用考虑并发的问题,将很多类似 size 或者 length 的参数暴露出来,将很多 O(n) 的操作降低为 O(1)。大大提升效率。下一讲,将会介绍 Redis 是怎么通过这些数据结构向外提供服务。 Redis 的代码真是写的太棒了,简洁高效。值得大家学习。

原文发布于微信公众号 - 犀利豆的技术空间(xilidou1)

原文发表时间:2018-03-16

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏企鹅号快讯

Python模块知识4:序列化Json/pickle

序列化与反序列化 序列化:把Python的基本数据类型转为字符串 反序列化:把字符串转为Python的基本数据类型 Python中用于序列化的两个模块: jso...

2269
来自专栏用户画像

7.7.4 置换选择排序(生成初始归并段)

7.7.3讨论了如何使用m路归并来减少磁盘访问次数。从第7.7.2的讨论可知,减少初始归并段个数r也可以减少归并趟数S。若总的记录个数为n,每个归并段的长度为L...

1442
来自专栏闻道于事

Java异常处理中的恢复模型

2844
来自专栏开源优测

[接口测试_B] 03 Pytest断言处理_assert和异常断言

Pytest的断言方式及应用场景 使用assert语句 断言预期的异常 断言预期的告警 利用上下文信息进行断言 自定义断言方式 使用assert语句进行断言...

44411
来自专栏机器人网

只会G代码不会宏,就别说你是数控师傅

一、变量 普通加工程序直接用数值指定G代码和移动距离;例如,GO1和X100.0。使用用户宏程序时,数值可以直接指定或用变量指定。当用变量时,变量值可用程序或用...

2884
来自专栏祥子的故事

Python编程快速上手 让繁琐工作自动化 | 第三章 :实践项目

3126
来自专栏SDNLAB

Open vSwitch系列之数据结构解析深入分析ofpbuf

上一篇我们分析了hmap,hamp可以说是Open vSwitch中基石结构,很多Open vSwitch中数据结构都依赖hmap。本篇我们来分析一下ofpbu...

3868
来自专栏申龙斌的程序人生

Eclipse油藏模型解析程序

2010年的时候,三维可视化项目中要读取eclipse建模软件产生的三维模型网格数据,经过连续多天的奋战,终于搞明白eclipse数模软件输出的egrid、in...

3327
来自专栏Spark学习技巧

Flink DataSet编程指南-demo演示及注意事项

Flink中的DataStream程序是对数据流进行转换的常规程序(例如,过滤,更新状态,定义窗口,聚合)。数据流的最初的源可以从各种来源(例如,消息队列,套接...

4.3K12
来自专栏debugeeker的专栏

《coredump问题原理探究》Linux x86版5.7节C风格数据结构内存布局之结构体数组

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/xuzhina/article/detai...

851

扫码关注云+社区

领取腾讯云代金券