黑马程序员Redis教程学习笔记（第8部分）：Redis底层数据结构原理（SDS、IntSet、ZipList）

课程概述

本篇笔记涵盖黑马程序员Redis教程中关于Redis底层数据结构原理的重要内容，包括SDS（简单动态字符串）、IntSet（整数集合）、ZipList（压缩列表）等核心数据结构的实现原理和优化策略。

1. Redis底层数据结构概览

1.1 数据结构的重要性

Redis的5种基本数据类型（String、Hash、List、Set、ZSet）底层都是基于更基础的数据结构实现的： - SDS：简单动态字符串，用于存储字符串 - IntSet：整数集合，用于存储整数集合 - ZipList：压缩列表，用于存储紧凑的列表数据 - Dict：哈希表，用于存储键值对 - SkipList：跳跃表，用于实现有序集合

1.2 Redis数据结构特点

内存友好：采用紧凑存储，减少内存占用
性能优化：针对Redis的使用场景进行专门优化
自动升级：根据数据特点自动选择最合适的数据结构

2. SDS（Simple Dynamic String）动态字符串

2.1 C语言字符串的问题

C语言字符串存在以下问题： 1. 获取长度时间复杂度高：O(N)，需要遍历整个字符串 2. 非二进制安全：以\0作为结束标识，如果字符串中包含\0会被误认为结束 3. 不可修改：字符串字面量保存在常量池中，无法修改

2.2 SDS结构详解

SDS是Redis自定义的字符串结构，包含以下字段：

struct SDS {
    uint8_t len;      // 已使用字节数
    uint8_t alloc;    // 总申请字节数（不含结束标识）
    uint8_t flags;    // 头信息类型标识
    char buf[];       // 存储实际数据的字符数组
};

2.3 SDS的优势

常数时间获取长度：O(1)时间复杂度
二进制安全：通过长度字段确定字符串边界
动态扩展：支持动态扩容
内存预分配：采用预分配策略，减少内存分配次数

2.4 SDS类型

Redis定义了多种SDS结构以适应不同长度的字符串： - sdshdr5：5位，已废弃 - sdshdr8：8位，最大2^8-1字节 - sdshdr16：16位，最大2^16-1字节 - sdshdr32：32位，最大2^32-1字节 - sdshdr64：64位，最大2^64-1字节

根据字符串长度自动选择合适的SDS类型，既节省内存又保证性能。

3. IntSet（整数集合）

3.1 IntSet概述

IntSet是Redis中用于存储整数集合的数据结构，具有以下特点： - 有序性：集合中的元素始终保持有序 - 唯一性：集合中的元素不允许重复 - 紧凑存储：内存占用小 - 自动升级：根据元素大小自动升级编码方式

3.2 IntSet结构

typedef struct intset {
    uint32_t encoding; // 编码方式
    uint32_t length;   // 元素个数
    int8_t contents[]; // 存储元素的数组
} intset;

3.3 编码方式

IntSet支持三种编码方式： - INTSET_ENC_INT16：16位整数，范围-32,768到32,767 - INTSET_ENC_INT32：32位整数，范围-2,147,483,648到2,147,483,647 - INTSET_ENC_INT64：64位整数，更大的范围

3.4 自动升级机制

当插入的整数超出当前编码范围时，IntSet会自动升级： 1. 扩展内存空间：根据新编码重新分配内存 2. 倒序复制元素：从后往前复制元素，避免数据覆盖 3. 插入新元素：将新元素插入到正确位置

升级示例：

初始状态：[5, 10, 20]，编码INTSET_ENC_INT16
插入50000：超出INT16范围，升级到INTSET_ENC_INT32
最终：[5, 10, 20, 50000]，编码INTSET_ENC_INT32

3.5 升级特性

不可降级：升级后不会降级
有序存储：使用二分查找定位插入位置
内存预分配：预留额外空间减少重分配

4. ZipList（压缩列表）

4.1 ZipList概述

ZipList是Redis为了节省内存而设计的一种紧凑数据结构，用于存储字符串或整数的列表。

4.2 ZipList结构

[ zlbytes ][ zltail ][ zllen ][ entry1 ][ entry2 ]...[ entryN ][ zlend ]

zlbytes：整个压缩列表占用的字节数
zltail：指向最后一个节点的偏移量
zllen：节点数量
entry：数据节点
zlend：结束标识（0xFF）

4.3 节点结构

每个节点（entry）包含三部分：

[ prevlen ][ encoding ][ content ]

prevlen：前一个节点的长度
encoding：编码属性，记录content的数据类型和长度
content：实际数据

4.4 编码方式

字符串编码：以00/01/10开头，根据长度选择不同编码
整数编码：以11开头，根据数值大小选择编码

5. Dict（哈希表）

5.1 Dict结构

Redis的字典基于哈希表实现：

typedef struct dict {
    dictType *type;     // 字典类型
    void *privdata;     // 私有数据
    dictht ht[2];       // 两张哈希表（用于rehash）
    long rehashidx;     // rehash索引
    unsigned long iterators; // 安全迭代器数量
} dict;

5.2 哈希表结构

typedef struct dictht {
    dictEntry **table;     // 哈希表数组
    unsigned long size;    // 哈希表大小
    unsigned long sizemask; // 哈希表大小掩码
    unsigned long used;    // 已使用节点数
} dictht;

5.3 渐进式Rehash

为避免一次性rehash造成阻塞，Redis采用渐进式rehash： 1. 创建新哈希表：同时维持两张哈希表 2. 逐步迁移：每次操作时迁移一个桶的数据 3. 完成迁移：释放旧哈希表

6. SkipList（跳跃表）

6.1 跳跃表概述

跳跃表用于实现有序集合（ZSet），具有以下特点： - 有序性：元素按分值有序排列 - 快速查找：平均O(logN)时间复杂度 - 支持范围查询：可高效查询范围内的元素

6.2 跳跃表结构

每个节点包含： - 分值（score）：用于排序 - 成员（member）：元素值 - 多层指针：指向不同层级的下一个节点 - 跨度（span）：到下一个节点的距离

7. RedisObject

7.1 RedisObject概述

Redis中所有值都用RedisObject包装：

typedef struct redisObject {
    unsigned type:4;        // 对象类型
    unsigned encoding:4;    // 编码方式
    unsigned lru:24;        // LRU时间
    int refcount;           // 引用计数
    void *ptr;              // 指向底层数据结构的指针
} robj;

7.2 对象类型

REDIS_STRING：字符串对象
REDIS_LIST：列表对象
REDIS_SET：集合对象
REDIS_ZSET：有序集合对象
REDIS_HASH：哈希对象

7.3 编码方式

不同数据类型可以使用不同的底层编码： - 字符串：RAW、EMBSTR、INT - 列表：ZIPMAP、QUICKLIST - 集合：INTSET、HASHTABLE - 有序集合：ZIPLIST、SKIPLIST - 哈希：ZIPLIST、HASHTABLE

8. 底层数据结构选择策略

8.1 自动转换条件

Redis会根据以下条件自动选择合适的数据结构：

字符串对象

EMBSTR编码：字符串长度≤44字节
RAW编码：字符串长度>44字节

列表对象

ZIPLIST编码：元素个数<512且元素长度<64字节
QUICKLIST编码：不满足ZIPLIST条件时

集合对象

INTSET编码：元素个数<512且全部为整数
HASHTABLE编码：不满足INTSET条件时

有序集合对象

ZIPLIST编码：元素个数<128且元素长度<64字节
SKIPLIST编码：不满足ZIPLIST条件时

哈希对象

ZIPLIST编码：键值对个数<512且键值长度<64字节
HASHTABLE编码：不满足ZIPLIST条件时

8.2 性能考虑

内存优化：使用紧凑的数据结构节省内存
访问效率：根据使用场景选择合适的数据结构
自动转换：Redis会自动在不同编码间转换

9. 应用实践

9.1 数据结构选择

在实际应用中，应根据数据特点选择合适的数据结构： - 小数据量：优先使用压缩数据结构 - 大数据量：使用哈希表等高效结构 - 有序需求：使用跳跃表 - 整数集合：使用IntSet

9.2 内存优化

合理配置转换阈值：通过配置参数调整自动转换条件
监控内存使用：关注不同数据结构的内存占用
避免BigKey：控制单个Key的大小

总结

Redis的底层数据结构设计充分考虑了性能和内存效率：

SDS解决了C语言字符串的问题：提供了常数时间获取长度、二进制安全、动态扩展等功能
IntSet实现了紧凑的整数集合存储：通过自动升级机制平衡内存和性能
ZipList节省了小数据的内存占用：通过紧凑布局减少内存碎片
Dict支持高效键值对存储：通过渐进式rehash避免阻塞
SkipList提供有序集合功能：在保证有序性的同时提供高效访问

理解这些底层数据结构的实现原理，有助于我们更好地使用Redis，选择合适的数据类型和优化策略，提升系统性能。