| redis对象 | redis 数据结构 |
| 字符串对象 | SDS(简单动态字符串) |
| 列表对象 | 压缩列表(ziplist) 或 链表(linkedlist) |
| 哈希对象 | 压缩列表 或 字典 |
| 集合对象 | 整数集合 或 字典 |
| 有序集合对象 | 压缩列表 或 跳跃表和字典 |
| 类型 | 编码 | 对象 |
|---|---|---|
REDIS_STRING | REDIS_ENCODING_INT | 使用整数值实现的字符串对象。 |
REDIS_STRING | REDIS_ENCODING_EMBSTR | 使用 embstr 编码的简单动态字符串实现的字符串对象。 |
REDIS_STRING | REDIS_ENCODING_RAW | 使用简单动态字符串实现的字符串对象。 |
REDIS_LIST | REDIS_ENCODING_ZIPLIST | 使用压缩列表实现的列表对象。 |
REDIS_LIST | REDIS_ENCODING_LINKEDLIST | 使用双端链表实现的列表对象。 |
REDIS_HASH | REDIS_ENCODING_ZIPLIST | 使用压缩列表实现的哈希对象。 |
REDIS_HASH | REDIS_ENCODING_HT | 使用字典实现的哈希对象。 |
REDIS_SET | REDIS_ENCODING_INTSET | 使用整数集合实现的集合对象。 |
REDIS_SET | REDIS_ENCODING_HT | 使用字典实现的集合对象。 |
REDIS_ZSET | REDIS_ENCODING_ZIPLIST | 使用压缩列表实现的有序集合对象。 |
REDIS_ZSET | REDIS_ENCODING_SKIPLIST | 使用跳跃表和字典实现的有序集合对象。 |
REDIS_STRING
编码raw结构
sds字符串
struct sdshdr{
//记录 buf 数组中已使用字节的数量
int len;
//纪录buf未使用字节的数量
int free
//存放字符串
char buf[];
};
作用 ： 作为redis 的部分键 和 值
REDIS_LIST
列表实现通过 链表和压缩列表
linkedlist
typedef struct listNode { // 前置节点 struct listNode *prev; // 后置节点 struct listNode *next; // 节点的值 void *value;} listNode; typedef struct list { // 表头节点 listNode *head; // 表尾节点 listNode *tail; // 链表所包含的节点数量 unsigned long len; // 节点值复制函数 void *(*dup)(void *ptr); // 节点值释放函数 void (*free)(void *ptr); // 节点值对比函数 int (*match)(void *ptr, void *key);} list; 作用 ：链表为列表键 链表节点为值 实现redis 发布与订阅， 慢查询， 监视器， 等等。
REDIS_HASH
哈希键的实现 字典 ／压缩列表
字典的实现
typedef struct dict { // 类型特定函数 dictType *type; // 私有数据 void *privdata; // 哈希表 rehash 时使用ht［1］ dictht ht[2]; // rehash 索引 // 当 rehash 不在进行时，值为 -1 int rehashidx; /* rehashing not in progress if rehashidx == -1 */} dict;
哈希表的实现
typedef struct dictht { // 哈希表数组 dictEntry **table; // 哈希表大小 unsigned long size; // 哈希表大小掩码，用于计算索引值 // 总是等于 size - 1 unsigned long sizemask; // 该哈希表已有节点的数量 unsigned long used;} dictht; 哈希表的节点
typedef struct dictEntry { // 键 void *key; // 值 union { void *val; uint64_t u64; int64_t s64; } v; // 指向下个哈希表节点，形成链表 struct dictEntry *next;} dictEntry; 通过链表解决冲突问题
负载因子为0.5 时扩张 小于0.1收缩
REDIS_SET
通过整数集合和字典实现
整数集合结构 只有小整数 才会在这里 其余都是在字典中实现
typedef struct intset { // 编码方式 uint32_t encoding; // 集合包含的元素数量 uint32_t length; // 保存元素的数组 int8_t contents[];} intset; 
REDIS_ZSET
有序集合通过跳跃表和字典实现或压缩列表
有序集合的跳跃表和字典实现
跳跃表的实现
typedef struct zskiplist { // 表头节点和表尾节点 struct zskiplistNode *header, *tail; // 表中节点的数量 unsigned long length; // 表中层数最大的节点的层数 int level;} zskiplist; 跳跃表的节点实现
typedef struct zskiplistNode { // 后退指针 struct zskiplistNode *backward; // 分值 double 类型的浮点数， 跳跃表中的所有节点都按分值从小到大来排序 double score; // 成员对象 指向sds对象 值 robj *obj; // 层 层高范围1－32 第一层level［0］ struct zskiplistLevel { // 前进指针 指向当前层的下一个节点 struct zskiplistNode *forward; // 跨度 纪录与同层下一节点之间的距离 unsigned int span; } level[];} zskiplistNode;
有序集合的实现
typedef struct zset { zskiplist *zsl; // 跳跃表 dict *dict; // 字典} zset; zset 结构中的 dict 字典为有序集合创建了一个从成员到分值的映射， 字典中的每个键值对都保存了一个集合元素： 字典的键保存了元素的成员， 而字典的值则保存了元素的分值。 通过这个字典， 程序可以用 O(1) 复杂度查找给定成员的分值， ZSCORE 命令就是根据这一特性实现的， 而很多其他有序集合命令都在实现的内部用到了这一特性。
为什么有序集合需要同时使用跳跃表和字典来实现？
在理论上来说， 有序集合可以单独使用字典或者跳跃表的其中一种数据结构来实现， 但无论单独使用字典还是跳跃表， 在性能上对比起同时使用字典和跳跃表都会有所降低。
举个例子， 如果我们只使用字典来实现有序集合， 那么虽然以 O(1) 复杂度查找成员的分值这一特性会被保留， 但是， 因为字典以无序的方式来保存集合元素， 所以每次在执行范围型操作 —— 比如 ZRANK 、 ZRANGE 等命令时， 程序都需要对字典保存的所有元素进行排序， 完成这种排序需要至少 O(N \log N) 时间复杂度， 以及额外的 O(N) 内存空间 （因为要创建一个数组来保存排序后的元素）。
另一方面， 如果我们只使用跳跃表来实现有序集合， 那么跳跃表执行范围型操作的所有优点都会被保留， 但因为没有了字典， 所以根据成员查找分值这一操作的复杂度将从 O(1) 上升为 O(\log N) 。
因为以上原因， 为了让有序集合的查找和范围型操作都尽可能快地执行， Redis 选择了同时使用字典和跳跃表两种数据结构来实现有序集合。
参考文献 《redis设计与实现》