Redis 数据结构

结构 /* ZSETs use a specialized version of Skiplists */ typedef struct zskiplistNode { sds ele; double score; struct zskiplistNode *backward; struct zskiplistLevel { struct zskiplistNode *forward; unsigned int span; } level[]; } zskiplistNode; typedef struct zskiplist { struct zskiplistNode *header, *tail; unsigned long length; int level; } zskiplist; ele: 持有数据，是一个 sds 结构 score: 分值 backward: 指向前一个节点 level: 层级，包含 forward 和 span 两个字段 forward: 指向下一个节点 span: 记录跨度，即当前节点到下一个节点的距离 优势 插入、删除、查找的时间复杂度都是 O(logN) 有序，可以使用跳表进行范围查询

结构 typedef struct dict { dictEntry **table; unsigned long size; unsigned long sizemask; unsigned long used; } dict; typedef struct dictEntry { void *key; union { void *val; uint64_t u64; int64_t s64; } v; struct dictEntry *next; } dictEntry; key: 键 val: 值，值可以是一个指针，也可以是 uint64_t 或 int64_t 类型的整数 next: 指向下一个节点，形成链表 哈希算法 // 使用字典设置的哈希函数，计算键 key 的哈希值 hash = dict->type->hashFunction(key); // 使用哈希表的 sizemask 属性和第一步得到的哈希值，计算索引值 index = hash & dict->ht[x].sizemask; 关注点 解决哈希冲突：拉链表，使用 *next 指向下一个具有相同索引值的哈希表节点 扩容和缩容：根据原哈希表已使用的空间扩大一倍或缩小一半 扩容条件： 没有执行 BGSAVE 或 BGREWRITEAOF 命令，且负载因子大于 1 在执行 BGSAVE 或 BGREWRITEAOF 命令，负载因子大于 5 渐进式 rehash：在 rehash 的过程中，新哈希表和旧哈希表同时存在，查询时先查询新哈希表，再查询旧哈希表，写入时只写入新哈希表

结构 双向链表，每一个节点都是一个 ziplist /* Node, quicklist, and Iterator are the only data structures used currently. */ /* quicklistNode is a 32 byte struct describing a ziplist for a quicklist. * We use bit fields keep the quicklistNode at 32 bytes. * count: 16 bits, max 65536 (max zl bytes is 65k, so max count actually < 32k). * encoding: 2 bits, RAW=1, LZF=2. * container: 2 bits, NONE=1, ZIPLIST=2. * recompress: 1 bit, bool, true if node is temporarry decompressed for usage....

介绍 SDS 全称为 Simple Dynamic String，用于存储二进制数据的一种结构，具有动态扩容、空间预分配、二进制安全等特性。Redis 中的字符串对象就是使用 SDS 结构实现的。 总体结构 struct __attribute__ ((__packed__)) sdshdr8 { uint8_t len; /* used */ uint8_t alloc; /* excluding the header and null terminator */ unsigned char flags; /* 3 lsb of type, 5 unused bits */ char buf[]; }; struct __attribute__ ((__packed__)) sdshdr16 { uint16_t len; /* used */ uint16_t alloc; /* excluding the header and null terminator */ unsigned char flags; /* 3 lsb of type, 5 unused bits */ char buf[]; }; struct __attribute__ ((__packed__)) sdshdr32 { uint32_t len; /* used */ uint32_t alloc; /* excluding the header and null terminator */ unsigned char flags; /* 3 lsb of type, 5 unused bits */ char buf[]; }; struct __attribute__ ((__packed__)) sdshdr64 { uint64_t len; /* used */ uint64_t alloc; /* excluding the header and null terminator */ unsigned char flags; /* 3 lsb of type, 5 unused bits */ char buf[]; }; len：记录 buf 中已使用的字节数 alloc：记录 buf 中已分配的字节数 flags：记录 buf 的类型，低 3 位表示类型，高 5 位未使用 buf：存储字符串的字节数组 优势 常数复杂度获取字符串长度：读取 len 字段即可，不需要遍历整个字符串 不存在缓冲区溢出问题：根据 len 和 alloc 字段，判断是否需要扩容 空间预分配，减少内存重分配次数：每次扩容都会多分配一些内存，减少内存重分配次数 二进制安全，可以存储任意二进制数据：以 len 字段的长度来判断字符串的结束，而不是以空字符 \0 来判断 兼容部分 C 字符串函数：遵从每个字符串的最后一个字节是空字符 \0 的惯例，可以使用部分 C 字符串函数 空间预分配 当执行字符串拼接操作时，如果字符串的长度超过了已分配的内存，Redis 会对字符串进行扩容。扩容的规则如下：...

什么时候会使用 IntSet 集合中的元素都是整数 元素数量不超过 set-max-intset-entries 参数设置的阈值 set-max-intset-entries：这个参数用于设置 intset 的最大元素数量。当集合的元素数量超过这个阈值时，Redis 会将底层实现从 intset 转换为 hashtable。默认值通常为 512 数据结构 typedef struct intset { uint32_t encoding; // 编码方式 uint32_t length; // 元素数量 int8_t contents[]; // 元素数组 } intset; contents 数组中的元素是有序的，且不重复。encoding 用于标识 contents 数组中的元素是什么类型的整数。encoding 的值有三种： INTSET_ENC_INT16 16 位整数 INTSET_ENC_INT32 32 位整数 INTSET_ENC_INT64 64 位整数 升级操作 如果插入的元素超过了 intset 的编码方式，Redis 会将 intset 升级为更大的编码方式。例如，如果 intset 的编码方式是 INTSET_ENC_INT16，而插入的元素是 32 位整数，那么 Redis 会将 intset 的编码方式升级为 INTSET_ENC_INT32 步骤如下： 扩容 intset，将 intset 的编码方式升级为更大的编码方式 从后往前，将 intset 中的元素转换为更大的编码方式 插入新的元素 图解如下： 不支持降级操作，一旦升级，就不会再降级！！！...