回顾 Redis 底层的几种基本数据结构。

简单动态字符串（Simple Dynamic String, SDS）

Redis 自己封装的一种字符串操作抽象类型，能实现快捷的字符串修改和节省空间。

应用范围：所有涉及到字符串修改的操作，如：string、key、AOF 等

结构

struct sdshdr {
  
  // 记录字符串长度，让查询字符串长度的时间复杂度为 O(1)
  int len;
  // 记录数组中未使用字节的数量
  // 确保在操作时很容易就能检测到缓冲区溢出的情况
  int free;
  // char 类型的字节数组，用于保存字符串
  // 减少内存再分配的次数，减少系统调用，增加性能
  char buf[];
  
}

SDS 遵循 C 的字符串规范，结尾的\0不会被算进总长度中。

注意，len + free不等于总的长度，因为free在记录空闲长度时，不会记录\0。

SDS 空间拓展规则

1. SDS 在更新字符串时发现空间不足时，会进行一次扩容
2. 如果 buf 数组中，字符串长度小于 1MB 时，在执行空间拓展时，会分配与字符串长度相同的空间，即，在分配完成后，字符串的长度为：len + free + 1 = len * 2 + 1
3. 如果 buf 数组中，字符串长度大于等于 1MB 时，在执行空间拓展时，会分配 1MB 的空间，即，在分配完成后，字符串的长度为：len + free + 1 = len + 1MB + 1

空间惰性释放

在删除字符串中的字符时，SDS 不会立即进行内存重分配。

与此同时，SDS 也提供了相应的 API，可以让我们在有需要时释放空间。

二进制存储

所有的SDS API 都以二进制的形式来存储数据，因此，SDS 字符串能保存一系列二进制数据。

链表（List）

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;

特点

双向链表、无环、头尾指针、记录长度、值多态

字典（Dictionary）

使用 Hash 表作为底层实现的字典。

应用范围：数据库、hash、set 等