Redis内部涉及 的数据结构

glcui

Redis就是内存中维持一个巨大的字典，字典的key节点及value节点是一个个数据结构。
在这里简单介绍一下Redis用到的数据结构。
1.简易动态字符串（sds）
Redis没有使用传统的C字符串形式，取而代之的是自己实现了一个简单动态字符串简易动态字符串结构，简称为SDS（Simple Dynamic Strings）。
SDS兼容C字符串的同时，带来了二进制安全、计算更有效率、杜绝缓冲区溢出等优点。
struct sdshdr {
/*字符串的长度。因为最后一个字节需为'\0'，所以也是buf已经使用的空间的长度-1*/
int len;
/*buf中剩余可用空间的长度*/
int free;
/*数据空间*/
char buf[];
};

"hello"的存储方式在内部就可能(小伙伴们考虑一下为啥是可能呢？)表示成下面的形式

2.双链表（adlist）
双链表是一个基本的数据结构，样子就像一串回形针。
Redis中的双链表跟小伙伴们在《数据结构》中学到的双链表一模一样，在此就不详细介绍了。
放个示意图

3.字典（dict）
作为key-value数据库，上面提到过整个Redis就是一个巨大的字典，字典的设计决定了此类产品的成败。
Redis的字典由字典类型特定函数和2个哈希表表组成。特定函数包括计算哈希值、复制键\值等一些列函数组成，两个哈希表用来实现渐进式 rehash。
typedef struct dict {
/*类型特定函数组成的结构体*/
dictType *type;
/*私有数据*/
void *privdata;
/*两个哈希表*/
dictht ht[2];
/*是否在进行rehash中*/
int rehashidx;
/*目前正在运行迭代器的数量*/
int iterators;
} dict;

哈希表hash算法采用比较流行的MurmurHash2算法，对于规律性较强的key，节点更加“分布均匀”。
用链表法处理hash碰撞，将多个哈希值相同的节点串连在一起。
渐进式 rehash是Redis字典特性，防止一次rehash导致系统资源使用增高可能导致的卡死。
非rehash时，数据会放到哈希表ht[0]；rehash时，新插入的数据会放置到ht[1]，同时每次字典操作都会从ht[0]移动一定数量的哈希表节点到ht[1]，直到ht[0]节点数变为0，
然后执行ht[0]=ht[1]，重置ht[1]。
示意图为正在rehash的字典的示意

4.跳表（skiplist）
跳表是种偷懒的设计,用来替代平衡树，跳表的算法有同平衡树一样的渐进的预期时间边界，并且更简单、更快速和使用更少的空间。
跳表是按照层级来建造的，每层皆是一个链表，上层是下层的快速跑道可以更快的定位数据所在的位置范围，查询数据时逐层定位缩小范围直至范围变为1或者0。
typedef struct zskiplistNode {
/* 成员对象,即存储的数据*/
robj *obj;
/*分值,用来排序*/
double score;
/*后退指针,用于跳表的从尾到头的遍历*/
struct zskiplistNode *backward;
/*层级*/
struct zskiplistLevel {
/*前进指针,指向本层的下一个节点*/
struct zskiplistNode *forward;
/* 跨度,记录到本层下一个节点的距离*/
unsigned int span;
} level[];
} zskiplistNode;

各个level节点记录前进指针的同时也会记录到下一个节点的跨度，遍历跳表只需按照跨度等于1从头到尾访问节点即可。

5.压缩列表（ziplist）
压缩列表是Redis为解决内存而设计的存储方式，到满足一定的条件（如元素的个数少、key或者value的长度短）的情形下，List和字典都有可能使用压缩列表存储。
压缩列表的存储结构如下：



zlbytes 记录整个压缩表占用的字节数
zltail 记录压缩列表尾节点距离压力表第一个字节地址的偏移
zllen 表示压缩节点的个数
zlentry 为压缩表节点
zlend 压缩表结尾特殊字节，为0xFF
zlentry的结构如下
typedef struct zlentry {
/*prevrawlen ：前置节点的长度 ,prevrawlensize ：编码 prevrawlen 所需的字节大小*/
unsigned int prevrawlensize, prevrawlen;
/*len ：当前节点值的长度,lensize ：编码 len 所需的字节大小*/
unsigned int lensize, len;
/*当前节点 header 的大小，等于 prevrawlensize + lensize*/
unsigned int headersize;
/*当前节点存储何种类型的数据*/
unsigned char encoding;
/*数据指针*/
unsigned char *p;
} zlentry;

6.整数集合（intset）
当集合中只有整数时，Redis会使用下面的结构来存储这些整数。
typedef struct intset {
/*编码方式*/
uint32_t encoding;
/*包含的元素个数*/
uint32_t length;
/*集合中的元素，会根据编码方式来决定一个元素占用多少个字节*/
int8_t contents[];
} intset;