Redis核心数据结构深度解析与底层实现
Redis数据结构设计哲学
Redis的数据模型超越了传统键值存储，通过为不同场景定制优化的数据类型，实现了内存效率与操作性能的平衡。其核心设计遵循三大原则：
- 空间优先：小数据量时采用紧凑结构（如压缩列表、整数集合）降低内存开销；
- 时间高效：大数据场景自动切换至哈希表、跳表等结构，保障O(1)或O(logN)的操作复杂度；
- 动态适应：支持运行时结构转换，根据数据增长自动升级底层实现。
基础数据类型及其底层机制
字符串（String）—— 二进制安全的动态字符串
Redis未使用C原生字符串，而是构建了SDS（Simple Dynamic String）结构：
struct sdshdr {
size_t len; // 字符串实际长度
size_t alloc; // 已分配内存大小
unsigned char flags; // 类型标识位
char buf[]; // 数据缓冲区
};
该设计带来四大优势：
- 支持二进制数据存储（不依赖'\0'终止符）；
- 预分配冗余空间减少频繁内存重分配；
- 长度信息缓存使strlen操作降至O(1)；
- 兼容C字符串函数接口。
典型应用包括缓存对象序列化数据、原子计数器及基于SETNX的分布式锁实现。
哈希（Hash）—— 渐进式扩容的字段映射
当字段数量不超过512且单个值长度≤64字节时，Redis使用压缩列表（ziplist）以节省内存。超过阈值后转为哈希表（hashtable），实现方式如下：
typedef struct dictEntry {
void *key;
union { void *val; } v;
struct dictEntry *next;
} dictEntry;
typedef struct hashtable {
dictEntry **table;
unsigned long size;
unsigned long used;
} dictht;
这种双阶段策略在小对象场景下可节省近半内存，适用于用户资料、购物车等属性集合存储。
列表（List）—— 分段压缩的双向链表
Redis 3.2+引入快速列表（quicklist）替代原有ziplist实现。它将多个压缩列表节点通过双向指针连接，每个节点包含一个独立的ziplist：
typedef struct quicklistNode {
struct quicklistNode *prev, *next;
unsigned char *zl;
unsigned int sz;
unsigned int count;
} quicklistNode;
此设计规避了单一ziplist的连锁更新问题，同时保持较高内存利用率。配合头尾O(1)插入删除特性，非常适合消息队列和最新动态流场景。
集合（Set）—— 动态编码的整数容器
纯整数集合在元素数≤512时采用整数集合（intset）：
typedef struct intset {
uint32_t encoding; // INT16/INT32/INT64
uint32_t length;
int8_t contents[];
} intset;
contents数组按升序存储整数，支持二分查找（O(logN)）。当插入超出当前编码范围的整数时，触发整体内存重分配并升级编码格式。非整数或超限集合则转为哈希表，值指向null。
有序集合（Sorted Set）—— 双索引排序结构
结合跳跃表（skiplist）与哈希表实现双重索引：
- 跳跃表维护分数排序，支持范围查询（ZRANGEBYSCORE）和排名定位；
- 哈希表提供成员到分数的O(1)映射（ZSCORE命令）。
跳跃表通过多层索引实现平均O(logN)的增删改查，比红黑树更易实现且天然支持区间操作，广泛用于排行榜和延迟任务调度。
高级数据结构应用场景
流（Stream）—— 持久化消息通道
Redis 5.0引入的Stream基于基数树（radix tree）实现，支持消费者组（consumer group）和消息确认机制。每条消息由时间戳-序列号唯一标识，保证全局有序性，适用于订单状态同步和日志聚合等需要可靠传递的场景。
位图（Bitmap）—— 高密度状态标记
复用String类型进行位级操作，每个bit代表一种状态。例如百万用户签到系统仅需约125KB内存。BITCOUNT指令使用SWAR算法高效统计置位数量，适合活跃度分析和布隆过滤器实现。
HyperLogLog —— 基数概率估算
基于随机化算法的去重计数器，误差率约0.81%。每个键固定占用12KB内存，可估算最多2^64个元素的基数。相比精确集合存储，内存消耗降低三个数量级以上，是UV统计的理想选择。
核心结构对比总结
| 数据类型 | 底层实现 | 转换条件 | 主要用途 |
|---|---|---|---|
| String | long/double/SDS | 数值范围决定 | 缓存、计数、锁 |
| Hash | ziplist → hashtable | 字段数>512 或 值长>64B | 对象属性、配置 |
| List | ziplist → quicklist | 元素数>512 或 节点大小超限 | 队列、栈、时间线 |
| Set | intset → hashtable | 含非整数 或 元素数>512 | 去重、交并差运算 |
| Sorted Set | ziplist → skiplist+hashtable | 元素数>128 或 成员/分值过长 | 排行榜、优先级队列 |
关键差异辨析
intset vs ziplist：前者专为有序整数集优化，支持二分查找但插入可能引发全量迁移；后者作为通用紧凑容器，允许任意类型嵌套存储，但遍历复杂度为线性且存在连锁更新风险。
SDS vs C字符串：SDS通过元数据缓存和预分配策略，解决了C字符串长度计算慢、缓冲区溢出和内存重分配频繁三大缺陷，更适合高频修改的缓存场景。
