Redis 五种基本数据类型（String、List、Hash、Set、ZSet）的强大性能与其精巧的底层数据结构设计密不可分。Redis 并没有直接使用这些简单动态字符串（SDS）、链表、字典等数据结构，而是根据不同的使用场景，用一种上层建筑，下层基础的方式，为同一个数据类型提供了多种底层实现，并在合适的时机进行自动转换，以达到性能与空间的最优平衡。

String（字符串）

String 是 Redis 中最基础的数据类型，但其底层实现并非只有一种简单的方式。

底层数据结构：

  1. RAW (SDS - Simple Dynamic String)： 这是最标准的字符串表示方式。SDS 是 Redis 对 C 语言原生字符串的封装和增强。

    • 结构定义：
      1
      2
      3
      4
      5
      struct sdshdr {
          int len;    // 记录buf数组中已使用字节的数量，等于SDS所保存字符串的长度
          int alloc;  // 记录buf数组中未使用字节的数量
          char buf[]; // 字节数组，用于保存实际的字符串内容
      };
    • 优点：
      • O(1) 时间复杂度获取字符串长度： 直接访问 len 属性，而 C 字符串需要遍历。
      • 杜绝缓冲区溢出： SDS 的 API（如 sdscat）会先检查 alloc 是否足够，不足则自动扩展。
      • 减少修改字符串时带来的内存重分配次数： 采用空间预分配（扩容时会多分配一些空间）和惰性空间释放（缩短时不立即释放多余空间）策略。
      • 二进制安全： 因为依赖 len 而不是 ‘\0’ 来判断字符串结束，可以存储任何二进制数据，包括图片、协议等。

  2. EMBSTR (Embedded String)： 一种嵌入式字符串，用于存储非常短（在 Redis 3.x 后，长度 ≤ 44 字节）的字符串。

    • 实现原理： 它将 Redis 的 redisObject 对象头 和 sdshdr 结构在内存上连续分配，一次性分配一块连续内存来容纳两者。
    • 优点：
      • 内存效率高： 只需要一次内存分配操作。
      • 缓存友好： 数据连续，能更好地利用 CPU 缓存。

  3. INT： 当字符串值可以表示为一个长整型数字时，Redis 会直接将数据保存在 redisObject 的 ptr 指针里（将 void* 强制转换为 long）。

    • 优点：
      • 节省内存： 无需额外的 SDS 结构。
      • 性能极致： 无需对字符串进行解析。

编码转换：

  • int -> raw： 当对一个 int 编码的字符串进行 append 等修改操作，使其不再是整数时，会转换为 raw 编码。
  • embstr -> raw： 由于 embstr 是只读的，任何对 embstr 编码的字符串的修改命令，都会先将其转换为 raw 编码，然后再执行修改。

List（列表）

Redis 的 List 是一个双向链表，但其底层实现经历了多次演化，现在默认使用的是 quicklist。

底层数据结构：

QUICKLIST（快速列表）： 一个由 ziplist（压缩列表） 作为节点的双向链表。它是 zipList 和 linkedList 的一种混合体，取二者之长。

  • ziplist (压缩列表)：
    • 是一块连续的内存，通过不同的编码来存储数据（整数或短字符串）。
    • 优点：内存紧凑，利用率高（是一块连续内存，没有指针开销）。
    • 缺点：每次插入删除都可能引发连锁更新（因为需要重新分配内存以保证连续性），性能较差。
  • linkedList (双向链表)：
    • 由多个节点通过指针连接而成。
    • 优点：插入删除效率高，只需要修改指针。
    • 缺点：内存开销大（每个节点除了数据，还有前后两个指针），内存碎片化。
  • quicklist 的折中方案：
    • quicklistNode 结构包含一个指向 ziplist 的指针。
    • quicklist 结构包含了链表的头尾节点、长度等信息。
    • 通过配置 list-max-ziplist-size，可以控制每个 ziplist 节点的最大容量。如果超过这个值，就会新建一个 quicklistNode 节点。
    • 通过配置 list-compress-depth，可以对链表两端的 ziplist 节点进行压缩（使用 LZF 算法），以进一步节省内存。

总结：List 的底层就是一个宏观上是链表（便于修改），微观上是压缩列表（节省内存）的 quicklist 结构。

Hash（哈希）

Hash 类型的底层实现有两种：ziplist 和 hashtable（字典）。Redis 会根据条件自动选择。

底层数据结构：

  1. ZIPLIST（压缩列表）：

    • 使用条件（可通过 hash-max-ziplist-entries 和 hash-max-ziplist-value 配置）：
      • 哈希对象保存的所有键值对的键和值的字符串长度都小于 hash-max-ziplist-value（默认 64 字节）。
      • 哈希对象保存的键值对数量小于 hash-max-ziplist-entries（默认 512 个）。
    • 存储方式： 每当有新的键值对加入到哈希时，程序会先将键压入 ziplist 的尾部，再将值压入 ziplist 的尾部。因此，同一个键值对的两个节点总是紧挨在一起，键节点在前，值节点在后。

  2. HASHTABLE（字典）：

    • 当上述条件不满足时，编码会自动从 ziplist 转换为 hashtable。
    • 结构： 与 Java 的 HashMap 类似，是“数组 + 链表”的拉链法实现，但做了很多优化。
      • 字典 dict 结构包含两个哈希表 dictht ht[2]，这是为了渐进式 rehash 而设计的。
      • 哈希表 dictht 包含一个指针数组 table，每个元素是一个指向 dictEntry 结构的指针。
      • 键值对 dictEntry 结构包含了键、值和指向下一个 dictEntry 的指针（形成链表）。
    • Rehash： 当哈希表保存的键值对数量过多或过少时，需要通过 rehash 来扩展或收缩数组大小。Redis 采用渐进式 rehash，在 rehash 过程中，同时使用 ht[0] 和 ht[1]，分多次、渐进地将 ht[0] 中的数据迁移到 ht[1] 中，避免了单次 rehash 的巨大延迟。

Set（集合）

Set 类型的底层实现也有两种：intset（整数集合）和 hashtable（字典）。

底层数据结构：

  1. INTSET（整数集合）：

    • 使用条件：
      • 集合对象保存的所有元素都是整数值。
      • 集合对象保存的元素数量不超过 set-max-intset-entries（默认 512 个）。
    • 结构： intset 是一个有序的、不重复的整数数组。它支持三种编码：int16_t, int32_t, int64_t。会根据存入的最大整数自动升级编码（例如，原先是 int16_t 的数组，存入一个 int32_t 的数字，整个数组都会升级为 int32_t）。

  2. HASHTABLE（字典）：

    • 当不满足 intset 的条件时，会转换为 hashtable。
    • 在 Set 中使用字典时，字典的每个键就是集合的元素，而字典的值全部设置为 NULL。

ZSet（有序集合）

ZSet 是 Redis 中最有特色的数据结构，它既要保证元素的唯一性，又要为每个元素关联一个 score 用于排序。其底层实现同样有两种：ziplist 和 skiplist + dict（跳跃表+字典）。

底层数据结构：

  1. ZIPLIST（压缩列表）：

    • 使用条件（可通过 zset-max-ziplist-entries 和 zset-max-ziplist-value 配置）：
      • 有序集合保存的元素数量小于 zset-max-ziplist-entries（默认 128 个）。
      • 有序集合保存的所有元素成员的长度都小于 zset-max-ziplist-value（默认 64 字节）。
    • 存储方式： 与 Hash 类似，每个元素使用两个紧挨在一起的 ziplist 节点来保存，第一个节点保存元素的成员（member），第二个节点保存元素的分值（score）。ziplist 内的集合元素按分值从小到大排序。

  2. SKIPLIST + DICT（跳跃表 + 字典）：

    • 这是最复杂的结构，由一个跳跃表 zsl 和一个字典 dict 共同实现。
    • 为什么需要两种结构？
      • 跳跃表 (zskiplist)： 核心结构，支持范围性操作（如 ZRANGE, ZRANK），时间复杂度为 O(logN)。跳跃表是一种多层的有序链表，通过建立“索引”来加快查找速度。
      • 字典 (dict)： 用于支持 O(1) 时间复杂度的按成员键取值操作（如 ZSCORE）。字典的键是成员（member），值是分值（score）。
    • 数据共享： 跳跃表的节点 zskiplistNode 和字典的 dictEntry 会共享成员和分值对象，不会造成数据的重复存储，节省内存。

总结：ZSet 通过同时使用跳跃表和字典，既高效地支持了按分值排序和范围查询，又高效地支持了按成员键访问，以空间换时间，实现了功能的极致性能。

核心思想总结

Redis 数据类型的底层实现哲学可以概括为：

  1. 灵活性： 同一数据类型有多种底层实现，根据数据内容和配置动态选择最合适的编码。
  2. 效率至上： 在时间（操作速度）和空间（内存占用）之间做精妙的权衡。
  3. 平滑升级： 当数据量变化导致当前编码不再高效时，会自动转换为更合适的编码，这个过程对用户透明。
  4. 底层优化： 对基础数据结构（如 SDS、字典的渐进式 rehash、跳跃表）进行了大量极致优化，这些是 Redis 高性能的基石。