Redis常用数据类型使用的数据结构

本文参考资源:

Redis数据结构——压缩列表 - 老於` - 博客园

极客时间《数据结构与算法之美》

总体来说,Redis的key-value数据存储是通过哈希表实现的,那么具体到某一数据类型,又是使用了什么数据结构呢?这里我们着重看Redis中的五大数据类型:String、Hash、List、Set、Sorted_set。其中String类型非常简单,就是字符串。

List

我们先来看列表。列表这种数据类型支持存储一组数据。这种数据类型对应两种实现方法,一种是压缩列表(ziplist),另一种是双向循环链表。

压缩列表(ZipList)

当列表中存储的数据量比较小的时候,列表就可以采用压缩列表的方式实现。具体需要同时满足下面两个条件:

  • 列表中保存的单个数据(有可能是字符串类型的)小于 64 字节。
  • 列表中数据个数少于 512 个。

它不是基础数据结构,而是 Redis 自己设计的一种数据存储结构。它有点儿类似数组,通过一片连续的内存空间,来存储数据。不过,它跟数组不同的一点是,它允许存储的数据大小不同(可以混合存储不同类型,不同大小的数据)。

听到“压缩”两个字,直观的反应就是节省内存。之所以说这种存储结构节省内存,是相较于数组的存储思路而言的。我们知道,数组要求每个元素的大小相同,如果我们要存储不同长度的字符串,那我们就需要用最大长度的字符串大小作为元素的大小(假设是20个字节)。存储小于 20 个字节长度的字符串的时候,便会浪费部分存储空间。

Redis常用数据类型使用的数据结构

数组的优势是占用一片连续的空间可以很好的利用CPU缓存访问数据。如果我们想要保留这种优势,又想节省存储空间我们可以对数组进行压缩。

Redis常用数据类型使用的数据结构

但是这样有一个问题,我们在遍历它的时候由于不知道每个元素的大小是多少,因此也就无法计算出下一个节点的具体位置。这个时候我们可以给每个节点增加一个length的属性。

Redis常用数据类型使用的数据结构

这种设计思想并不少见,java的class文件字节码中涉及到字段表、方法表、属性表,都会先给一个数据项数,然后紧跟的是数据项的列表,每一个数据项开头都会记录数据项的长度。这部分相关内容见Java字节码实例探究

Redis中的压缩列表,构成如下图:

Redis常用数据类型使用的数据结构

一个压缩列表可以包含任意多个节点(entry),每个节点可以保存一个字节数组或者一个整数值。除了存储节点外,头部还存储了额外的信息:

  • zlbytes:列表总长度
  • zltail:最后一个节点地址据列表起始地址的偏移量
  • zllen:节点个数

尾部附加了一个zlend作为结束的标识。

压缩列表相较于数组,虽然节省了空间,但失去了数组的随机访问性,由于每个数据项的大小都可能不同,不能通过计算偏移量来获取某一中间元素的地址,只能顺序访问,这一点就跟链表一样,比链表好的是物理上的存储还是连续的,不必多次寻址。所以数据项较多时压缩列表就不适用了,进而使用双向循环链表。

双向循环链表

当不满足压缩列表的使用条件时,就使用双向循环链表,这部分较简单。

Redis常用数据类型使用的数据结构

Hash

Hash类型又称字典类型,也有两种实现方式。一种是我们刚刚讲到的压缩列表,另一种是散列表。

同样,只有当存储的数据量比较小的情况下,Redis 才使用压缩列表来实现字典类型。具体需要满足两个条件:

  • 字典中保存的键和值的大小都要小于 64 字节;
  • 字典中键值对的个数要小于 512 个。

当不能同时满足上面两个条件的时候,Redis 就使用散列表来实现字典类型。Redis 使用MurmurHash2 这种运行速度快、随机性好的哈希算法作为哈希函数。对于哈希冲突问题,Redis 使用链表法(拉链法)来解决。除此之外,Redis 还支持散列表的动态扩容、缩容。

当数据动态增加之后,散列表的装载因子会不停地变大。为了避免散列表性能的下降,当装载因子大于 1 的时候(对于使用拉链法解决哈希冲突的哈希表装载因子是有可能大于1的),Redis 会触发扩容,将散列表扩大为原来大小的 2 倍左右。

当数据动态减少之后,为了节省内存,当装载因子小于 0.1 的时候,Redis 就会触发缩容,缩小为字典中数据个数的大约 2 倍大小。

由于扩容缩容要做大量的数据搬移和哈希值的重新计算,比较耗时。针对这个问题,Redis 使用了渐进式扩容缩容策略,将数据的搬移分批进行,避免了大量数据一次性搬移导致的服务停顿。

Set

集合这种数据类型用来存储一组不重复的数据。这种数据类型也有两种实现方法,一种是基于有序数组,另一种是基于散列表。

当要存储的数据,同时满足下面这样两个条件的时候,Redis 就采用有序数组,来实现集合这种数据类型。

  • 存储的数据都是整数。
  • 存储的数据元素个数不超过 512 个。

当不能同时满足这两个条件的时候,Redis 就使用散列表来存储集合中的数据。

Sorted_set

Sorted_set又称有序集合,它用来存储一组数据,并且每个数据会附带一个得分(权重)。根据得分实现对个数据进行排序。

它的底层通过跳表实现,相关内容参考跳表-披着链表外衣的伪搜索树。通过得分的大小,我们将数据组织成跳表这样的数据结构,以支持快速地按照得分值、得分区间获取数据。

实际上,跟 Redis 的其他数据类型一样,有序集合也并不仅仅只有跳表这一种实现方式。当数据量比较小的时候,Redis 会用压缩列表来实现有序集合。具体点说就是,使用压缩列表来实现有序集合的前提,有这样两个:

  • 所有数据的大小都要小于 64 字节。
  • 元素个数要小于 128 个。

原创文章,作者:彭晨涛,如若转载,请注明出处:https://www.codetool.top/article/redis%e5%b8%b8%e7%94%a8%e6%95%b0%e6%8d%ae%e7%b1%bb%e5%9e%8b%e4%bd%bf%e7%94%a8%e7%9a%84%e6%95%b0%e6%8d%ae%e7%bb%93%e6%9e%84/