详解Redis数据结构(附源码)

电脑硬件
2025-09-07 00:15:02

引言

只有弄明白Redis数据结构，才能理解它如此快速的原因，并不只是它存储于内存，本篇文章将拆开Redis数据结构分析它高效的原因

字符串（String）

基本概念：字符串是 Redis 中最基本的数据结构，可以存储任何形式的字符串，包括文本、二进制数据等，一个字符串的最大长度可达 512MB。

底层代码：

struct sdshdr { // 记录 buf 数组中已使用字节的数量，等于 SDS 所保存字符串的长度 int len; // 记录 buf 数组中未使用字节的数量 int free; // 字节数组，用于保存字符串 char buf[]; }; len：该字段记录了当前 SDS 中存储的字符串的实际长度。通过这个字段，获取字符串长度的操作时间复杂度为 O (1)，而在传统 C 字符串中，需要遍历整个字符串来获取长度，时间复杂度为 O (n)。free：它表示 buf 数组中尚未使用的字节数量。这个字段的存在使得 SDS 在进行字符串修改时，可以预先分配足够的空间，减少内存重新分配的次数。buf：这是一个字符数组，用于实际存储字符串的内容。在数组的末尾，会以 '\0' 结尾，这样可以兼容部分 C 字符串函数。

总结以上：获取字符串长度时间复杂度O(1)，减少内存分配次数，兼容C语言函数

应用场景缓存数据：可缓存网页内容、数据库查询结果等，将网页的 HTML 内容以字符串形式存储，键为网页的 URL。计数器：用于统计网站访问量、用户点赞数等，通过incr命令记录文章阅读次数。

列表（List）

基本概念：列表是 Redis 中的一种线性数据结构，支持在头部或尾部插入和删除元素。列表可以存储多个字符串元素，元素可以重复，最大长度为 2^32 - 1。

底层代码： Redis 列表的底层实现有两种：

压缩列表（ziplist）：用于存储小列表，节省内存。

双向链表（linkedlist）：用于存储大列表，支持快速的头尾操作。

// 压缩列表结构（ziplist） struct ziplist { unsigned char *zlbytes; // 整个压缩列表占用的字节数 unsigned char *zltail; // 最后一个节点的偏移量 unsigned char *zllen; // 节点数量 unsigned char *zlentry; // 节点数据 }; // 双向链表节点结构 struct listNode { struct listNode *prev; // 前驱节点 struct listNode *next; // 后继节点 void *value; // 节点值 }; // 双向链表结构 struct list { listNode *head; // 链表头节点 listNode *tail; // 链表尾节点 unsigned long len; // 链表长度 };

特点：存储偏移量避免遍历查找末尾字节

压缩列表：内存紧凑，适合小列表，但插入和删除效率较低。

双向链表：支持 O(1) 时间复杂度的头尾插入和删除操作，适合频繁修改的场景。

应用场景：根据不同指定产生中间件

消息队列：使用 LPUSH 和 RPOP 实现队列。

最新消息列表：使用 LPUSH 和 LRANGE 获取最新消息。

栈：使用 LPUSH 和 LPOP 实现栈。

哈希（Hash）

基本概念：哈希是 Redis 中的一种键值对集合，适合存储对象。每个哈希可以存储多个字段和值，字段和值都是字符串类型。

底层代码： Redis 哈希的底层实现有两种：

压缩列表（ziplist）：用于存储小哈希，节省内存。

字典（dict）：用于存储大哈希，基于哈希表实现。

// 字典结构 struct dict { dictEntry **table; // 哈希表数组 unsigned long size; // 哈希表大小 unsigned long sizemask; // 哈希表大小掩码 unsigned long used; // 已使用的节点数 }; // 哈希表节点结构 struct dictEntry { void *key; // 键 union { void *val; uint64_t u64; int64_t s64; } v; // 值 struct dictEntry *next; // 指向下一个节点（解决哈希冲突） };

压缩列表：内存紧凑，适合小哈希。

sizemask（哈西表大小掩码）：是哈希表大小减 1（size - 1），用于将哈希值映射到哈希表的索引范围内。它的主要作用是：

快速计算索引：通过 hash & sizemask 的方式，将哈希值映射到哈希表的索引位置。

保证索引在合法范围内：由于 sizemask = size - 1，且 size 是 2 的幂次方，hash & sizemask 的结果一定在 [0, size-1] 范围内。

字典：支持 O(1) 时间复杂度的查找、插入和删除操作。

应用场景：

存储对象：如用户信息、商品信息。

字段级操作：可以直接修改某个字段，而不需要读取整个对象。

集合（Set）

基本概念：集合是 Redis 中的一种无序且唯一的数据结构，适合存储不重复的元素。

底层代码： Redis 集合的底层实现有两种：

整数集合（intset）：用于存储整数集合，节省内存。