struct sdshdr{
// 记录 BUF 数组中已使用字节的数量 = SDS 所保存字符串的长度
int len;
// 记录 BUF 数组中未使用字节的数量
int free;
// 字节数组 用于保存字符串
char buf[];
};
C字符串 | SDS | |
---|---|---|
获取长度的时间复杂度 | O(N) | O(1) |
API安全性 | 不安全,可能会造成缓冲区溢出 | 安全 |
内存分配 | 修改字符串长度N次必须执行N次内存重分配 | 修改字符串长度N次最多执行N次内存重分配 |
属性 | 只能保存文本数据 | 可以保存文本或者二进制数据 |
字典使用哈希表作为其底层实现
typedef struct dictEntry{
// 键
void *key;
// 值
union{
void *val;
uint64_tu64;
int64_ts64;
}v;
// 指向下一个哈希节点
struct dictEntry *next;
}dictEntry;
typedef struct dictht{
// 哈希表数组
dictEntry **table;
// 哈希表大小
unsigned long size;
// 哈希表大小掩码 计算索引值使用 size - 1
unsigned long sizemask;
// 该哈希表已存在节点数量
unsigned long used;
}dictht;
typedef struct dict{
// 类型特定函数 诸如,复制、比较、销毁等
dictType *type;
// 私有数据
void *privdata;
// 哈希表
dictht ht[2];
// rehash 索引 >=0 时表示在工作 =-1 时表示未工作
int rehashidx;
}dict;
typedef struct dictType{
// 计算哈希值的函数
unsigned int (*hashFunction)(const void *key);
// 复制键的函数
// 复制值的函数
// 对比键的函数
// 销毁键的函数
// 销毁值的函数
}dictType;
链表结构,对于相同键的数据,使用 next 指针来形成链表
rehash 是什么,如何作用?
即使有链表来处理键冲突,但是当节点数量远远大于 size 时,如果不扩充哈希表规模,请自行想象。这也是 rehash 的存在意义,笔者认为这也是 redis 扩展性的展现。
rehash 在哪些场景被触发?
rehash 规模判定
无论是收缩还是扩展,size 的大小均为 2 的 N 次方,N 的取值服从满足公式的最小值 (2的N次方 > used)
rehash 的渐进式执行
| 主要数据结构 |
| :------------: |
| 简单动态字符串 |
| 链表 |
| 字典 |
| 跳跃表 |
| 整数集合 |
| 压缩列表 |
类型 | 编码 | 底层实现 |
---|---|---|
字符串对象 | REDIS_ENCODING_INT | long类型的整数 |
字符串对象 | REDIS_ENCODING_EMBSTR | embstr 编码的 简单动态字符串 |
字符串对象 | REDIS_ENCODING_RAW | 简单动态字符串 |
列表对象 | REDIS_ENCODING_ZIPLIST | 压缩列表 |
列表对象 | REDIS_ENCODING_LINKEDLIST | 链表 |
哈希对象 | REDIS_ENCODING_ZIPLIST | 压缩列表 |
哈希对象 | REDIS_ENCODING_HT | 字典 |
集合对象 | REDIS_ENCODING_INTSET | 整数集合 |
集合对象 | REDIS_ENCODING_HT | 字典 |
有序集合对象 | REDIS_ENCODING_ZIPLIST | 压缩列表 |
有序集合对象 | REDIS_ENCODING_SKIPLIST | 跳跃表 |
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。