一、前言

我们都知道Redis是用C语言实现的，但是C 本身并没有内置高级数据结构
如：String（字符串），List（链表），Set（集合），Hash（哈希表） ， Zset（有序集合），Stream（流）等
所以，Redis 必须自己从零设计一套高度定制化的数据结构，满足其作为高性能内存数据库的独特需求。

二、SDS数据结构

1、SDS简介

SDS（Simple Dynamic String，简单动态字符串） 是 Redis 自主实现的一种高效、安全、二进制友好的动态字符串结构，用于替代 C 语言原生的 char* 字符串。

2、为什么需要SDS

C语言并没有字符串结构，而是通过字符数组来间接的表示字符串，对应的存储结果，如下：

C 语言中的字符串本质是 以 \0（空字符）结尾的字符数组，这种设计存在严重问题：

问题	说明
🔴 获取长度需 O(n)	必须遍历到\0才知道长度（strlen()）越长越慢
🔴 二进制不安全	如果数据中间有 \0，会被截断，被误认为字符串结束 （无法存图片、加密数据等）
🔴 缓冲区溢出风险高	strcat(dest, src) 不检查dest空间是否够大，极易导致内存越界
🔴 修改效率低	无法预分配空间 ，每次拼接都可能触发 realloc（重新分配内存）
🔴 内存浪费或碎片	没有统一管理，频繁分配小字符串导致碎片

为了解决这些问题，Redis 设计了 SDS，它是一个带有元数据头的结构，支持：

SDS 优点
✅ 获取长度O(1) ： 通过 len 字段直接记录当前字符串长度，无需遍历
✅ 二进制安全： 字符串内容由len决定，可包含任意字节（包括 \0），适用于任意二进制数据
✅ 杜绝缓冲区溢出： 所有修改操作（如 sdscat）都会先检查 alloc 是否足够，不足则自动扩容后再写入
✅ 高效修改 + 空间预分配： 采用“预分配冗余空间”策略（<1MB 时翻倍，≥1MB 时 +1MB），大幅减少 realloc 次数
✅ 惰性空间释放 + 多种 header 优化内存：    1、缩短字符串时不立即释放内存（仅更新 len），后续可复用    2、根据字符串长度自动选择 sdshdr 5/8/16/32/64，最小化结构体开销

3、SDS 的结构

Redis 使用了多种 SDS 类型来优化内存使用，根据字符串长度选择不同 header
flags 字段用于标识当前 SDS 使用的是哪种头部结构（header type），它决定了 len 和 alloc 字段的大小（从而支持不同长度的字符串），是 SDS 实现“空间效率自适应”的关键。

#define SDS_TYPE_5  0    // 0b000  SDS_TYPE_5 在 Redis 6.0+ 中已被弃用（因设计缺陷）
#define SDS_TYPE_8  1    // 0b001
#define SDS_TYPE_16 2    // 0b010
#define SDS_TYPE_32 3    // 0b011
#define SDS_TYPE_64 4    // 0b100

SDS 的 flags 类型（定义在 sds.h 中）

// Redis源码中的 sds.h 文件
/*
已弃用：设计缺陷，没有独立的 len 和 alloc 字段！Redis 6.0 已移除
*/
struct __attribute__((__packed__)) sdshdr5 {
    unsigned char flags; // 高5位存 alloc，低3位存 type（固定为0）
    char buf[];
};
/*
 sdshdr8：用于存储长度在 32 ~ 255 字节之间的字符串。
 len 和 alloc 使用 uint8_t（1字节），最多表示 255。
 当字符串长度 >= 32 且 <= 255 时，Redis 自动选用此结构以节省内存。
*/
struct __attribute__ ((__packed__)) sdshdr8 {
    uint8_t len;         /* 已使用字节数（字符串实际长度） */
    uint8_t alloc;       /* 已分配的总容量（不包括头部和结尾的空字符 \0） */
    unsigned char flags; /* 低3位表示SDS类型（此处为SDS_TYPE_8），高5位保留未用 */
    char buf[];          /* 柔性数组，用于存储实际的字符串内容（末尾自动加 \0） */
};

/*
 sdshdr16：用于存储长度在 256 ~ 65535 字节（即 64KB - 1）之间的字符串。
 len 和 alloc 使用 uint16_t（2字节），适用于中等大小的字符串。
 当字符串长度 >= 256 且 <= 65535 时使用。
*/
struct __attribute__ ((__packed__)) sdshdr16 {
    uint16_t len;        /* 已使用字节数（字符串实际长度） */
    uint16_t alloc;      /* 已分配的总容量（不包括头部和结尾的空字符 \0） */
    unsigned char flags; /* 低3位表示SDS类型（此处为SDS_TYPE_16），高5位保留未用 */
    char buf[];          /* 柔性数组，用于存储实际的字符串内容（末尾自动加 \0） */
};

/*
 sdshdr32：用于存储长度在 65536 ~ 4,294,967,295 字节（约 4GB）之间的字符串。
 len 和 alloc 使用 uint32_t（4字节），适用于大字符串（如大JSON、序列化对象等）。
 在 32 位或 64 位系统上，只要字符串不超过 4GB，通常优先使用此结构。
*/ 
struct __attribute__ ((__packed__)) sdshdr32 {
    uint32_t len;        /* 已使用字节数（字符串实际长度） */
    uint32_t alloc;      /* 已分配的总容量（不包括头部和结尾的空字符 \0） */
    unsigned char flags; /* 低3位表示SDS类型（此处为SDS_TYPE_32），高5位保留未用 */
    char buf[];          /* 柔性数组，用于存储实际的字符串内容（末尾自动加 \0） */
};

/*
 sdshdr64：用于存储长度超过 4GB 的超大字符串（极少见，生产环境几乎不用）。
 len 和 alloc 使用 uint64_t（8字节），仅在 64 位系统上可能被使用。
 当字符串长度 > 2^32 - 1（即 > 4,294,967,295 字节）时启用。
*/
struct __attribute__ ((__packed__)) sdshdr64 {
    uint64_t len;        /* 已使用字节数（字符串实际长度） */
    uint64_t alloc;      /* 已分配的总容量（不包括头部和结尾的空字符 \0） */
    unsigned char flags; /* 低3位表示SDS类型（此处为SDS_TYPE_64），高5位保留未用 */
    char buf[];          /* 柔性数组，用于存储实际的字符串内容（末尾自动加 \0） */
};

4、SDS 扩容规则（当需要更多空间时）

当 SDS 的当前分配空间（alloc）不足以容纳新增数据时，系统会自动执行扩容操作：
申请一块更大的内存区域，将原有数据（包括头部元信息和字符串内容）完整复制到新内存，随后释放旧内存，并更新指针使其指向新的地址。

条件	扩容策略	目的
当前字符串长度 < 1MB	新容量 = 2 × 所需总长度（即至少翻倍）	减少小字符串频繁 realloc（重新分配内存），提升性能
当前字符串长度 ≥ 1MB	新容量 = 所需总长度 + 1MB	避免大字符串翻倍导致内存浪费

5、Redis 中 String 类型对象的三种内部编码方式

在 Redis 中，String 类型的值由 redisObject 结构表示，其内部编码（encoding）可以是以下三种之一：

OBJ_ENCODING_INT
OBJ_ENCODING_EMBSTR
OBJ_ENCODING_RAW

这些编码方式决定了 String 值在底层如何存储，而其中两种（EMBSTR 和 RAW）直接与 SDS 相关

1、OBJ_ENCODING_INT

• 适用场景： 当字符串内容可以被解析为一个 64 位有符号整数（例如 “123”、“-456”）时，Redis 会将该值以整数形式直接存储在 redisObject 的 ptr 字段中
• 与 SDS 的关系：不使用 SDS。此时字符串值并未以字符数组形式存在，而是以整数形式内联存储，节省内存并提升操作效率（如 INCR/DECR 可直接对整数运算）

  SET mykey 100   # 编码为 INT
  

2、OBJ_ENCODING_EMBSTR

• 适用场景： 当字符串 不能表示为整数，且 长度 ≤ 44 字节（Redis 7.0+ 为 44 字节；早期版本如 3.2 是 39 字节）时，使用 EMBSTR 编码。

• 与 SDS 的关系：

  • 仍然使用 SDS 存储实际字符串内容。

  • EMBSTR 的内存布局是“一次性写死”的，redisObject 和 SDS 在同一块连续内存中分配（一次 malloc），没有预留额外空间（不像 RAW 的 SDS 会预分配），无法原地扩容

  • 这种设计减少了内存分配次数（只需 malloc 一次），也提高了缓存局部性。

  • EMBSTR 编码的字符串是 只读的：一旦修改（如 append、setrange），会转换为 RAW 编码。

    一次malloc 的意思是：调用 一次 malloc(size) 系统函数，申请一块足够大的连续内存

• SDS 类型： 通常使用 sdshdr8（因为长度 ≤ 44 < 255）

  SET mykey "hello world"   # 长度 11 → 编码为 EMBSTR
  

3、OBJ_ENCODING_RAW

• 适用场景： 当字符串 不能表示为整数，且 长度 > 44 字节 时，使用 RAW 编码。

• 与 SDS 的关系：

  • 使用标准的 SDS 结构存储字符串。
  • redisObject 和 SDS 分别进行内存分配（两次 malloc）：redisObject 的 ptr 指向独立的 SDS 对象。
  • 支持动态修改（如追加、截断等），SDS 会自动扩容或缩容。

• SDS 类型： 根据长度选择 sdshdr8、sdshdr16、sdshdr32 或 sdshdr64。

  SET mykey "a very long string that exceeds forty-four bytes in length"  # 编码为 RAW
  

  编码方式总结

  编码方式	是否使用 SDS	说明
  OBJ_ENCODING_INT	❌ 不使用	直接将整数值嵌入指针，无字符串存储
  OBJ_ENCODING_EMBSTR	✅ 使用 SDS	使用 SDS，但 redisObject 与 SDS 连续分配（只读优化）
  OBJ_ENCODING_RAW	✅ 使用 SDS	使用标准 SDS，redisObject 与 SDS 分开分配（可变）

  综上，EMBSTR 和 RAW 都基于 SDS 实现字符串存储，区别在于内存布局和分配策略；而 INT 完全绕过 SDS，以整数形式高效存储数值型字符串

三、哈希表

1、哈希表的定义与本质

Redis 中的 dict 就是 Redis 自己实现的哈希表，是其底层非常核心的数据结构之一。
哈希表（Hash Table）是一个笼统的、抽象的数据结构概念，而不是某一种具体的实现。理解这一点，是厘清 Redis 中 dict 与"哈希"关系的关键。
换句话说：Redis 的 dict = 哈希表的 C 语言实现。

哈希表（Hash Table）的本质就是一种字典（Dictionary）结构。
哈希表通过 哈希函数（hash function） 将 key 映射到数组的某个索引位置，从而实现 平均 O(1) 时间复杂度 的查找、插入和删除。

2、哈希表的数据结构结构

在 Redis 中，dict 是一个核心的底层数据结构，本质上是一个高性能的哈希表（Hash Table），被广泛用于实现多种关键功能：

键空间（Keyspace）管理： 每个 Redis 数据库（redisDb）通过 dict 维护其所有键值对的映射；
哈希类型（Hash）： 当 Hash 对象较大时，底层编码切换为 hashtable，即基于 dict 实现；
集合类型（Set）： Set 的底层直接使用 dict，其中键表示集合元素，值设为 NULL；
有序集合（ZSet）： ZSet 内部结合了 dict 与跳跃表（SkipList），其中 dict 用于提供 O(1) 时间复杂度的成员分数查询。

dict 不仅定义了键值映射的逻辑结构，还内建了一套完整的生命周期管理机制，由其内部的哈希表管理器负责：
创建与初始化
动态扩容与缩容
高效的查找、插入与删除操作
支持渐进式 rehash，在保证高并发性能的同时平滑完成哈希表的结构调整

在 Redis 源码（dict.h）中，dict 主要由以下几个结构体组成：

//1. dict：Redis 的字典顶层结构，内部包含两个 dictht （可以理解它为哈希表的管理器，也笼统的叫它哈希表）
//  只负责管理生命周期、rehash 状态、函数指针等，不存业务数据
typedef struct dict {
    dictType *type;         // 类型特定函数指针（如 hash 函数、key/value 复制/释放等）
    void *privdata;         // 私有数据，传递给 type 中的函数
    dictht ht[2];           // 两个哈希表，用于渐进式 rehash。ht[0]: 主哈希表（正常时使用），ht[1] 在 rehash（扩容/缩容） 时使用
    long rehashidx;         // rehash 状态：-1 表示未在 rehash，否则表示当前 rehash 到哪个索引
    int16_t pauserehash;    // 是否暂停 rehash（Redis 7.0+）
} dict;

// 2. dictht：表示一个真正的哈希表（hash table）
//   只保存元信息（size, used）和桶数组指针（table），本身不存 key/value
typedef struct dictht {
    dictEntry **table;         // 指针数组，也称哈希桶数组：每个元素是一个指向 dictEntry 链表的指针
    unsigned long size;        // 桶的数量（总是 2^n）
    unsigned long sizemask;    // 掩码 = size - 1
    unsigned long used;        // 当前存储的键值对数量
} dictht;

//3. dictEntry： 表示哈希表中的节点（键值对）
//  存储键值对的最小单元，通过 next 指针形成链表
typedef struct dictEntry {
    void *key;                  // 键：（指针类型：指向键的指针，可指向任意类型的 key）
    union {
        void *val;              // 通用指针，用于存储任意类型的值
        uint64_t u64;           // 可直接存储 64 位无符号整数（节省内存分配）
        int64_t s64;            // 可直接存储 64 位有符号整数
        double d;               // 可直接存储浮点数
    } v;                        // 值（联合体，节省空间）
    struct dictEntry *next;     // 指向下一个 dictEntry，用于解决哈希冲突（链地址法）
} dictEntry;

ht[0] 是正常使用的哈希表。
ht[1] 在 rehash（扩容/缩容） 时使用。
rehashidx 表示当前正在（或下一个将要）处理的桶的索引
ht[rehashindx] 标记 rehash 进度。
假设 rehashindex =3 则表示 索引 0、1、2 的桶（bucket）已经从 ht[0] 迁移到了 ht[1]，下一个要迁移的是 ht[0] 中索引为 3 的桶

2、为什么 Redis 哈希表查询平均是 O(1)？

Redis 哈希表之所以在平均情况下能实现 O(1) 的查询性能，关键在于其精巧的负载控制机制和高效的内存访问方式。

具体来说，Redis 会监控哈希表的负载因子（即：数据总条数 ÷ 桶的数量）。一旦该比值 大于等于 1，系统就会触发扩容操作。这意味着，在绝大多数正常运行状态下，每个桶平均只存储一条数据。

当执行查询时，Redis 首先通过高效的哈希函数快速计算出目标键（key）对应的桶索引（index），几乎一步就能定位到目标位置。即便因哈希冲突导致某个桶中存放了多条数据（以链表形式组织），由于链表长度极短（通常只有 1~2 个节点），通过指针遍历比对也仅需纳秒级的时间开销。

因此，在合理设计和自动扩容机制的保障下，Redis 哈希表的查询操作在平均意义上接近常数时间复杂度——即 O(1)。

3、什么是哈希冲突？

举个通俗的例子：

• 假设 Redis 的底层哈希表有 8 个“格子”（即哈希桶，索引为 0~7）。

• 使用一个哈希函数 h(key) = key.hashCode() % 8 来决定每个 key 存放在哪个格子。

• 如果两个不同的 key，比如 "user:1001" 和 "product:2002"，经过计算后都得到 h(key) = 3，那么它们都想放进第 3 号格子 —— 这就发生了 哈希冲突。

  只要 key 的数量超过哈希表的容量，就必然会出现冲突， 哈希冲突是正常现象 。

4、Redis如何解决哈希冲突

1、✅ Redis 默认采用 链地址法

• 每个哈希桶（bucket）维护一个链表（或更准确地说，是一个 dictEntry链）。

• 所有哈希值相同的 key，会以链表形式挂在这个桶上。

• 插入时用“头插法”提高效率；查找时遍历链表比对 key。

  但链表过长会影响性能（O(n) 查找），所有元素挤在一个链表里 → 退化成单链表 → O(n)
  每个桶平均 100 个元素 → 查找要遍历 100 次。所以 Redis 还引入了渐进式 rehash

2、✅ 渐进式 rehash

• 当哈希表负载因子（used / size）过高（默认 > 1）时，Redis 会启动扩容。
• 创建一个新哈希表ht[1]（通常是原大小的 2 倍）。
• 分多次、在每次操作时迁移一部分数据，避免一次性 rehash 导致服务卡顿。
• 迁移期间，读写操作会同时查两个表，保证数据一致性。

5、底层数据结构

四、压缩列表 ziplist

1、定义与本质

• 跳表是一种概率性数据结构，用于在有序链表的基础上加速查找。其核心思想是通过多层索引来跳过部分元素，从而将查找、插入、删除的时间复杂度从 O(n) 降低到 平均 O(log n)。

• ziplist 是一种紧凑的、连续内存的、用于存储可变长度元素的序列化数据结构，其每个元素自带长度和类型信息，支持双端操作，但不支持 O(1) 随机访问。

2、它与传统数组的相似之处（为什么有人会说它是“数组”）

• 连续内存布局
  ziplist 的所有数据（header + entries + end marker）都存储在 一块连续的内存区域 中，这点和 C 语言中的数组类似。

• 通过偏移量访问
  Redis 利用 zltail（尾部偏移）等字段，像“索引”一样快速定位 entry，类似于数组通过下标计算地址。

• 顺序存储
  元素按插入顺序线性排列，支持从前向后或从后向前遍历 —— 类似数组的顺序访问。
  所以，在 “紧凑、连续、顺序” 这些语义上，把它类比为“特殊数组”是可以帮助初学者理解的。

  ❌ 关键区别（为什么它不是传统意义上的数组）

  特性	传统数组（如 C 数组）	Redis ziplist
  元素大小	所有元素 固定长度（如 int[10] 每个 4 字节）	每个 entry 可变长度（prevlen + encoding + data 长度不一）
  随机访问	O(1)：arr[i] 直接计算地址	O(N)：必须从头或尾逐个解析 entry 才能找到第 i 个
  内存结构	纯数据，无元信息	每个 entry 自带 长度和编码信息（metadata）
  插入/删除	固定大小，通常不支持动态增删	支持动态增删，但可能触发 连锁更新（cascade update）

  最核心的区别：ziplist 是一个“自描述的、可变长元素的序列”，而数组是“同构、定长元素的集合”。

3、ziplist 的问题：

• 连锁更新： 当一个 entry 被修改导致长度变化时，可能需要连续更新后续所有 entry 的 prevlen 字段。
• 解析开销大： 从后往前遍历时效率低（因为每个 entry 只记录前一个 entry 的长度，不记录自身长度，不利于快速随机访问或追加操作）。
• 内存对齐不友好： 结构紧凑但不利于现代 CPU 的缓存优化。
• 扩展性差： 难以支持更复杂的编码需求（如带类型标签的元素）

4、prevlen存在的意义是什么？

prevlen 的核心作用：实现反向遍历
ziplist 是一块连续内存，没有指针。要实现类似双向链表的功能（如 LPOP、ZRANGE … REV），必须能在任意 entry 处快速找到前一个 entry 的起始地址。

✅ 有了 prevlen：

• 假设当前 entry 起始地址是 p；
• 读取 p 处的 prevlen 值（比如是 12）；
• 那么前一个 entry 的起始地址就是 p - 12；
• 从而实现 O(1) 时间复杂度的反向跳转。

❌ 假设没有 prevlen：
在 ziplist（以及 listpack）中，从前往后遍历时，确实可以通过解析 encoding 字段，推断出：

• data 的长度；

• encoding 字段自身占多少字节（1~5 字节，取决于字符串/整数类型）；

• 再加上 prevlen 字段的长度（1 或 5 字节，需先读第一个字节判断）；
  → 于是可以算出 当前 entry 的总字节数，从而跳到下一个 entry。

  所以：前向遍历不需要 prevlen 的值，只需要知道它占多少字节即可。❌ 但关键问题在于：反向遍历
  🚫 问题：内存是线性布局，没有“指向前一个”的信息

假设你在某个 entry 的起始位置 p，你想找到前一个 entry 的起始位置。

• 你知道当前 entry 的结构：[prevlen][encoding][data]
• 但你不知道前一个 entry 有多长，除非你从头开始遍历（O(n)
• 要么当前 entry 显式告诉你前一个 entry 的长度。

👉 这正是 prevlen 字段存在的意义！

5、底层数据结构

五、压缩列表 listpack

1、定义

• Redis 的 listpack 是一种紧凑、高效的底层数据结构，用于替代早期的 ziplist（压缩列表），主要目的是解决 ziplist 在某些场景下的性能和内存问题。
• 它从 Redis 7.0 开始正式成为 Redis 内部某些数据类型（如 ：Stream 和部分 Hash / List / ZSet 的小对象编码）的底层编码方式之一

2、数据结构

六、跳表 SkipList

1、定义

• Redis 中的 跳表（Skip List） 是一种用于实现有序集合（Sorted Set，即 ZSET）的数据结构。
  最底层（Level 0）是一个有序的双向链表，在链表的基础上，增加了多级索引，通过多级索引位置的转跳，实现了快速查找元素
• 跳表： 主要用于实现 有序集合（Sorted Set, ZSET），支持按分数（score）排序和范围查询。

2、应用场景

• 1、需要 排序 的场景（如排行榜、优先级队列）

• 2、频繁 范围查询（如“分数在 80~100 之间的用户”）

• 3、需要 按排名访问（如“Top 10”）

  跳表： 查找指定成员 member 需要 O(log N)，不如哈希表快；无法 O(1) 判断 member 是否存在

3、跳表的数据结构

typedef struct zskiplist {
	struct zskiplistNode *header, *tail;
	unsigned long length;   // 节点数量
	int level;              // 当前最大层数
} zskiplist;

typedef struct zskiplistNode {
	sds ele;                // 成员对象（字符串）
	double score;           // 分值
	struct zskiplistNode *backward; // 后退指针（仅指向前一个节点）
	struct zskiplistLevel {
    	struct zskiplistNode *forward; // 前进指针
    	unsigned long span;            // 到 forward 节点的跨度
	} level[];              // 层级数组（柔性数组）
} zskiplistNode;

七、双向链表 Quicklist

1、定义与本质

Redis Quicklist 用于实现 List（列表）类型。它是对早期版本中使用的 ziplist（压缩列表） 和 linkedlist（双向链表） 的优化与融合，
Redis Quicklist —— 本质上是一个 由 ziplist 组成的双向链表。

2、数据结构

typedef struct quicklist {
    quicklistNode *head;        // 头节点
    quicklistNode *tail;        // 尾节点
    unsigned long count;        // 所有 ziplist 中元素总数
    unsigned int len;           // quicklistNode 节点数量
    signed int fill : 16;       // 每个 ziplist 的填充因子（可配置）
    unsigned int compress : 16; // LZF 压缩深度（0 表示不压缩）
    ...
} quicklist;

typedef struct quicklistNode {
    struct quicklistNode *prev;
    struct quicklistNode *next;
    unsigned char *zl;          // 指向一个 ziplist
    size_t sz;                  // ziplist 的字节大小
    unsigned int count : 16;    // ziplist 中的元素个数
    unsigned int encoding : 2;  // 编码方式：RAW 或 LZF 压缩
    ...
} quicklistNode;

✅关键特点：

• 每个节点是一个 ziplist，而不是单个元素。
• 整体是 双向链表，支持 O(1) 的头尾插入/删除。
• 中间操作（如 index 访问）通过遍历节点 + 在 ziplist 内部查找实现。
• 支持 LZF 压缩（可选），进一步节省内存。

✅优势：
✅ 内存友好：多个小元素打包进 ziplist，减少 malloc 开销

✅ 性能均衡：头尾操作快，中间操作可接受

✅ 可配置：通过参数平衡内存与性能

✅ 支持压缩：进一步降低内存占用（适用于冷数据）

3、Listpack 分割策略：

在Quicklist基本结构上，高效的核心是避免每个Listpack的元素过多或过少。
避免元素过多的方法： 配置阈值
控制节点负载因子超过阈值时触发拆分 list-node-auto-split-threshold（默认 0.75），使得Listpack元素数量不能超过阈值或者Listpack占用的空间不能超过阈值。
如果超过阈值则分割成两个Listpack。
避免元素过少的方法： 在合适的时机进行Listpack合并。