Redis底层数据结构？编码与底层数据结构的映射？

Redis底层数据结构

一、简单动态字符串（SDS）
结构：

struct sdshdr {int len;     // 已使用字节长度 int free;    // 未使用字节长度 char buf[];  // 字节数组（兼容C字符串）
};

特点：

1. 二进制安全：支持存储包含空字符（\0）的二进制数据，适用于图片、音频等。
2. 高效长度获取：直接读取len属性，时间复杂度O(1)，而C字符串需遍历O(n)。
3. 内存预分配：扩展时分配额外空间（如新长度+扩展后长度x2），减少频繁内存分配。
4. 惰性释放：缩短字符串时保留未使用空间，避免立即内存回收。

应用场景：所有Redis键和字符串值的底层实现。

二、压缩列表（Ziplist）
结构：
连续内存块，包含：

• zlbytes（总字节数）、zltail（尾节点偏移量）、zllen（元素个数）
• 每个节点存储前驱长度、当前数据类型/长度、实际数据
• zlend标记结尾（0xFF）。

特点：

1. 内存紧凑：无指针开销，适合小规模数据（如哈希、列表元素少时）。
2. 顺序访问：查找中间元素需遍历，时间复杂度O(n)，但头尾操作高效O(1)。

应用场景：小规模哈希（Hash）、列表（List）和有序集合（ZSet）的底层实现。

三、哈希表（Hashtable）
结构：

typedef struct dict {dictEntry table;      // 哈希桶数组 unsigned long size;     // 桶数量 unsigned long sizemask; // 哈希掩码（size-1）unsigned long used;     // 已存元素数量 
} dict;

特点：

1. 链式哈希冲突解决：哈希桶通过链表存储冲突元素。
2. 渐进式Rehash：扩容时逐步迁移数据，避免单次迁移阻塞服务。
3. 动态扩容：当负载因子（used/size）超过阈值（默认1）时，扩容至2倍。

应用场景：大规模哈希（Hash）、集合（Set）的底层实现。

四、跳跃表（Skiplist）
结构：
多层有序链表，节点包含：

• 分值（score）用于排序
• 后退指针（BW）用于逆序访问
• 多层前进指针（L1-Ln）加速范围查询。

特点：

1. 高效范围查询：时间复杂度O(log n)，适合有序集合的区间操作（如ZRANGE）。
2. 动态层数：节点层数基于幂次定律随机生成（1-32层），平衡查询与内存。

应用场景：有序集合（ZSet）的底层实现之一（与哈希表配合）。

五、整数集合（Intset）
结构：

typedef struct intset {uint32_t encoding;  // 编码类型（int16/32/64）uint32_t length;    // 元素数量 int8_t contents[];  // 整数数组 
} intset;

特点：

1. 自动升级编码：插入更大整数时升级数组类型（如int16→int32）。
2. 内存紧凑：仅存储整数，无指针开销。

应用场景：元素均为整数的小规模集合（Set）。

六、快速列表（Quicklist）
结构：
双向链表 + 压缩列表（Ziplist），节点为Ziplist片段。
特点：

1. 平衡内存与性能：大列表拆分为多个Ziplist节点，减少内存碎片。
2. 支持头尾高效操作：双向链表结构支持快速插入/删除。

应用场景：列表（List）的默认底层实现。

七、其他优化结构

1. embstr编码字符串：短字符串（≤44字节）与redisObject连续存储，减少内存分配次数。
2. listpack（替代Ziplist）：新版Redis引入，取消节点间依赖，提升并发安全性。

---

总结：Redis数据结构选择策略

数据类型	可能编码	选择条件（示例）
字符串	int/embstr/raw	整数值/短字符串/长字符串
列表	quicklist	所有列表操作（默认）
哈希	ziplist/hashtable	字段数≤hash-max-ziplist-entries
集合	intset/hashtable	元素全为整数且数量少
有序集合	ziplist/skiplist+dict	元素数≤zset-max-ziplist-entries

编码与底层数据结构的映射

一、字符串对象（OBJ_STRING）

编码方式	底层数据结构	触发条件与特性
OBJ_ENCODING_INT	直接存储整数值	当值为整数且范围在LONG_MIN到LONG_MAX之间时使用，内存占用最小。
OBJ_ENCODING_EMBSTR	紧凑存储的SDS	字符串长度≤44字节（Redis 3.2+）时，redisObject与SDS连续存储，减少内存分配次数。
OBJ_ENCODING_RAW	标准SDS结构	字符串长度>44字节或经过修改的embstr对象，支持动态扩容。

---

二、列表对象（OBJ_LIST）

编码方式	底层数据结构	触发条件与特性
OBJ_ENCODING_QUICKLIST	快速列表（Quicklist）	所有列表的默认实现，由双向链表和多个Ziplist节点组成，平衡内存与操作效率。

---

三、哈希对象（OBJ_HASH）

编码方式	底层数据结构	触发条件与特性
OBJ_ENCODING_ZIPLIST	压缩列表（Ziplist）	当哈希字段数≤hash-max-ziplist-entries（默认512）且所有值长度≤hash-max-ziplist-value（默认64字节）时使用。
OBJ_ENCODING_HT	哈希表（Hashtable）	超出Ziplist阈值时自动转换，支持高效的随机读写操作。

---

四、集合对象（OBJ_SET）

编码方式	底层数据结构	触发条件与特性
OBJ_ENCODING_INTSET	整数集合（Intset）	集合元素全为整数且数量≤set-max-intset-entries（默认512）时使用，内存紧凑。
OBJ_ENCODING_HT	哈希表（Hashtable）	包含非整数元素或元素数量超过阈值时转换，键存储元素、值设为NULL。

---

五、有序集合对象（OBJ_ZSET）

编码方式	底层数据结构	触发条件与特性
OBJ_ENCODING_ZIPLIST	压缩列表（Ziplist）	元素数≤zset-max-ziplist-entries（默认128）且所有成员长度≤zset-max-ziplist-value（默认64字节）时使用，按分值排序。
OBJ_ENCODING_SKIPLIST+HT	跳跃表（Skiplist）+哈希表	超出Ziplist阈值时转换，跳跃表支持范围查询，哈希表提供O(1)的单元素访问。

---

六、编码动态转换机制

1. 自动升级
   • 当数据特征超出当前编码的容量或类型限制时，自动切换为更高效的编码（如Ziplist→Hashtable）。
2. 不可逆操作
   • 大部分转换是单向的（如Intset→Hashtable），Redis不主动降级以节省计算资源。