2. Redis 核心数据结构与性能基础：String、List、Hash、Set、ZSet 的底层编码与时间复杂度分析

Redis 之所以能成为企业级热点削峰场景的首选缓存组件，其核心优势不仅在于纯内存操作，更在于其五种基本数据结构（String、List、Hash、Set、ZSet）背后精巧的底层编码机制。理解这些编码方式及其对应的时间复杂度，是进行性能调优和系统设计的前提。

2.1 数据结构全景概览

Redis 对外暴露五种数据类型，每种类型在内部根据存储数据的特点（如数据大小、元素数量、元素类型）动态切换底层编码，以在内存占用和访问速度之间取得最佳平衡。

2.2 String：最基础的原子操作单元

String 是 Redis 中最简单的数据类型，但也是性能最极致、使用最广泛的结构。其底层编码根据存储内容动态选择：

• int 编码： 当存储的字符串可以表示为 64 位有符号整数时，Redis 直接使用 long 类型存储，此时 INCR、DECR 等操作是纯 CPU 级别的原子递增，时间复杂度为 O(1)。
• embstr 编码： 当字符串长度小于等于 44 字节（Redis 7.0 中为 44，早期版本为 39）时，Redis 使用 embstr 编码。它将 redisObject 和 sdshdr 结构体分配在同一块连续内存中，一次内存分配，一次内存释放，缓存局部性极佳。
• raw 编码： 当字符串长度超过 44 字节时，使用 raw 编码，redisObject 和 sdshdr 分开分配内存，需要两次分配。

# 时间复杂度示例
SET key value          # O(1)
GET key                # O(1)
INCR counter           # O(1)
APPEND key "suffix"    # O(N)，N 为追加后字符串长度
STRLEN key             # O(1)

2.3 List：从 ziplist 到 quicklist 的演进

List 在 Redis 3.2 版本之后统一使用 quicklist 编码。quicklist 是一个双向链表，但每个节点内部是一个 ziplist（紧凑列表）。这种设计兼顾了内存压缩和两端操作的性能。

• ziplist 节点： 每个 ziplist 存储一定数量的元素（默认 8KB 或 8192 个元素），元素在内存中连续存储，节省指针开销。
• 链表结构： 通过双向指针连接多个 ziplist，支持在两端快速插入和删除。

# 时间复杂度示例
LPUSH key value        # O(1)
RPUSH key value        # O(1)
LPOP key               # O(1)
RPOP key               # O(1)
LINDEX key index       # O(N)，N 为链表长度，需要遍历
LRANGE key 0 -1        # O(N)，N 为返回元素个数

2.4 Hash：对象缓存的性能利器

Hash 是存储对象属性的最佳选择。其底层编码在 Redis 7.0 之后发生了重要变化：

• listpack 编码（替代 ziplist）： 当 Hash 中的字段数量小于 hash-max-listpack-entries（默认 512）且每个字段的 key 和 value 长度小于 hash-max-listpack-value（默认 64 字节）时，使用 listpack。listpack 比 ziplist 更紧凑，且避免了 ziplist 的级联更新问题。
• hashtable 编码： 当超过上述阈值时，自动升级为哈希表，此时所有操作的时间复杂度为 O(1)。

# 时间复杂度示例
HSET user:1001 name "Alice"    # O(1)
HGET user:1001 name            # O(1)
HGETALL user:1001              # O(N)，N 为字段数量
HMSET user:1001 age 30 city "NY" # O(N)，N 为字段数量
HLEN user:1001                 # O(1)

2.5 Set：无序集合的去重与运算

Set 用于存储不重复的元素集合，支持高效的集合运算（交集、并集、差集）。其底层编码有两种：

• intset 编码： 当集合中所有元素都是整数，且元素数量小于 set-max-intset-entries（默认 512）时，使用整数集合。intset 使用有序数组存储，支持二分查找，时间复杂度为 O(log N)。
• hashtable 编码： 当不满足 intset 条件时，自动升级为哈希表，所有元素操作的时间复杂度为 O(1)。

# 时间复杂度示例
SADD key member         # O(1)
SREM key member         # O(1)
SISMEMBER key member    # O(1)
SMEMBERS key            # O(N)，N 为集合大小
SINTER key1 key2        # O(N * M)，N 和 M 为集合大小
SUNION key1 key2        # O(N + M)
SPOP key                # O(1)

2.6 ZSet：有序集合的排序与范围查询

ZSet 是 Redis 中最复杂的数据结构，它结合了 skiplist（跳表） 和 hashtable（哈希表） 两种底层实现，同时支持按 score 排序和按 member 快速查找。

• listpack 编码（小数据量）： 当 ZSet 元素数量小于 zset-max-listpack-entries（默认 128）且所有元素长度小于 zset-max-listpack-value（默认 64 字节）时，使用 listpack 存储，按 score 排序。
• skiplist + hashtable 编码（大数据量）： 当超过阈值时，使用跳表维护有序性（O(log N) 插入/删除/查找），同时使用哈希表维护 member 到 score 的映射（O(1) 查找）。

# 时间复杂度示例
ZADD key score member       # O(log N)
ZREM key member             # O(log N)
ZSCORE key member           # O(1) - 哈希表直接定位
ZRANK key member            # O(log N) - 跳表查找
ZRANGE key 0 10             # O(log N + M)，M 为返回元素数
ZRANGEBYSCORE key min max   # O(log N + M)
ZCARD key                   # O(1)

2.7 时间复杂度对比总结

下表汇总了五种数据结构在典型操作下的时间复杂度，帮助你在系统设计时做出正确的结构选择：