Redis 数据结构源码剖析（SDS、Dict、Skiplist、Quicklist、Ziplist）

1. 前言

Redis 的高性能与丰富数据结构密切相关。
核心数据结构包括：

• SDS（Simple Dynamic String）：字符串底层实现。
• Dict（哈希表）：Key-Value 映射。
• Skiplist（跳表）：有序集合底层结构。
• Quicklist（快速列表）：List 的底层实现。
• Ziplist / Listpack（压缩列表）：小型集合或 Hash 的紧凑存储。

这些结构各有特点，支持 高效读写、低内存消耗 和 动态扩展。

---

2. SDS（Simple Dynamic String）

2.1 SDS 概念

Redis 字符串不是简单 C 字符数组，而是 SDS，支持 动态扩容、二进制安全、O(1) 获取长度。

2.2 SDS 结构

struct sdshdr {
    int len;      // 已使用长度
    int free;     // 剩余可用空间
    char buf[];   // 字符串内容（实际数据）
};

2.3 特性

• len：快速获取字符串长度，避免 O(n) strlen()。
• free：预留空间，减少扩容次数。
• 二进制安全：可存储 \0。

2.4 核心操作

s = sdsnew("hello");       // 创建
s = sdscat(s, " world");   // 拼接
sdsfree(s);                // 释放

SDS 的扩容采用 指数增长，保证拼接操作的均摊 O(1) 性能。

---

3. Dict（哈希表）

3.1 Dict 概念

Redis 的 Hash 类型、数据库全局 Key-Value 都使用 Dict。

3.2 Dict 结构

typedef struct dictEntry {
    void *key;
    void *val;
    struct dictEntry *next;   // 冲突链表
} dictEntry;

typedef struct dictht {
    dictEntry **table;
    unsigned long size;
    unsigned long sizemask;
    unsigned long used;
} dictht;

typedef struct dict {
    dictht ht[2];   // 支持渐进式 rehash
    long rehashidx;
} dict;

3.3 特性

• 渐进式 rehash：避免大表扩容阻塞主线程。
• 冲突处理：链表法（拉链法）。
• 可定制化：支持自定义 hash 函数与 key/value dup/free 函数。

---

4. Skiplist（跳表）

4.1 Skiplist 概念

跳表是 Redis 有序集合（ZSet） 的底层结构。

• 支持快速 范围查询 和 按分数排序。
• 查找、插入、删除平均 O(log n)。

4.2 Skiplist 结构

typedef struct zskiplistNode {
    sds ele;
    double score;
    struct zskiplistNode *backward;
    struct zskiplistLevel {
        struct zskiplistNode *forward;
        unsigned int span;
    } level[];
} zskiplistNode;

typedef struct zskiplist {
    struct zskiplistNode *header, *tail;
    unsigned long length;
    int level;
} zskiplist;

• score：排序依据。
• forward：多层索引，提高查找效率。
• span：用于计算排名。

---

5. Quicklist（快速列表）

5.1 Quicklist 概念

Redis 3.2 之后，List 类型底层使用 Quicklist 替代双端链表 + ziplist。

5.2 Quicklist 结构

typedef struct quicklistNode {
    struct quicklistNode *prev, *next;
    unsigned char *zl;   // ziplist 存储多个元素
    unsigned int sz;     // ziplist 大小
} quicklistNode;

typedef struct quicklist {
    quicklistNode *head, *tail;
    unsigned long count; // 元素总数
    int fill;            // ziplist fill factor
} quicklist;

5.3 特性

• 每个节点存储多个元素，减少链表节点开销。
• 内置 压缩策略，节省内存。
• 支持双向访问，O(1) 插入/删除。

---

6. Ziplist / Listpack

6.1 Ziplist 概念

• 小型集合、Hash、ZSet 会用 Ziplist 存储。
• 是 连续内存压缩存储，减少内存碎片。

6.2 Ziplist 结构

[zlbytes][zltail][zllen][entry][entry]...[zlend]

• zlbytes：总字节数
• zltail：最后一个元素偏移
• zllen：元素数量
• entry：元素内容，支持整数压缩

6.3 特性

• 对小对象极致节省内存
• 查询效率较低，但适合小规模数据

---

7. 数据结构选择策略

数据类型	小规模	大规模
String	embstr	raw
List	ziplist	quicklist
Hash	ziplist	dict
Set	intset	dict
ZSet	ziplist	skiplist+dict

Redis 会根据 元素个数、元素长度、配置阈值 自动升级底层数据结构。

---

8. 小结

本文分析了 Redis 核心数据结构源码：

1. SDS：高效字符串存储，支持 O(1) 获取长度和动态扩容。
2. Dict：高性能哈希表，支持渐进式 rehash。
3. Skiplist：有序集合底层结构，支持快速排序和范围查询。
4. Quicklist：List 的底层实现，支持压缩和双向访问。
5. Ziplist / Listpack：小型集合压缩存储，节省内存。

📌 理解这些数据结构是 Redis 高性能和内存优化的核心，也是所有命令执行和对象操作的基础。

---

下一篇可以写 Redis 内存优化与管理机制（内存碎片、LRU、惰性删除、内存回收策略），这样 Redis 的内存管理体系就完整了。