# Redis数据结构原理
Redis是一个高性能的内存数据库，其高性能的一个重要原因是它采用了高效的数据结构。本文将深入探讨Redis内部使用的数据结构及其实现原理。
## 1. 简单动态字符串（SDS）
Redis使用简单动态字符串（Simple Dynamic String，SDS）作为字符串的基本表示。
### 结构定义
“`c
typedef struct sdshdr {
int len; // 已使用的字节数
int free; // 未使用的字节数
char buf[]; // 字节数组，存储字符串
} sdshdr;
“`
### 特点
– **长度计算**：O(1)时间复杂度，直接通过len字段获取
– **空间预分配**：当字符串增长时，会预分配额外的空间，减少内存分配次数
– **惰性空间释放**：当字符串缩短时，不会立即释放空间，而是通过free字段记录，供后续使用
– **二进制安全**：可以存储任意二进制数据，包括空字符
### 应用场景
– 存储字符串值
– 作为List、Hash等数据类型的元素
## 2. 字典（Dict）
字典是Redis中使用最广泛的数据结构之一，用于实现Hash、Set等数据类型。
### 结构定义
“`c
typedef struct dict {
dictType *type; // 类型特定函数
void *privdata; // 私有数据
dictht ht[2]; // 哈希表，用于渐进式rehash
long rehashidx; // rehash索引，-1表示未进行rehash
unsigned long iterators; // 当前正在使用的迭代器数量
} dict;
typedef struct dictht {
dictEntry **table; // 哈希表数组
unsigned long size; // 哈希表大小
unsigned long sizemask; // 掩码，用于计算索引
unsigned long used; // 已使用的槽位数
} dictht;
typedef struct dictEntry {
void *key; // 键
union {
void *val; // 值
uint64_t u64; // 64位无符号整数
int64_t s64; // 64位有符号整数
double d; // 双精度浮点数
} v; // 值的不同表示
struct dictEntry *next; // 指向下一个哈希表节点，用于解决哈希冲突
} dictEntry;
“`
### 特点
– **哈希冲突处理**：使用链地址法，通过链表解决哈希冲突
– **渐进式rehash**：为了避免rehash过程中阻塞主线程，Redis采用渐进式rehash策略
– **扩容策略**：当哈希表的负载因子（used/size）大于1时，会触发扩容
– **缩容策略**：当哈希表的负载因子小于0.1时，会触发缩容
### 应用场景
– 实现Hash数据类型
– 实现Set数据类型（当元素为字符串时）
– 存储Redis的键值对
## 3. 跳跃表（Skip List）
跳跃表是Redis中用于实现Sorted Set的核心数据结构。
### 结构定义
“`c
typedef struct zskiplistNode {
robj *obj; // 成员对象
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;
“`
### 特点
– **多层索引**：通过多层索引结构，提高查找效率
– **平均时间复杂度**：O(log n)，接近平衡树的性能
– **插入和删除操作**：时间复杂度O(log n)，且实现简单
– **空间复杂度**：O(n)，比平衡树更节省空间
### 应用场景
– 实现Sorted Set数据类型
– 用于范围查询
## 4. 整数集合（IntSet）
整数集合是Redis中用于存储整数的特殊数据结构，当Set中的元素都是整数时使用。
### 结构定义
“`c
typedef struct intset {
uint32_t encoding; // 编码方式：INTSET_ENC_INT16、INTSET_ENC_INT32、INTSET_ENC_INT64
uint32_t length; // 元素数量
int8_t contents[]; // 存储元素的数组
} intset;
“`
### 特点
– **紧凑存储**：根据元素的大小自动选择合适的编码方式
– **有序存储**：元素按升序存储，便于二分查找
– **动态扩容**：当需要存储更大的整数时，会自动升级编码方式
### 应用场景
– 存储整数集合
– 当Set中的元素都是整数时使用
## 5. 压缩列表（Ziplist）
压缩列表是Redis中用于存储小数据的紧凑数据结构，用于List、Hash、Sorted Set等数据类型的底层实现。
### 结构定义
“`
“`
– `zlbytes`：压缩列表的总字节数
– `zltail`：压缩列表尾部元素的偏移量
– `zllen`：压缩列表中的元素个数
– `entry`：压缩列表中的元素
– `zlend`：压缩列表的结束标记
### 特点
– **紧凑存储**：节省内存空间
– **连续内存**：元素存储在连续的内存区域
– **支持多种数据类型**：可以存储字符串和整数
– **查找时间复杂度**：O(n)，适用于小数据量
### 应用场景
– 实现List数据类型（当列表较小时）
– 实现Hash数据类型（当哈希表较小且字段值较小时）
– 实现Sorted Set数据类型（当有序集合较小且元素值较小时）
## 6. 快速列表（Quicklist）
快速列表是Redis 3.2引入的新数据结构，用于优化List的存储。
### 结构定义
“`c
typedef struct quicklist {
quicklistNode *head; // 头节点
quicklistNode *tail; // 尾节点
unsigned long count; // 元素总数
unsigned int len; // 节点数量
int fill : QL_FILL_BITS; // 每个节点的最大元素数
unsigned int compress : QL_COMP_BITS; // 压缩深度
} quicklist;
typedef struct quicklistNode {
struct quicklistNode *prev; // 前一个节点
struct quicklistNode *next; // 后一个节点
unsigned char *zl; // 压缩列表
unsigned int sz; // 压缩列表的大小
unsigned int count : 16; // 压缩列表中的元素个数
unsigned int encoding : 2; // 编码方式：RAW或LZF
unsigned int container : 2; // 容器类型：NONE或ZIPLIST
unsigned int recompress : 1; // 是否需要重新压缩
unsigned int attempted_compress : 1; // 尝试压缩的次数
unsigned int extra : 10; // 额外字段
} quicklistNode;
“`
### 特点
– **结合了链表和压缩列表的优点**：链表便于修改，压缩列表节省空间
– **可配置的压缩深度**：可以根据需要压缩中间节点，节省内存
– **灵活的节点大小**：可以根据配置调整每个节点的大小
### 应用场景
– 实现List数据类型
## 7. 流（Stream）
流是Redis 5.0引入的新数据结构，用于处理消息流。
### 结构定义
“`c
typedef struct stream {
unsigned char *last_id; // 最后一条消息的ID
uint64_t length; // 消息数量
rax *rax; // 存储消息的基数树
rax *cgroups; // 消费组信息
} stream;
“`
### 特点
– **消息持久化**：消息存储在磁盘上，支持持久化
– **消费组**：支持多个消费组，每个消费组有独立的消费位置
– **消息ID**：每条消息有唯一的ID，格式为时间戳-序列号
– **范围查询**：支持按消息ID范围查询
### 应用场景
– 消息队列
– 事件流处理
– 日志收集
## 8. 总结
Redis采用了多种高效的数据结构，每种数据结构都有其特定的应用场景：
| 数据结构 | 应用场景 | 时间复杂度 |
|———|———|———–|
| SDS | 字符串存储 | O(1) |
| 字典 | Hash、Set | O(1) |
| 跳跃表 | Sorted Set | O(log n) |
| 整数集合 | 整数集合 | O(log n) |
| 压缩列表 | 小数据存储 | O(n) |
| 快速列表 | List | O(n) |
| 流 | 消息流处理 | O(log n) |
这些数据结构的组合使用，使得Redis在保证性能的同时，也能适应各种不同的应用场景。了解这些数据结构的原理，对于理解Redis的工作机制和优化Redis应用都有很大帮助。
