剖析Redis常用数据类型对应的数据结构

谁借莪１个温暖的怀抱￠ 2022-12-14 03:52 134阅读 0赞

## 一 概述 ##

Redis是一种键值(Key-Value)数据库。相对于关系型数据库（如MySQL），Redis也被称作关系型数据库。像MySQL这样的关系型数据库，表结构比较复杂，包含的字段较多，可以通过SQL语句实现复杂的查询需求。而Redis中只包含“键”和“值”两部分，只能通过“键”来查询“值”。由于这种简单的存储结构，让Redis的读写效率非常高。

除此之外，Redis主要是作为内存数据库来使用，也就是说，数据是存储在内存中的。尽管它经常被用作内存数据库，但是，它也支持将数据存储在硬盘中。

Redis中，键的数据类型是字符串，但是为了丰富数据存储的方式，方便开发者使用，值的数据类型有很多，常用的数据类型有字符串，列表，字典，集合，有序集合。

## 二 Redis值数据的不同数据结构 ##

**1. 字符串(String)：**这种数据结构非常简单，对应的就是数据结构中的字符串。

**2. 列表(List)：**列表这种数据类型支持存储一组数据。这种数据类型对应两种实现方法，一种是压缩列表(ziplist)，另一种是双向循环链表。

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

1.  列表中保存的单个数据（有可能是字符串类型的）小于64字节；
2.  列表中的数据个数少于512个。

压缩列表并非基础的数据结构，而是Redis中按需求设计的一种数据结构，它类似于数组，通过一片连续的内存空间，来存储数据。不过，它跟数组不同的一点是，它允许存储的数据大小不同的同时支持不同数据类型数据的存储。

![20201013102416227.png][]

在数组结构中，每个元素的大小是相同的，如果我们要存储不同长度的字符串，那我们就需要用最大长度的字符串大小作为元素的大小。这时候就会造成存储空间的让费。

![20201013103014274.png][]

除此之外，在Redis中基于压缩列表的数据结构的数据是保存在一片连续的内存空间，通过键值来获取值列表类型的数据，读取的效率也是非常高的。

当列表中存储的数据量比较大的时候，也就是不能够满足条件1和条件2的时候，列表就要通过双向循环链表来实现了。

在Redis的双向链表的实现方式中，它额外定义了一个list结构体，来组织链表的首，尾指针，还有长度等信息。

typedef struct listNode {
        struct listNode *prev;
        struct listNode *next;
        void *value;
    } listNode;
    
    typedef struct list {
        listNode *head;
        listNode *tail;
        unsigned long len;
    }list;

**3 字典（hash）:** 字典类型用来存储一组数据对，每个数据又包含了键值两个部分。字典类型也有两种实现方式，一种为压缩列表，另一种为散列表。

**Redis中的字典是由dict.h/dict结构定义：**

typedef struct dict{
       //类型特定函数
    	dictType *type;
    	//私有数据
    	void *privdata;
    	//哈希表
    	dictht ht[2];
    	//rehash索引
    	//当rehash不在进行时，值为-1
    	int rehashidx;
    }dict;

**Redis字典所使用的哈希表由 dict.h/dictht结构定义：**

typedef struct dictht{
         //哈希表数组
         dictEntry **table;
         //哈希表大小
         unsigned long size;
         //哈希表大小掩码，用于计算索引值
         //总是等于 size-1
         unsigned long sizemask;
         //该哈希表已有节点的数量
         unsigned long used;
         }dictht；

**哈希表节点使用dictEntry结构表示，每个dictEntry结构都保存着一个键值对：**

typedef struct dictEntry{
         //键
         void *key;
         //值
         union{
              void *val;
              uint64_tu64;
              int64_ts64;
         }v;
    
         //指向下一个哈希表节点，形成链表
         struct dictEntry *next;
    }dictEntry；

我们存储时需要对键值的键进行哈希运算，这种方式会存在哈希冲突，所以为每个结点加一个指向哈希表节点的指针并通过拉链法或者称为拉链法解决Hash冲突。

解决哈希冲突的另一种方法是开放寻址法。

Redis利用字典类型存储数据时，只有当存储的数据量比较小的情况下，Redis才使用压缩列表来实现字典类型，同样要满足两个条件：

1.  字典中保存的键和值的大小都要小于64字节；
2.  字典中键值对的个数要小于512个。

当不能同时满足上述两个条件的时候，Redis就是用散列表来实现字典类型。Redis使用MurmurHash2这种运行速度快，随机性好的哈希算法作为对键进行hash计算的哈希函数。然后对hash冲突的问题，Redis使用链表法来解决。此外，Redis还支持散列表的动态扩容，缩容。

当数据动态增加之后，散列表的装载因子会不停地变大。为例比避免散列表性能的下降，当装载因子**(装载因子=哈希表已经保存的节点数/哈希表的大小)**大于1的时候，Redis会触发扩容，将散列表扩大为原来的2倍左右。

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

为了解决Redis在扩缩容要做大量的数据搬移和哈希值的重新计算而耗时的问题，Redis使用了渐进式扩容缩容策略，将数据的搬移分批进行，以避免出现大量数据一次性搬移导致的服务停顿问题。

**4 集合(set):** 集合这种数据类型用来存储一组不重复的数据，这种数据类型也存在两种实现方法，一种时基于有序数组，另一种事基于散列表。

当要存储的数据同时满足下述两个条件的时候，Redis就采用有序数组，一种是基于有序数组，另一种是基于散列表。

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

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

**5 有序集合(sortedset):** 有序集合这种数据类型，它用来存储一组数据，并且每个数据都会附带一个得分。通过得分的大小，我们将数据组织成跳表这样的数据结构，以支持快速地按照得分值，得分区间获取数据。

实际上，跟Redis的其他数据类型一样，有序集合也并不仅仅只有跳表这一种方式。当数据量比较小的时候，Redis会用压缩列表来实现有序集合。当然，需要同时满足以下两个条件：

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

## 三 Redis数据结构的持久化 ##

尽管Reids经常会被用作内存数据库，但是，它也支持数据持久化到硬盘中，使得在机器断电或者宕机的情况下，存储在Redis中的数据也不会丢失。在机器重新启动之后，Redis只需要再将存储在硬盘中的数据，重新读取到内存，就可以继续工作。

Redis的数据结构格式由“键”和“值”两个部分组成。而“值”又支持很多数据类型，比如字符串，列表，字典，集合，有序集合。

其中字典和集合等值类型，底层用到了散列表，散列表中有指针的概念，而指针指向的是内存中的存储地址。此时就会有一个被称为**数据结构持久化的问题**或者**对象的持久化问题**，即如何将一个跟具体地址有关的数据结构存储到磁盘中。

**解决数据结构持久化问题或者对象的持久化问题的解决思路：**

**第一种：**清除原来的存储结构，只将数据存储到磁盘中。当我们需要从磁盘还原数据到内存的时候，再重新将数据组织成原来的数据结构。这也是Redis实际采用的持久化思路。

但是这种思路存在一定的弊端，那就是数据从硬盘还原到内存的过程，会耗用比较多的时间。如，我们现在要将散列表中的数据存储到磁盘中。当我们从磁盘中，取出数据重新构建散列表的时候，需要重新计算每个数据的哈希值。如果磁盘中存储的数据很大的时候，则重新构建数据结构的耗时就不可忽视了。

**第二种：**这种方式是保留数据原来的存储格式，将数据按照原有的格式存储在磁盘中。如数据结构为散列表的时候，我们将散列表的大小，每个数据被散列到的槽的编号等信息，都保存到磁盘中。基于磁盘中的这些信息，我们从磁盘中将数据还原到内存中的时候，就可以避免重新计算哈希值。

## 四 总结 ##

Redis中常用的数据类型底层依赖的数据结构大致分为：**压缩列表（一种特殊的数组），有序数组，链表，散列表，跳表。**事实上，Redis就是对这些常用数据结构的封装。

[20201013102416227.png]: /images/20221123/f9cfd205ea9a4352b7092468f756e6d6.png
[20201013103014274.png]: /images/20221123/e08410f35a174431be85917fa05a31f2.png