Redis基本数据结构
2021-01-23 本文已影响0人
鸿雁长飞光不度
SDS(简单动态字符串)
定义
struct sdshdr {
//记录buf数组中已使用的字节数量
int len;
//记录buf数组中未使用的字节数量
int free;
//字节数组，用于保存字符串
char buf[];
}
应用场景
表示除了字面量以外的字符串。
对比C字符串优点
- 获取字符串长度直接避免了每次计算、直接读取,O(1)复杂度。
- 字符串连接时动态扩容，避免引发缓冲区不足的错误。
- 减少修改字符串时带来的内存重分配次数，采用空间预分配、惰性空间释放策略。
- 二进制安全，以len的值计算长度而不是\0判断结尾。
- 兼容部分C字符串函数。
| C字符串 | SDS |
|---|---|
| O(N)获取字符串长度 | O(1)获取长度 |
| API不安全，可能缓冲区溢出 | API安全不会造成缓冲区溢出 |
| 修改字符串N次必然执行N次内存重分配 | 最多执行N次 |
| 只保存文本数据 | 可以保存文本或者二进制 |
| 使用string.h所有函数 | 可使用一部分函数 |
链表
定义
typedef struct listNode{
struct ListNode * prev;
struct ListNode *next;
void * value;
} listNode;
typedef struct list {
//表头
listNode * head;
//表尾节点
listNode * tail;
// 链表包含节点数量
unsigned int long;
//节点复制函数
void *(*dup)(void*ptr);
//节点释放函数
void *(*free)(void*ptr);
//节点值对比函数
int (*match)(void*ptr,void*key);
}list;
字典 （symbol table）
哈希表
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 _tu64;
int64 _ts64;
}v;
//指向下个哈希表节点，形成链表
strcut dictEntry *next;
}dictEntry
redis的字典
typedef struct dict{
//type和privdata属性是针对不同类型的键值对，创建多态字典。
dictType * type;
void * privdata;
// 哈希表
dictht ht2[];
// rehash时候的索引值，没有rehash操作等于-1
int trehashidx;
}
typedef struct dictType{
//计算哈希值的函数
unsigned int (*hashFunction)(const void * key);
//复制key的函数
void *(*keyDup)(void*privdata,const void*key);
// 复制值的函数
void*(*valDup)(void*privdata,const void *obj);
//对比key
int*(*keyCompare)(void *privdata,void*key1,void*key2);
//销毁key
void(*keyDestruct)(void * privdata,void *key);
//销毁value
void(*valDestruct)(void * privdata,void *obj);
}dictType
{
"id":1234,
"shop_id":'12345'
}
字典被广泛用于Redis的各种功能，包括数据库和哈希键。
跳跃表
typedef struct zskiplistNode{
struct zskiplistLevel {
// 前进指针
struct zskiplistNode * forward;
//跨度
unsigned int span;
}level[];
// 后退指针
struct zskiplistNode * backward;
// 分值
double score;
// 成员对象
robj * obj;
}
跳跃表
typedef struct zskiplist {
//表头节点和表尾节点
struct skiplistNode * header, *tail;
// 表中节点的数量
unsigned long length;
// 表中层数最大的节点的层数
int level;
}zskiplist;
实现有序集合、集群节点中作内部数据结构。每次生成一个节点都会根据幂次定律确定层数（越大的数据出现的概率越小），跨度用来计算排位，再查找节点的过程中，将沿途访问过的所有跨度累计起来，就是目标节点再跳跃表中的排位。
整数集合
typedef struct intset{
// 编码方式
uint32_t encoding;
// 集合包含的元素数量
uint32_t length;
// 保存的元素的数量
int8_t contents[];
}intset;
整数集合是集合键的底层实现之一，底层以实现为数组，数组以有序、无重复的方式保存元素，有需要的时候会根据新添加元素的类型改变数组类型。只支持类型升级
不支持降级操作。
压缩列表
压缩列表是列表键和哈希键的底层实现之一，当一个列表键只包含少量的列表项目，
并且每个列表项要么是小整数值，要么就是长度比较短的字符串。redis就会使用压缩列表做底层实现。
| 属性 | 类型 | 长度 | 用途 |
|---|---|---|---|
| zlbytes | uint32_t | 4字节 | 记录占用的内存字节数：对压缩列表进行内存分配 |
| zltail | uint32_t | 4字节 | 记录压缩列表表尾节点距离起始地址有多少字节。 |
| zllen | uint16_t | 2字节 | 记录节点数量，小于uint16_max有效，等于时需要遍历计算。 |
| entryX | 列表节点 | 不定 | 压缩列表包含的各个节点，节点长度由节点保存的内容决定 |
| zlend | uint8_t | 1字节 | 特殊值，标记压缩列表的末端 |
压缩列表节点：
- previous_entry_length:以字节为单位，记录前一个节点长度。
- encoding:记录节点的content属性保存数据的类型以及长度。
- content：保存节点的值，可以是一个字节数组或者整数。
压缩列表是为节约内存开发的顺序数据结构，被用作列表键和哈希键的底层实现之一，添加新的节点到压缩列表或者删除节点，可能会引发连锁更新操作，但是出现的几率不高。
Redis对象
Redis对象基于上述基本数据结构组合实现，可以根据不同的场景设置不同的数据结构实现，从而优化对象再不同场景下的使用效率。Redis对象实现了基于引用技术的内存回收机制，程序不再使用某个对象的时候，这个对象所占用的内存就会被释放，并且基于引用计数实现了对象共享机制。Redis对象带有访问时间记录信息，计算数据库键空转市场，再服务器启用maxmemmoery功能，空转时长较大的key会被优先删除。
typedef struct redusObject {
// 类型
unsigned type:4;
// 编码
unsigned encoding:4;
// 指向底层实现数据结构的指针
void *ptr;
}
| 类型 | 编码 | 对象 |
|---|---|---|
| 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 | 使用跳跃表和字典实现的有序集对象 |
