Skip to content

Redis数据结构

Redis为其五种基本数据类型（字符串、列表、哈希、集合、有序集合）设计了专门的底层数据结构。这样做是为了在特定场景下最大化地提升性能和内存使用效率。理解这些底层实现有助于在开发中进行性能优化。

1. 简单动态字符串 (Simple Dynamic String - SDS)

  • 定义: Redis自定义的字符串实现，用于替代C语言传统的以空字符\0结尾的字符串。

  • 核心优势:

    • 快速获取长度: 内部记录了字符串长度（len属性），获取长度的时间复杂度为O(1)。

    • 防止缓冲区溢出: 在拼接或修改字符串时，会预先检查空间，不足时自动扩容，杜绝了C语言字符串操作的溢出风险。

    • 优化内存分配:

      • 空间预分配: 扩容时会分配比实际需要更多的空间，减少连续增长操作带来的内存重分配次数。

      • 惰性空间释放: 缩短字符串时，多余的空间不会立即回收，而是记录下来以备后用。

    • 二进制安全: 通过len属性判断字符串结束，而非\0，因此可以存储包含\0的任意二进制数据（如图片、序列化对象）。

  • 结构: 主要由 len (已用长度)、alloc (总分配长度) 和 buf[] (实际数据存储区) 组成。

2. 压缩列表 (ZipList)

  • 定义: 一种为极度节省内存而设计的、连续存储的双向链表。当列表或哈希的元素数量较少且单个元素体积较小时，Redis会采用它。

  • 核心优势 (省内存):

    • 每个节点（entry）的长度是可变的，根据存储内容的实际大小而定。

    • 通过encoding字段来描述当前节点数据的类型和长度，避免了为所有节点预留同样大小的空间。

  • 结构: 整个ZipList是一块连续内存，包含zlbytes（总字节数）、zltail（尾节点偏移量）、zllen（节点数）和zlend（结束标志）。每个节点包含prevlen（前一节点的长度，用于反向遍历）和encoding（编码信息）。

  • 缺点:

    • 连锁更新: 修改中间的一个节点，如果导致其长度变化，可能会引起其后所有节点的prevlen字段都需要更新，在最坏情况下时间复杂度为O(N)。

    • 写操作涉及内存重分配，开销较大。

3. 快表 (QuickList)

  • 定义: Redis 3.2 之后引入，是列表（List）数据类型的标准底层实现。它是一个双向链表，但每个链表节点都是一个ZipList。

  • 核心优势:

    • 在ziplist（省内存但修改复杂）和普通双向链表（指针开销大但修改灵活）之间做出了完美平衡。

    • 将一个大列表切分成多个小的ZipList，限制了连锁更新的影响范围，同时减少了指针的内存开销。

  • 特点: 可以通过配置项fill来限制每个ZipList的大小，还可以通过compress配置对两端之外的ZipList节点进行LZF压缩，进一步节省内存。

4. 字典/哈希表 (Dict / Hash Table)

  • 定义: Redis的哈希（Hash）类型和数据库本身（存储所有键值对）的底层实现，本质就是哈希表。

  • 核心优势 (渐进式Rehash):

    • 当哈希表需要扩容或缩容时，操作不是一次性完成的。

    • 它会创建一个新的空哈希表，然后在后续的每次增、删、改、查操作中，将旧哈希表中的一小部分数据“顺便”迁移到新表中，直到迁移完成。

    • 这个机制避免了因一次性迁移海量数据而导致的服务器长时间阻塞。

  • 结构:

    • 采用链地址法解决哈希冲突，即哈希值相同的元素会通过指针形成一个链表。

    • 内部包含两个哈希表（ht[0]和ht[1]），一个用于当前使用，一个用于rehash过程。

5. 整数集 (IntSet)

  • 定义: 当集合（Set）中的所有元素都是整数，且元素数量不多时，Redis会使用整数集作为其底层实现。

  • 核心优势:

    • 内部数据存储在一个有序、无重复的数组中，非常紧凑，节省内存。

  • 核心特性 (升级):

    • 当向一个只能存储16位整数（int16_t）的整数集中添加一个32位整数（int32_t）时，整数集会自动“升级”。

    • 它会重新分配能容纳32位整数的内存空间，并将所有现有元素转换为32位，再插入新元素，并保持有序。

    • 升级是单向的，不会为了节省空间而降级。

6. 跳表 (ZSkipList / Skip List)

  • 定义: 有序集合（ZSet）的底层实现之一。它是一种在有序链表基础上增加了多级“快速通道”（索引）的数据结构。

  • 核心优势:

    • 通过多级索引，实现了平均O(logN)时间复杂度的查找、插入和删除操作，性能媲美平衡树。

    • 相比平衡树（如红黑树），跳表的实现更简单，代码更易于理解和维护。

    • 进行范围查找（如ZRANGE命令）时，逻辑非常清晰，只需在底层链表上顺序遍历即可。

  • 结构:

    • 每个节点除了有指向下一个节点的指针外，还包含一个层（level）数组，每层都有一个指向该层更远处节点的forward指针。

    • 节点创建时会随机生成一个层数，层数越高的节点越少，构成了金字塔形的索引结构。