江苏龙网

  1. 主页 > 生活百科 > >

Redis底层数据结构解密( 二 )

Redis


 
3.4 LZF压缩
快速列表ziplist为了push与pop操作的效率默认首尾节点不进行LZF压缩,如果需要设置更多节点不进行LZF压缩可以通过redis.conf配置文件中1099行list-compress-depth 0参数定义
 
四：Dict
redis中的hash、set等对象都有使用到字典这个数据结构,字典底层实现使用哈希表的结构 。字典中主要掌握它的渐进式hash,结构源码位置位于dict.h文件中
 
4.1 字典结构
typedef struct dict {
dictType *type;
void *privdata;
dictht ht[2];
long rehashidx;
} dict;
 
属性名称作用含义
type 自定义一些操作的方法,拷贝key、拷贝value、销毁key、销毁value等
privdate创建dict时传入,用于某些特殊操作回传给调用函数
ht [0]用于数据存储,[1]用于rehash变更
rehashidx表示rehash进度,-1表示未进行rehash
4.2 哈希表结构
typedef struct dictht {
dictEntry **table;
unsigned long size;
unsigned long sizemask;
unsigned long used;
} dictht;
 
属性名称作用含义
tablehash表节点
size hash表大小
sizemark哈希表大小掩码,计算索引值 。大小等于size -1
used哈希表已有的节点数量
4.3 哈希表节点结构
typedef struct dictEntry{
void *key;
union{
void *val;
uint64_tu64;
int64_ts64;
}v;
struct dictEntry *next;
}dictEntry
 
属性名称作用含义
key 保存数据的key值
union值对象,可以是一个对象,因为有个对象空指针或者是uint64、int64的整数
next 指向下一个Entry的指针,形成一个链表
4.4 渐进式rehash
字典的rehash操作数据量过大时并不是一次完成,而是分批次逐渐进行
rehash过程中新插入字典数据放在[1]哈希表中,并将原[0]中数据重新进行hash计算加入[1]中 。读操作将会读取[0]、[1]两个哈希表
rehash过程标志使用dict中属性rehashidx标识
rehash采用cow写时复制技术
五：Intset
redis中常用对象set会用到的底层数据结构
 
5.1 整数集合特点
1：内容全是数字
2：内存连续
3：元素有序,不可重复
5.2 Intset结构
typedef struct intset{
uint32_t encoding;
uint32_t length;
int8_t contents[];
}intset;
 
属性名称作用含义
encoding整数集合可以有三种编码方式16、32、64
length整数集合数组中保存的元素个数
contents从小到大保存的整数集合中的元素
六：ZipList
zset中用到的一个数据结构,性能可以和红黑树、AVL树不相上下

Redis底层数据结构解密

文章插图
 
6.1 跳跃表结构
typedef struct zskiplist{
//表头结点和尾节点
structz skiplistNode *heade,*tail;
//表中节点数量
unsigned long length;
//表中层数最大的节点的层数
int level;
}zskiplist;
 
属性名称作用含义
head跳跃表头结点
tail 跳跃表尾节点
length跳跃表节点数量,表头结点不记录在里面
level 跳跃表最大层数,不记录表头节点
6.2 跳跃表节点
typedof struct zskiplistNode{
//层
struct zskiplistNode{
//前进指针
struct zskiplistNode *forward;
//跨度
unsihned int span;
}level[];
//后退指针
struct zskiplistNode *backward;
//分值
double score；
//成员对象
robj *obj;
}zsikplistNode;
 
属性名称作用含义
zskiplistNode集合记录该节点位于的每一层
forward 每一层节点对应的下一个节点
span 距离下一个节点需要跨越的层数
backward 后退指针
score 节点分数值
obj 跳跃表节点保存的对象

【Redis底层数据结构解密】


推荐阅读


上一篇：什么是接口幂等性？为什么会产生这个问题？如何保证接口幂等性？

下一篇：HotStuff算法详解