数据结构

本文同时涉及用户可见的数据类型和 Redis 内部编码。内部实现会随版本变化，不能把某一版本的源码结构当成固定 API；可使用 OBJECT ENCODING key 查看 key 当前采用的内部编码。

字符串

Redis 使用 SDS（Simple Dynamic String）表示字符串，而不是直接使用以 \0 结尾的 C 字符串。SDS 会记录已使用长度、已分配空间和类型标识。

主要特点：

获取字符串长度的时间复杂度为 O(1)。
二进制安全，可以保存文本、序列化对象、图片等字节数据。
扩容时会预分配空间，减少频繁申请和复制内存的次数。
不同长度的字符串使用不同宽度的头部结构，以减少额外内存开销。

链表

下面的双向链表是 Redis 的通用内部结构之一。需要注意：现代 Redis 的 List 数据类型主要使用 quicklist，其节点内部通常使用 listpack，不能简单理解为“一个元素对应一个链表节点”。

数据结构

// 链表节点定义
typedef struct listNode {
    struct listNode * prev; 
    struct listNode * next;
    
    void * value; //节点数值
} listNode;

// 链表定义
typedef struct list {
    listNode * head; // 链表头
    listNode * tail; // 链表尾
    
    unsigned long len; // 长度
    
    void *(*dup) (void *ptr); // 节点值复制函数
    void (*free) (void *ptr); // 截止释放函数
    void (*match) (void *ptr, void *key); // 节点值对比函数
}

常见 API
1. lpush
2. rpush
3. lpop
4. rpop
5. llen
6. lrange

哈希表

哈希表是一种存储数据的结构。在哈希表中，键和值是一一对应的关系，一个键key对应一个值value。哈希表这个数据结构可以通过键key，在o(1)时间复杂度的情况下获得对应的值。
由于C语言自己没有内置哈希表这一数据结构，因此Redis自己实现了Hash表。
Redis 的哈希表基于拉链法实现

数据结构
1. 哈希表大小通常为 2 的幂，sizemask = size - 1，可通过 hash & sizemask 快速计算数组索引。

// hash表
typedef struct dictht {
    dictEntry **table;      // 哈希表数组
    unsigned long size;     // Hash 表大小 2的幂次方
    unsigned long sizemask; // 哈希表掩码
    unsigned long used;     // Hash 表使用的大小 包括拉链表上的
} dictht;
// 节点结构
typedef struct dictEntry {
    void *key;
    union {
        void *val;
        uint64_t u64;
        int64_t i64;
        double d;
    } v;
    struct dictEntry *next;
} dictEntry;

// 
typedef struct dict {
    dictType *type;
    void *privdata;
    dictht ht[2];  // 当表需要扩容时，0是老表 1是新表
    long rehashidx; // 未进行 rehash 时值为 -1
} dict;

rehash：used / size 是负载因子。负载因子增大时哈希冲突通常会增加，Redis 会渐进式地将旧表中的数据迁移到新表，避免一次性迁移长时间阻塞主线程
1. 分配空间给ht[1]。分配空间由ht[0]的具体参数决定。
2. 将ht[0]存储的键值对，重新计算hash值和索引值，并赋值到ht[1]的对应位置中。
3. 当赋值完成后，释放ht[0]所占用空间，并把ht[0]指向ht[1]目前的地址。
4. ht[1]指向空表。
什么时候 rehash
1. Redis 没有执行后台备份时，当负载因子大于等于 1 就执行。（此时 CPU 相对空闲。）
2. Redis 正在执行后台备份时，当负载因子大于等于 5 才执行。（避免同时进行 rehash 和备份带来过高负载。）

集合

普通集合

Set 保证成员唯一。其内部编码可能是整数集合、哈希表或 listpack，具体取决于 Redis 版本、元素类型和集合规模。

整数集合

数据结构

typedef struct intset {
    uint32_t encoding;  // 编码 int16_t int32_t int64_t
    uint32_t length;    // 集合长度
    int8_t contents[];  // 元素数组
}

操作
1. 对于修改，intset保持其一段空间有序。由于intset占用段连续内存，所以每次修改数据需要重新申请空间，比如增加就是扩容，删除就是缩容
2. 对于查找，由于 intset 中的数据有序，因此可以执行二分查找算法。

有序集合

跳表

命令
1. zadd
2. zcard
3. zrank
4. zcount
5. zrangebyscore
6. zrem
7. zscore

数据结构 ​

字符串 ​

链表 ​

哈希表 ​

集合 ​

普通集合 ​

整数集合 ​

有序集合 ​

数据结构

字符串

链表

哈希表

集合

普通集合

整数集合

有序集合