Redis面试（三）：底层数据结构（一）

2.6 底层数据结构(编码)

Redis对外提供了string,list,hash,set,zet等类型，但是Redis内部针对不同类型存在编码(底层数据结构)的概念，所谓编码就是具体使用哪种底层数据结构来实现。编码不同将直接影响数据的内存占用和读写效率。 使用 object encoding {key} 命令获取编码类型。如下:

 redis> set str:1 hello
 OK
 redis> object encoding str:1
 "embstr" # embstr编码字符串
 redis> lpush list:1 1 2 3
 (integer) 3
 redis> object encoding list:1
 "ziplist" #  ziplist编码列表

Redis针对每种数据类型(type)可以采用至少两种编码方式来实现，下表表示type和encoding的对应关系。

2.6.1 SDS

1. 介绍

虽然 Redis 是用 C 语言写的，但是 Redis 并没有使用 C 的字符串表示，而是自己构建了一种 简单动态字符串（Simple Dynamic String，SDS）。

SDS结构如下：

 struct sdshdr{ 
     unsigned int len;   // 记录buf数组中已使用字节的数量
     unsigned int free;  // 记录 buf 数组中未使用字节的数量 
     char buf[];         // 字节数组，用于保存字符串
 }

SDS 结构图如下：

相比于 C 的原生字符串，Redis 的 SDS 不光可以保存文本数据还可以保存二进制数据，并且获取字符串长度复杂度为 O(1)（C 字符串为 O(N)）, 除此之外，Redis 的 SDS API 是安全的，不会造成缓冲区溢出。

2. 优点

SDS相比于C语言中的普通字符串有以下优势和特点：

1. 动态扩展：SDS可以根据需要动态地扩展字符串的长度，而无需事先预分配足够的空间。这使得字符串的拼接和修改操作更加高效。
2. 空间预分配：当SDS扩展字符串时，会预先分配一定的额外空间，以减少频繁扩展的次数，提高性能。
3. O(1)复杂度的长度获取：通过len字段，可以在O(1)的时间复杂度内获取字符串的长度，而无需遍历整个字符串。
4. 二进制安全：SDS不仅可以存储文本字符串，还可以存储二进制数据。它的字符串值不以空字符'\0'作为结尾，而是通过len字段来标识字符串的长度，因此可以存储包含空字符在内的任意二进制数据。
5. 减少缓冲区溢出的风险：由于SDS在内部记录了字符串的长度，因此在进行字符串操作时，可以防止缓冲区溢出的风险，提高了安全性。

2.6.2 双向链表

1. 介绍

在Redis中，每个列表都由一个双向链表来实现，该链表的每个节点表示列表中的一个元素。每个节点都包含了指向前一个节点和后一个节点的指针，并且节点中存储了实际的元素值。

双向链表的节点结构如下：

 typedef struct listNode {
     struct listNode *prev;   // 前一个节点指针
     struct listNode *next;   // 后一个节点指针
     void *value;             // 节点存储的元素值
 } listNode;

而列表本身由一个列表对象（listObject）来包装，其中包含指向链表头节点和尾节点的指针，以及列表的长度（即节点的数量）。

列表对象结构如下：

 typedef struct list {
     listNode *head;   // 链表头节点指针
     listNode *tail;   // 链表尾节点指针
     unsigned long len;// 列表长度（节点数量）
     //...
 } list;

2. 优点

通过双向链表的结构，Redis的列表数据类型具备了以下特点和优势：

1. 高效的插入和删除操作：由于双向链表可以通过节点的指针快速找到前后节点，所以在插入和删除元素时具有较低的时间复杂度。
2. 可以在两端进行操作：双向链表支持在头部和尾部进行插入和删除操作，因此Redis的列表类型可以从列表两端快速添加或删除元素。
3. 顺序访问和反向访问：双向链表允许按照正向和反向的顺序遍历元素，这在某些场景下非常有用。
4. 可变长度：双向链表的长度可以动态增长和缩减，因此Redis的列表类型可以根据需要自由地添加或删除元素。

2.6.3 压缩列表

1. 介绍

压缩列表（ziplist） 是 Redis 为了节省内存而开发的，是由一系列特殊编码的 连续内存块 组成的顺序型数据结构，一个压缩列表可以包含任意多个节点（entry），每个节点可以保存一个字节数组或者一个整数值。

压缩列表并不是对数据利用某种算法进行压缩，而是将数据按照一定规则编码在一块连续的内存区域，目的是节省内存。

压缩列表的结构如下：

 | zlbytes | zltail | zllen | entry1 | entry2 | ... | entryN | zlend |

• zlbytes：表示压缩列表占用的字节数。
• zltail：指向压缩列表的尾部元素。
• zllen：表示压缩列表中的元素数量。
• entry1、entry2、...、entryN：压缩列表中的元素，每个元素包含长度字段和实际存储的数据。
• zlend：表示压缩列表的末尾

压缩列表的每个节点构成如下：

 | PrevLen | PrevEntryLength | EntryLength | EntryData |

• 前一个节点字节数（PrevLen）：这是一个可选字段，用于表示前一个压缩列表节点的长度。如果当前节点是第一个节点，则该字段不存在。
• 前一个节点的长度（PrevEntryLength）：这是一个可选字段，用于表示前一个压缩列表节点的数据长度。如果当前节点是第一个节点，则该字段不存在。
• 当前节点的长度（EntryLength）：这是一个固定长度的字段，用于表示当前节点的数据长度（包括数据本身和可能的额外信息）
• 当前节点数据（EntryData）：这是当前节点的实际数据，可以是整数、字符串或其他类型的值。根据压缩列表的编码方式不同，数据可以采用不同的格式进行存储。 压缩列表的元素可以是不同类型的值，根据值的特性，它们被存储为不同的编码方式。例如，整数可以使用整数编码进行存储，而字符串则使用字节数组编码进行存储。 这种灵活的编码方式使得压缩列表能够根据实际数据类型进行优化，节省内存空间。

2. 优点

压缩列表（ziplist）在Redis中具有以下几个优点：

1. 内存效率：压缩列表以紧凑的方式存储数据，可以在相对较小的内存空间中存储多个元素。相比于使用其他数据结构（如链表或哈希表），压缩列表在存储小型列表或哈希时可以节省内存。
2. 连续内存存储：压缩列表使用连续的内存块来存储数据，这使得对于连续内存访问的操作更加高效。这有助于提高数据访问速度，减少内存碎片化的问题。
3. 快速插入和删除：压缩列表对于在列表或哈希的两端进行插入和删除操作非常高效。Redis可以在不进行大规模内存重新分配和复制的情况下，快速调整压缩列表的大小以适应新的元素。
4. 灵活的元素类型：压缩列表可以存储不同类型的元素，包括整数、字符串和字节数组等。它根据元素的特性使用不同的编码方式，以最大程度地减少内存占用。这种灵活性使得压缩列表适用于存储多种数据类型的集合。
5. 顺序访问效率：压缩列表提供了高效的顺序访问，可以快速地遍历整个列表或哈希。这对于处理有序数据集合非常有用，例如范围查询或迭代操作。

2.6.4 整数集合

1. 介绍

整数集合（intset） 是 Redis 用于保存整数值的集合抽象数据类型，它可以保存类型为 int16_t、int32_t 或者 int64_t 的整数值，并且保证集合中不会出现重复元素。

整数集合底层结构：

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

1. 编码类型（encoding）：整数集合根据存储的整数范围选择不同的编码类型。 Redis支持三种编码类型：int16、int32和int64，分别用于存储16位、32位和64位整数。编码类型决定了整数在集合中的存储形式和占用的内存大小。默认是int16
2. 长度（length）：集合包含的元素数量
3. 数组（contents）：整数集合的主要部分是一个整数数组，用于存储整数值。数组中的每个元素都是一个整数，并且按照升序排列。 需要注意的是虽然 contents 数组声明为 int8_t 类型，但是实际上 contents 数组并不保存任何 int8_t 类型的值，其真正类型有 encoding 来决定。

整数集合的特点如下：

1. 紧凑存储：整数集合通过选择合适的编码类型和有序数组的方式，实现了紧凑的存储。 相比于使用普通的动态数组，整数集合可以节省一定的内存空间。
2. 按值升级：当插入一个无法存储在当前编码类型中的整数时，整数集合会自动进行升级操作。 升级操作将整数集合从一个较小的编码类型升级到一个更大的编码类型，并将已有的整数重新编码。这样可以保证整数集合能够容纳更大范围的整数。 整数集合不支持降级操作，一旦对数组进行了升级，编码就会一直保持升级后的状态。

我正在参与2023腾讯技术创作特训营第二期有奖征文，瓜分万元奖池和键盘手表