前言

前面介绍了 Redis底层的数据类型，但是Redis常用的五种数据结构是怎样的呢？

文章目录

• 前言
• 一、对象类型介绍
• • 1.1 概念
  • 1.2 对象类型和编码
  • • 1）type：类型
    • 2）encoding：编码和底层实现
• 二、字符串对象
• • 2.1 编码类型
  • 2.2 编码转换
  • 2.3 字符串常用方法
• 三、列表对象
• • 3.1 编码类型
  • 3.2 编码转换
  • 3.3 常用方法
• 四、哈希对象
• • 4.1 编码类型
  • 4.2 编码转换
  • 4.3 常用方法
• 五、集合对象
• • 5.1 编码类型
  • 5.2 编码转换
  • 5.3 常用命令
• 六、有序集合对象
• • 6.1 编码类型
  • 6.2 为什么需要同时使用跳跃表和字典来实现？
  • 6.3 编码转换
  • 6.4 有序集合的实现方法
• 七、类型检查与命令多态
• • 7.1 类型检查
  • 7.2 命令执行时的多态实现
  • 7.3 内存回收
  • 7.4 对象共享

一、对象类型介绍

1.1 概念

前面介绍了几种Redis 底层使用的数据结构，比如 简单动态字符串(SDS)、双端链表、字典、压缩列表、整数集合、跳跃表等。但是Redis并没有直接使用这些数据结构，而是基于这些结构创建了一个对象系统，这个系统包含字符串对象、列表对象、哈希对象、集合对象、有序集合对象五种对象类型。

1.2 对象类型和编码

Redis每次创建键值对时，会至少创建两个对象，一个对象用作键值对的键对象，另一个作为值对象。
每个对象都由一个redisObject 结构表示，该结构包含内容：type(对象类型)、encoding(编码)、ptr(指向底层数据结构的指针)。

typedef struct redisObject {
   // 类型
   unsigned type;
   // 编码
   unsigned encoding;
   // 指向底层数据结构的指针
   void *ptr;
} robj;

1）type：类型

对于对象来说，键总是一个字符串，而值包含五种类型：字符串、列表、哈希、集合、有序集合；
我们常说的列表键指的就是 “这个数据库键所对应的值为列表对象”；

可以通过TYPE key 来查看该对象的值类型：

2）encoding：编码和底层实现

对象的 ptr 指针指向底层数据结构，而这些数据结构的类型是由 encoding 决定的。
可以通过 OBJECT ENCODING xxx 命令来查看对象的值所对应的编码。
Redis中的编码类型如下所示：

各种对象类型与相对应的编码：

二、字符串对象

字符串对象的编码可以为 int、raw、embstr

2.1 编码类型

• 如果一个对象中存储的值是整数，而且这个整数值可以用 long 来表示，那么字符串对象会将整数值保存在字符串对象结构的 ptr属性里面，并将字符串对象的编码设置为int。
  

• 如果一个对象中存储的是字符串，并且字符串值的长度大于32字节，那么会使用一个简单动态字符串（SDS）来保存这个字符串值，并将编码设置为raw。
  

• 如果一个对象中存储的是字符串，并且字符串的长度小于32字节，那么会采用embstr 编码。embstr编码是一种存储优化的编码类型，它和raw 编码类似，都使用 redisObject结构和sds结构来表示字符串对象，但是 raw 编码会调用两次内存分配函数来创建 redisObject 和 sds，embstr 编码直接调用一次内存分配函数来创建一块连续的空间，空间中包含上述两个结构。
  

• embstr 比 raw 编码优势体现在：
  (1) embstr 调用一次内存分配函数来创建一块连续空间分配给 redisObject 和 sds，而 raw 需要两次；
  (2) 释放内存时，embstr只需要调用一次内存释放函数，raw需要调用两次；
  (3) 由于内存空间连续，embstr 编码对象的字符串对象能够比 raw编码的字符串对象更好地利用缓存带来的优势。

2.2 编码转换

• 将 int 编码中存储的整数值转换为字符串(比如说调用append方法)，对象编码就会由 int 变为 raw；
  
• embstr 编码的字符串只是可读的，不能修改。当我们要修改 embstr 编码字符串时，程序会将对象编码从 embstr 转换为raw，然后再执行修改命令。

2.3 字符串常用方法

三、列表对象

列表对象的编码可以为 ziplist 或者 linkedList

3.1 编码类型

• ziplist 编码列表list 采用 ziplist 数据结构实现，其中 list 的每个节点 entry 保存一个列表元素。
  
• linkedList 编码的列表对象使用双端链表来实现，每个双端链表节点（node）都保存了一个字符串对象，而每个字符串对象都对应了一个列表元素。
  

3.2 编码转换

当同时满足下列条件时，采用 ziplist 编码，否则采用 linkedList 编码：

• 列表对象保存的所有字符串元素的长度都小于 64字节；
• 列表对象保存的元素数量小于512个；

可以在配置文件进行配置修改：
list-max-ziplist-value：保存字符串的最大长度；
list-max-ziplist-entries：最大保存元素数量；

3.3 常用方法

四、哈希对象

哈希对象的编码可以为：ziplist、hashtable

4.1 编码类型

• ziplist
  当同时满足 ①哈希对象保存的所有键值对的键和值的字符串长度都小于64字节；②哈希表保存的键值对数量小于512个。 时会采用 压缩列表作为哈希对象的底层实现，其中同一键值对的两个节点总是紧挨在一起，保存的键在前，值在后。
  

• hashtable
  另一方面，hashtable 编码的哈希对象使用字典作为底层实现，哈希对象中每个键值对都使用一个字典键值对来保存。
  

4.2 编码转换

同时满足以下条件，使用的是压缩列表，否则使用哈希表

• 哈希对象保存的所有键值对的键和值的字符串长度小于64字节；
• 哈希对象保存的键值对数量小于512个。
  

4.3 常用方法

五、集合对象

集合对象可以使用 intset 或者 hashtable 编码

5.1 编码类型

• intset
  当集合中保存的都是整数时，集合对象使用整数集合作为底层实现。
  
• hashtable
  如果集合中保存的数据都是字符串对象，那么会使用字典来实现。其中字典的每个键都是一个字符串对象(对应一个集合元素)，而字典的值全部设置为 NULL。
  

5.2 编码转换

当集合对象可以同时满足以下条件时，对象使用整数集合 intset 编码：

• 集合中保存的都是整数；
• 集合中元素个数不能超过512个；
  

5.3 常用命令

六、有序集合对象

有序集合的编码可以是：ziplist/skiplist + dict

6.1 编码类型

采用ziplist编码时，底层使用压缩列表作为数据结构实现，每个几个元素使用两个紧挨在一起的压缩列表节点来保存，第一个节点保存元素的成员，第二个元素则保存元素的分值。

采用 skiplist编码时，有序集合对象使用 zset结构作为底层实现，一个zset结构同时包含一个字典和一个跳跃表。

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

zset结构中的 zsl跳跃表按照分值从小到大保存了所有集合元素，每个跳跃表节点都保存了一个集合元素，跳跃表object属性保存了元素成员，而跳跃表节点的score属性保存了元素的分值。

zset结构中的dict字典为有序集合创建了一个从成员到分值的映射，字典的键保存元素成员，字典的值保存元素的分值。通过这个字典使得 zscore命令能够通过O(1)的复杂度来通过成员名称获取到分值。

有序集合中每个元素的成员都是一个字符串对象，而每个元素的分值都是double类型的浮点数。虽然zset结构同时使用跳跃表和字典来保存集合元素，但是这两种数据结构都会通过指针来共享元素的成员和分值，所以同时使用跳跃表和字典来保存集合元素不会产生任何重复成员或者分值，也不会因此而浪费额外的内存。

6.2 为什么需要同时使用跳跃表和字典来实现？

理论上采用任何一种数据结构都能够实现，但是无论单独使用跳跃表还是字典，在性能上对比起同时使用字典和跳跃表都会有所降低。使用字典会使得以O(1)复杂度查找成员的分值，但是对于范围操作比如 ZRANK、ZRANGE等命令时，程序都要对字典保存所有的元素进行排序，完成这种排序需要至少O(NlogN) 时间复杂度，以及额外的O(N) 内存空间。

如果使用跳跃表实现有序集合，那么跳跃表执行范围操作的优点会被保留，但是根据成员查找分值的操作的复杂度将会从O(1) 上升为 O(logN)。为了让有序集合的查找和范围型操作都尽可能地快速执行，Redis选择了同时使用字典和跳跃表两种数据结构来实现有序集合。

6.3 编码转换

当同时满足以下两个条件时，对象使用 ziplist 编码：

• 有序集合保存的元素数量小于128个；
• 有序集合保存的所有元素成员长度都小于64字节。

6.4 有序集合的实现方法

七、类型检查与命令多态

7.1 类型检查

Redis中用于操作键的命令基本上可以分为两种类型，其中一种是对于任何类型的键都可以执行的，比如DEL、EXPIRE、RENAME、TYPE、OBJECT命令。另外一种是对于特殊类型的特定命令。
因此当我们对于错误的类型使用了错误的方式时，Redis就会进行类型检查，根据对象 redisObject结构的 type属性值来判断能否执行对应的命令。

7.2 命令执行时的多态实现

比如LLEN命令，服务器除了确保执行命令的是列表键之外，还需要根据键所有的编码来选择正确的实现方式：

• 如果编码为ziplist，说明底层数据结构为压缩列表，程序将使用ziplistLen函数来返回列表的长度；
• 如果编码为linkedList，说明底层使用双端链表来实现，程序将使用linkedListLen来返回列表长度；

从面向对象的角度出发，我们就可以认为 LLEN 命令是多态的，只要执行命令的对象类型为列表键，无论采用什么编码命令都能够正常执行。
而其余的DEL、EXPLAIN等命令的区别在于，前者是基于类型的多态——一个命令可以处理多种不同类型的键；后者是基于编码的多态——一个命令可以同时适用于多种不同的编码。

7.3 内存回收

Redis 的内存回收采用引用计数法来跟踪对象的引用信息，每引用一次计数器加一，否则减一，初始化值为1。对于计数器为0的对象会被回收。

typedef struct redisObject {
   // .....
   // 引用计数
   int refcount;
   // .....
}

7.4 对象共享

在Redis中，能够让多个键共享同一个值对象，但是它只能共享字符串键或者数据结构中嵌套了字符串对象的对象 (linkedlist编码的列表对象、hashtable编码的哈希对象、hashtable编码的集合对象、zset编码的有序集合对象)。
在进行对象共享时，需要执行以下两个步骤：

• 将数据库键的指针指向同一个现有的值对象；
• 对象的引用计数器值refcount加1。

那么为什么Redis不共享包含字符串的对象？
因为Redis需要检查给定的共享对象和目标对象是否完全相同，而一个对象保存的值越复杂，验证共享对象和目标对象是否相同所需的复杂度就会越高，消耗的CPU时间也会越多。