Redis系列(九)底层数据结构之五种基础数据类型的实现

栏目: IT技术 · 发布时间: 4年前

内容简介:Redis 已经是大家耳熟能详的东西了,日常工作也都在使用,面试中也是高频的会涉及到,那么我们对它究竟了解有多深刻呢?我读了几本 Redis 相关的书籍,尝试去了解它的具体实现,将一些底层的数据结构及实现原理记录下来。本文将介绍 Redis 中

前言

Redis 已经是大家耳熟能详的东西了,日常工作也都在使用,面试中也是高频的会涉及到,那么我们对它究竟了解有多深刻呢?

我读了几本 Redis 相关的书籍,尝试去了解它的具体实现,将一些底层的数据结构及实现原理记录下来。

本文将介绍 Redis 中 五种基础数据类型 的实现方法。 这五种基本类型基本覆盖了我们业务中使用的 80%的场景,对面试也覆盖至少 90%.(其中重点当然是有序集合以及散列结构咯).

定义

在前面的八篇文章中,我们详细的介绍了 Redis 中的 8 种基本数据结构,但是众所周知,Redis 常用的数据类型有五种。包括,字符串,列表,集合,有序集合,哈希。

而这五种数据类型,底层就是用前面介绍的数据结构实现的,当然,并不是直接一对一的绑定关系,而是采用了精妙的设计,构建了一个对象系统。

熟悉 OOP 编程的读者,可能很快就能想到为什么要这么设计了,对象系统带来的好处是非常多的,但是并不在这一篇文章中讲。这里只是提到对象系统,让大家对于五种数据类型为什么可以用一些花里胡哨的方法来实现,有一个初步的了解。

接下来将逐一分析五种数据类型的底层实现数据结构,及实现方式(编码)之间的切换条件。

注:后续提到五种数据类型,用 xx 对象来指代。比如 字符串对象,列表对象。提到的底层数据结构,用全称来讲。

字符串对象

涉及到的数据结构, SDS , 强烈建议阅读本系列第一篇文章。

字符串对象的底层实现有三种可能:int, raw, embstr.

int

如果一个字符串对象,保存的值是一个整数值,并且这个整数值在 long 的范围内,那么 redis 用整数值来保存这个信息,并且将字符串编码设置为 int .

比如:

Redis系列(九)底层数据结构之五种基础数据类型的实现

raw

如果字符串对象保存的是一个 字符串 , 并且长度大于 32 个字节,它就会使用前面讲过的 SDS(简单动态字符串) 数据结构来保存这个字符串值,并且将字符串对象的编码设置为 raw .

Redis系列(九)底层数据结构之五种基础数据类型的实现

embstr

如果字符串对象保存的是一个 字符串 , 但是长度小于 32 个字节,它就会使用 embstr 来保存了, embstr 编码不是一个数据结构,而是对 SDS 的一个小优化,当使用 SDS 的时候,程序需要调用两次内存分配,来给 字符串对象 和 SDS 各自分配一块空间,而 embstr 只需要一次内存分配,因为他需要的空间很少,所以采用 连续的空间保存,即将 SDS 的值和 字符串对象的值放在一块连续的内存空间上。这样能在短字符串的时候提高一些效率。

比如:

Redis系列(九)底层数据结构之五种基础数据类型的实现

浮点数如何保存?

redis 的字符串数据类型是支持保存浮点数,并且支持对浮点数进行加减操作,但是 redis 在底层是把浮点数转换成字符串值,之后走上面三种编码的规则的。对浮点数进行操作时,也是从字符串转换成浮点数进行计算,然后再转换成字符串进行保存的。

编码转换条件

这块的知识其实是很符合我们的认知的,比如 int 编码只可以保存整数,那么当我们对一个 int 编码的字符串对象,修改它的值,它自然就会使用 raw 编码了。

但是有一个特性,Redis 没有为 embstr 编码提供任何的修改操作,这也就是为什么它只是个编码而不是一个数据结构的原因。

所以在 Redis 中, embstr 编码的值其实是 只读 的,只要发生修改,立刻将编码转换成 raw .

总结

字符串对象底层的数据结构或者说编码有三种,分别是 int , raw , embstr . 他们之间的使用条件如下:

编码 使用条件
int 可以用 long 保存的整数
embstr 字符串长度小于 32 字节(或者浮点数转换后满足)
raw 长度大于 32 的字符串

列表对象

涉及到的数据结构, 压缩列表 , 双向链表 , 快速列表 , 强烈建议阅读本系列的第 二,三,四 篇文章。

在 Redis 3.2 版本之前,列表对象底层由 压缩列表和双向链表配合实现,当元素数量较少的时候,使用压缩列表,当元素数量增多,就开始使用普通的双向链表保存数据。

但是这种实现方式不够好,双向链表中的每个节点,都需要保存前后指针,这个内存的使用量 对于 Redis 这个内存数据库来说极其不友好。

因此在 3.2 之后的版本,作者新实现了一个数据结构,叫做 quicklist . 所有列表的底层实现都是这个数据结构了。它的底层实现基本上就是将 双向链表和压缩列表进行了结合,用双向的指针将压缩列表进行连接,这样不仅避免了压缩列表存储大量元素的性能压力,同时避免了双向链表连接指针占用空间过多的问题。

具体的原理讲解请 阅读对应的文章,这里不再赘述。

总结

编码 使用条件
quicklist 所有数据

集合对象

涉及到的数据结构: intset , dict(hashtable) , 强烈建议阅读本系列第五,第六篇文章。

集合对象的编码可以是 intset 或者 hashtable(字典) .

intset

当集合中的所有元素都是整数,且元素的数量不大于 512 个的时候,使用 intset 编码。

Redis系列(九)底层数据结构之五种基础数据类型的实现

intset 编码时,底层使用 intset 数据结构。

hashtable

当元素不符合 全部为整数值且元素个数小于 512 时,集合对象使用的编码方式为 hashtable .

字典的每一个键都是一个字符串对象,其中保存了集合里的一个元素,字典的值全部被设置为 NULL.

Redis系列(九)底层数据结构之五种基础数据类型的实现

总结

编码 使用条件
intset 所有元素都是整数且元素个数小于 512
hashtable 其他数据

有序集合对象

涉及到的数据结构, 压缩列表 , 跳跃表 , 字典 , 强烈建议阅读本系列 第三篇,第六篇,第七篇文章。

有序集合对象的编码可以是 ziplist 以及 skiplist .

ziplist 编码

当使用 ziplist 编码时,有序集合对象的实现数据结构为 ziplist (听起来像句废话), 每个集合的元素 (key-value), 使用两个紧挨着的压缩列表的节点来表示,第一个节点保存集合元素的成员 (member), 第二个节点保存集合元素的分支 (score).

在压缩列表的内部,集合元素按照分值从小到大进行排序。

Redis系列(九)底层数据结构之五种基础数据类型的实现

skiplist 编码

当使用 skiplist 编码的时候,内部使用 zset 来实现数据的保存, zset 的定义如下:

typedef struct zset{
  zskiplist *zsl;
  dict *dict;
}zset;

为什么需要同时使用跳跃表以及字典呢?

其实如果我们细想,单独使用字典或者跳跃表,都是可以实现有序集合的所有功能的,但是性能太差劲了。

  • 当我们只使用字典来实现,我们可以以 O(1) 的时间复杂度获取成员的分值,但是由于字典是无序的,当我们需要进行范围性操作的时候,需要对字典中的所有元素进行排序,这个时间复杂度至少需要 O(nlogn).
  • 当我们只使用跳跃表来实现,我们可以在 O(logn) 的时间进行范围 排序 操作,但是如果要获取到某个元素的分值,时间复杂度也是 O(logn).

因此,将字典和跳跃表结合进行使用,可以在 O(1) 的时间复杂度下完成查询分值操作,而对一些范围操作,使用跳跃表可以达到 O(logn) 的是缠绵复杂度。

Redis系列(九)底层数据结构之五种基础数据类型的实现

可以看到,我在上一次的例子中,添加了一个很长的 key 之后,有序集合的编码方式就成为了 skiplist .

总结

编码 使用条件
ziplist 元素数量少于 128 且 所有元素成员的长度小于 64 字节
skiplist 不满足上述条件的其他情况

散列对象

涉及到的数据结构, 压缩列表 , 字典 , 强烈建议阅读本系列 第三篇,第六篇文章。

哈希对象的编码可以是 ziplist 或者 hashtable .

ziplist 编码

ziplist 编码下的哈希对象,使用了压缩列表作为底层实现数据结构,用两个连续的压缩列表节点来表示哈希对象中的一个键值对。实现方式类似于上面的有序集合的场景。

Redis系列(九)底层数据结构之五种基础数据类型的实现

如图中所示,当我放入了两个简单的键值对,此时哈希对象的编码为 ziplist.

hashtable 编码

这是对 hashtable 最直观的应用了~

哈希结构本身在结构上和字典 (hashtable) 就颇为相似,因此哈希对象中的每一个键值对都是字典中的一个键值对。

  • 字典的每一个键都是一个字符串对象,对象中保存了键值对的键。
  • 字典的每一个值都是一个字符串对象,对象中保存了键值对的值。

Redis系列(九)底层数据结构之五种基础数据类型的实现

如图中所示,当我在上一个示例中额外加入一个很长的值,那么编码方式就来到了 hashtable .

总结

编码 使用条件
ziplist 键值对的键和值的长度都小于 64 字节,且 键值对个数小于 512.
hastable 不满足上述条件的其他条件

全文总结

其实在前面的几篇文章写完之后,也就是在所有的底层数据结构介绍完之后,所谓的 Redis 的五种基础数据类型的底层实现原理 就已经没有了难度。

所有用到的底层数据结构都知道了,剩下的无非是个排列组合问题以及各种实现方式之间的切换条件,然后这个条件也仅仅是了解性知识,强行记住也没有必要。

这里把五种基础数据类型的可能的编码列出来方便理解及记忆。

基础数据类型 可能的编码方式
字符串 int, raw, embstr
列表 之前是 ziplist 和 linkedlist, 现在全是 quicklist 了。
集合 intset 或者 hashtable
有序集合 ziplist 或者 skiplist , skiplist 编码中使用了跳跃表+字典
散列 ziplist 或者 hashtable

至于他们的转换条件,由于我不会用 markdown 画多维表格,但是又不想写 html, 就不做总结了,需要的读者可以点击目录跳转至每一个小结的总结~.

参考文章

《Redis 的设计与实现(第二版)》

《Redis 深度历险:核心原理和应用实践》

完。

联系我

最后,欢迎关注我的个人公众号【 呼延十 】,会不定期更新很多后端工程师的学习笔记。

也欢迎直接公众号私信或者邮箱联系我,一定知无不言,言无不尽。

Redis系列(九)底层数据结构之五种基础数据类型的实现

以上皆为个人所思所得,如有错误欢迎评论区指正。

欢迎转载,烦请署名并保留原文链接。

联系邮箱:huyanshi2580@gmail.com

更多学习笔记见个人博客或关注微信公众号 < 呼延十 >------> 呼延十


以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

C语言程序开发范例宝典

C语言程序开发范例宝典

2010-1 / 59.00元

《C语言程序开发范例宝典》全面介绍了应用C语言进行开发的各种技术和技巧,全书共分12章,内容包括基础知识、指针、数据结构、算法、数学应用、文件操作、库函数应用、图形图像、系统调用、加解密与安全性、游戏、综合应用等。全书共提供300个实例,每个实例都突出了其实用性。 《C语言程序开发范例宝典》既可作为C程序的初学者学习用书,也可作为程序开发人员、相关培训机构老师和学生的参考用书。一起来看看 《C语言程序开发范例宝典》 这本书的介绍吧!

CSS 压缩/解压工具
CSS 压缩/解压工具

在线压缩/解压 CSS 代码

JSON 在线解析
JSON 在线解析

在线 JSON 格式化工具

图片转BASE64编码
图片转BASE64编码

在线图片转Base64编码工具