Redis 中 string 和 list 的底层实现
Redis有5种基础数据结构，对应的value分别为：string (字符串)、list (列表)、set (集合)、hash (哈希) 和 zset (有序集合)
Redis 对象头结构体：
struct RedisObject {int4 type; // 4bits 对象的基本类型int4 encoding; // 4bits 对象的编码方式int24 lru; // 24bits 对象的最近访问时间（Least Recently Used）int32 refcount; // 4bytes 对象的引用计数void *ptr; // 8bytes，64-bit system 指向对象的实际存储位置
} robj;
string
结构
Redis的字符串是动态字符串，是可以修改的字符串，内部结构实现上类似于Go的slice切片，采用预分配冗余空间的方式来减少内存的频繁分配
- 内部为当前字符串实际分配的空间capacity一般要高于实际字符串长度len
- 当字符串长度小于1M时，扩容加倍；大于1M时，扩容增加1M
- 字符串最大长度为512M
sds
虽然Redis是用c实现的，但是他们的string结构并不相同，Redis中的字符串是可以修改的字符串，在内存中它是以字节数组的形式存在的
Redis 的字符串叫「SDS」，也就是 Simple Dynamic String，是一个带长度信息的字节数组
struct SDS<T> {T capacity; // 数组容量 使用泛型表示T len; // 数组长度 使用泛型表示byte flags; // 特殊标识位.byte[] content; // 数组内容 字节数组
}
T:当字符串比较短时，len和capacity可以使用byte和short来表示，Redis为了对内存做极致的优化，不同长度的字符串使用不同的结构体来表示
编码方式
sds编码
当字符串长度小于或等于 44 字节 时，Redis 使用
embstr编码（embedded string 嵌入式）当字符串长度大于 44 字节 时，Redis 使用
raw编码
整数编码
当存储的值是一个小整数时，Redis 会使用整数编码来存储，这样可以节省内存
list
Redis 的List类型是一个简单的字符串列表，支持从头部或尾部插入和删除元素。它的底层实现方式取决于列表的大小和元素的特性
双向链表（LinkedList）
在Redis3.2之前，当List的元素数量较多或元素较大时，Redis使用双向链表作为底层数据结构
// 节点
typedef struct listNode {struct listNode *prev; //上一元素struct listNode *next; //下一元素void *value; //元素值
} listNode;// 双向链表
typedef struct list {// 头结点listNode *head;// 尾元素listNode *tail;// 元素值复制函数void *(*dup)(void *ptr);// 元素值释放函数void (*free)(void *ptr);// 元素值对比函数int (*match)(void *ptr, void *key);// 元素长度unsigned long len;
} list;
压缩链表（ziplist）
当List中的元素数量较少（默认小于512个）且每个元素的大小较小（默认小于 64 字节）时，Redis会使用 ziplist
zlbytes：4 字节，记录整个 Ziplist 占用的内存字节数zltail：4 字节，记录 Ziplist 表尾节点的偏移量zllen：2 字节，记录 Ziplist 中的节点数量entry：列表节点，每个节点的长度由其内容决定zlend：1 字节，标记 Ziplist 的结束（值为 0xFF）
快排列表（quicklist）
结构
在3.2之后，Redis使用Quicklist
Quicklist是由多个压缩列表（ziplist）组成的双向链表，每个压缩列表称为一个节点
// quicklist.htypedef struct quicklistEntry {unsigned char *value; // 存储的值unsigned int sz; // 值得长度long long longval; // 如果是整数，这里存储整数表示unsigned int encoding:4; // 值得编码方式unsigned int attempted_float_conversion:1; // 是否尝试过将值转换为浮点数
} quicklistEntry;typedef struct quicklistNode {struct quicklistNode *prev; // 前一个节点struct quicklistNode *next; // 下一个节点unsigned char *zl; // 指向ziplistunsigned int sz; // ziplist的大小unsigned int count:16; // ziplist中的元素数量unsigned int encoding:4; // 编码类型unsigned int container:4; // 容器类型unsigned int recompress:1; //是否需要重新压缩
} quicklistNode;typedef struct quicklist {quicklistNode *head; // 头节点quicklistNode *tail; // 尾节点const quicklistCompress *compress; // 压缩深度unsigned int count; // 节点数量unsigned long len; // 总元素数量signed int fill : QL_FILL_BITS; // 每个节点的填充因子unsigned int compress : QL_COMP_BITS; // 压缩深度unsigned int bookmark_count: QL_BM_BITS; // 书签数量quicklistBookmark bookmarks[]; // 书签数组
} quicklist;主要的数据结构包括：
- quicklistEntry：表示 quicklist 中的一个条目（entry）
- quicklistNode：表示 quicklist 中的一个节点，包含一个 ziplist
- quicklist：整个 quicklist 结构，包含头尾节点、统计信息等
工作原理
- 节点存储：
- 每个
quicklistNode包含一个 ziplist，用于紧凑存储多个元素。- ziplist 是一种紧凑的内存结构，适合存储小数据项。
- 动态调整：
- 当向 Quicklist 中插入数据时，Redis 会根据配置的
list-max-ziplist-size参数决定是否需要创建新的节点。- 如果当前 ziplist 达到大小限制，Redis 会创建一个新的
quicklistNode，并在新节点中创建一个新的 ziplist。- 压缩策略：
- Quicklist 支持对中间节点进行压缩，以节省内存。
- 压缩深度由
list-compress-depth参数控制，可以指定两端不压缩的节点数量。- 内存管理：
- Quicklist 通过合理控制 ziplist 的大小，避免大规模连续内存申请。
- 压缩和解压缩使用 LZF 算法，适合实时应用。