3.Redis数据结构与编码

redis支持数据结构

编码类型

编码结构

算法思想

编码类型特点与优势

String

raw-大于39个字节的字符串

//sds.h

struct sdshdr {

//记录sdshdr长度

int len;

//记录buf数组未使用字节数量

int free;

//字节数据 保存字符串

char buf[];

};

空间换时间

1.sds记录字符串长度，获取字符串长度为O(1),C语言不记录字符串长度其时间复杂度为O(N)

2.杜绝缓存区溢出，由于sds记录字符串长度，其字符串创建的时候分配好内存空间，不会导致溢出。

3.降低字符串操作内存分配次数，空间预分配，sds内存分配大于1M者分配N+1M空间，当sds内存不足1M分配2N内存空间。

4.惰性内存释放，sds在字符串缩短时候不会立刻释放其持有内存空间。

5.二进制安全 sds.buf保存一系列二进制数据，使redis不但能保存字符串而且可以保存音频、视频等文件

int-8个字节的长整型 

embstr-小于等于39个字节的字符串

Hash

dict-字典

//dict.h

//hash节点数据结构

typedef struct dictEntry {

// 键

void *key;

union {

//void指针可存储任何数据

void *val;

//数字类型存储引用 节约内存

uint64_t u64;

int64_t s64;

double d;

} v;

// 指向下个节点的指针

struct dictEntry *next;

} dictEntry;

/*操作函数*/

typedef struct dictType {

//计算hash值的函数

uint64_t (*hashFunction)(const void *key);

//复制键的函数

void *(*keyDup)(void *privdata, const void *key);

//复制值的函数

void *(*valDup)(void *privdata, const void *obj);

//对比键的函数

int (*keyCompare)(void *privdata, const void *key1, const void *key2);

//销毁键的函数

void (*keyDestructor)(void *privdata, void *key);

//销毁值的函数

void (*valDestructor)(void *privdata, void *obj);

} dictType;

/*hash表数据结构-作用方便路由*/

typedef struct dictht {

// hash表数组

dictEntry **table;

// hash表数据大小

unsigned long size;

// 指针数组掩码 用于计算索引值sizemask=size-1

unsigned long sizemask;

// 哈希表现有节点数量

unsigned long used;

} dictht;

/*hash主体结构体*/

typedef struct dict {

// 特定类型处理函数 指向dictType方法

dictType *type;

// 类型处理函数的私有数据

void *privdata;

// hash表数量为2

dictht ht[2];

// 记录rehashidx到哪一步 默认-1标示没有rehash

long rehashidx;

//正在遍历数

unsigned long iterators;

} dict;

数组链条结构-空间换时间

1.dict数据结构时间复杂度在O(1)-O(N)之间。

2.hash最大值2<<32的数字，足够大不超过int范围保证性能，很多中间件hash范围的选择。

3.数据结构理论基础，hash表性能优秀于链表，hash表最优时间复杂度为O(1), 链表时间复杂度O(N).

4. hash碰撞解决：redis对有相同hash值的key，使用单链表解决。

5.dictht负载因子=dictht.used/dictht.size,该值越大证明key冲突越大。默认该值大于5强制Rehash。

6.Rehash指redis在负载因子大于5的情况下，为了维护redis的性能需要对redis扩容，对redis ht[0]转移元素到ht[1], redis为保证高可用，不会一次性转移渐进式转移hash表。

7. dit结构体redis最大数据量为40亿（2<<32），如果大于这个数量推荐扩容key。

ziplist-压缩列表如下

略

数据在hash-max-ziplist-entries(元素数) 512

hash-max-ziplist-value(元素大小) 64范围内Hash使用ziplist编码

List

ziplist-压缩列表

//ziplist数据结构

typedef struct ziplist{

/*ziplist分配的内存大小*/

uint32_t bytes;

/*达到尾部的偏移量*/

uint32_t tail_offset;

/*存储元素实体个数*/

uint16_t length;

/*存储内容实体元素*/

unsigned char* content[];

/*尾部标识*/

unsigned char end;

}ziplist;

/*节点数据结构 ziplist.c*/

typedef struct zlentry {

/*前一个元素长度需要空间和前一个元素长度,这里可能触发连锁更新*/

unsigned int prevrawlensize, prevrawlen;

/*元素长度需要空间和元素长度*/

unsigned int lensize, len;

/*头部长度即prevrawlensize + lensize*/

unsigned int headersize;

/*元素内容编码*/

unsigned char encoding;

/*元素实际内容*/

unsigned char *p;

}zlentry;

双向链表-连续存储空间节约内存空间

ziplist编码数据结构：

1. ziplist时间复杂度在O(n)

2.ziplist数据结构是一个特殊数双向链表使用连续的内存空间。

3.ziplist利用连续的内存空间存储，内存使用率更低，如果满足下面条件，ziplist存储转化为quicklist存储。因为当list过大其触发 realloc概率变大，可能导致内存拷贝。 hash-max-ziplist-entries(元素数) 512

hash-max-ziplist-value(元素大小) 64

4.list数据结构主要是提高内存使用率的，其时间复杂度比较高，所以redis元素数大于64转化为quicklist结构存储。

5.ziplist每个节点大小在250-253之间超过后节点扩容。

quicklist-快速列表

/*qucklist.h数据结构*/

/*链结构*/

typedef struct quicklist {

quicklistNode *head;

quicklistNode *tail;

unsigned long count; /*ziplists元素总数 */

unsigned long len; /*quicklistNodes数目*/

int fill : 16; /*ziplist节点大小设置 */

unsigned int compress : 16; /*压缩深度设置*/

} quicklist;

/*节点结构*/

typedef struct quicklistNode {

struct quicklistNode *prev;

struct quicklistNode *next;

/*

*不设置recompress压缩参数指向ziplist结构

* 设置recompress压缩参数指向ziplistlzf结构

*/

unsigned char *zl;

/*ziplist长度*/

unsigned int sz; /* ziplist size in bytes */

/*ziplist 包含节点数 占16bytes长度*/

unsigned int count : 16; /* count of items in ziplist */

//ziplist是否压缩 1:未压缩 2: 被压缩使用LZF压缩算法

unsigned int encoding : 2; /* RAW==1 or LZF==2 */

//预留字段 2:表示ziplist做节点容器

unsigned int container : 2; /* NONE==1 or ZIPLIST==2 */

//查看压缩字段需要解压，recompress=1表示在适当机会在压缩回去

unsigned int recompress : 1; /* was this node previous compressed? */

//预留字段

unsigned int attempted_compress : 1; /* node can't compress; too small */

//扩展字段

unsigned int extra : 10; /* more bits to steal for future usage */

} quicklistNode;

/*节点引用对象 记录各层次节点信息*/

typedef struct quicklistEntry {

const quicklist * quicklist; //指向所属的quicklist对象

quicklistNode * node; //指向所属的quicklistNode对象

unsigned char * zi; //指向当前的ziplist

unsigned char * value; //指向zplist对象的字符串Value成员

long long longval; //指向ziplist中的整数Value成员

unsigned int sz; //当前ziplist对象的大小

int offset; //保存相对ziplist的偏移位置大小

} quicklistEntry;

快速列表-串连ziplist内存块

quicklist数据结构：

1.quicklist是在ziplist与linkedlist基础上构建的一种数据结构。

2.由于ziplist的内存空间是连续的会有很多内存碎片，quicklist将多个ziplist连接起来提供内存使用率。

3.由于quicklist是有多个ziplist构成的，所以单个ziplist规模不是很大当ziplist单节点发生连锁更新的时候降低影响

4.quicklist中ziplist节点大小和个数受ziplist配置决定

Set

hashtable

内部结构dict实现 略

intset

//intset.h

typedef struct intset {

//编码类型 int16_t、int32_t、int64_t

uint32_t encoding;

//最大长度 2<<32

uint32_t length;

//数组

int8_t contents[];

} intset;

intset-数组结构

intset数据结构：

1.redis特有的数据结构存储整形

2.编码类型不同的有序数组,其查找，修改，增加的时间复杂度为O(n)。

3. 其效率一般除掉集合交叉并场景，其他场景可以使用Zset代替。

4.其数据结构优点空间复杂度好节约空间

Zset

skiplist-跳跃表

/* server.h */

typedef struct zskiplistNode {

sds ele;

//分值

double score;

//后退指针

struct zskiplistNode *backward;

//层

struct zskiplistLevel {

//前进指针

struct zskiplistNode *forward;

//跨度

unsigned long span;

} level[];

} zskiplistNode;

//跳跃表结构体

typedef struct zskiplist {

//表头节点和尾部节点

struct zskiplistNode *header, *tail;

//表中节点数量

unsigned long length;

//链表最大层数

int level;

} zskiplist;

跳跃表-多层链表

skiplist数据结构：

1.skiplist时间复杂度O(logn)

2.跳跃表首先是一条按照分值排序的有序链表，为什么是有序的链表？有序链表可以让skiplist快速屏蔽无关层的遍历。

3.跳跃表插入时间复杂度是O(1)

4.跳跃表实现原理就是新插入的节点，有个随机的层数，每层和首尾节点建立链接，通过链接快速定位到目标元素。

5.跳跃表缺点：跳跃表通过层跳跃访问目标，也就是说明层是访问的快速通道，如果待访问的节点正好在访问目标层时间复杂度O(1),最坏的时间复杂度为O(层数节点数)+O(N)。所以，跳跃表强调链表有序，可以通过有序排查掉无效的层。

ziplist-压缩列表

略

数据结构

函数名称

作用

复杂度

String

sdsempty

创建一个只包含空字符串“”的sds

O(N)

sdsnew

根据给定的C字符串，创建一个相应的sds

O(N)

sdsnewlen

创建一个指定长度的sds，接受一个指定的C字符串作为初始化值

O(N)

sdsdup

复制给定的sds

O(N)

sdsfree

释放给定的sds

O(1)

sdsupdatelen

更新给定sds所对应的sdshdr的free与len值

O(1)

sdsMakeRoomFor

对给定sds对应sdshdr的buf进行扩展

O(N)

sdscatlen

将一个C字符串追加到给定的sds对应sdshdr的buf

O(N)

sdscpylen

将一个C字符串复制到sds中，需要依据sds的总长度来判断是否需要扩展

O(N)

sdscatprintf

通过格式化输出形式，来追加到给定的sds

O(N)

sdstrim

对给定sds，删除前端/后端在给定的C字符串中的字符

O(N)

sdsrange

截取给定sds，[start,end]字符串

O(N)

sdscmp

比较两个sds的大小

O(N)

sdssplitlen

对给定的字符串s按照给定的sep分隔字符串来进行切割

O(N)

ziplist

iplistNew

创建一个新的压缩列表。

O(1)

ziplistPush

创建一个包含给定值的新节点， 并将这个新节点添加到压缩列表的表头或者表尾。

平均O(N^2)

ziplistInsert

将包含给定值的新节点插入到给定节点之后。

O(N)

ziplistFind

在压缩列表中查找并返回包含了给定值的节点。

O(N^2)

ziplistNext

返回给定节点的下一个节点。

O(1)

ziplistPrev

返回给定节点的前一个节点。

O(1)

ziplistGet

获取给定节点所保存的值。

O(1)

ziplistDelete

从压缩列表中删除给定的节点。

平均O(N^2)

ziplistDeleteRange

删除压缩列表在给定索引上的连续多个节点。

平均O(N^2)

ziplistBlobLen

返回压缩列表目前占用的内存字节数。

O(1)

ziplistLen

返回压缩列表目前包含的节点数量。

节点数量小于 65535 时O(N)

PS：因为 ziplistPush 、 ziplistInsert 、 ziplistDelete 和 ziplistDeleteRange 四个函数都有可能会引发连锁更新(极端的节点空间扩容)， 所以它们的最坏复杂度都是O(N^2)

quicklist

quicklistCreat

创建 quicklist

O(1)

quicklistInsertAfter

在某个元素的后面添加数据

O(N)

quicklistInsertBeforer

在某个元素的前面添加数据

O(N)

quicklistReplaceAtIndex

替换某个元素

O(N)

quicklistDelEntry

删除单个元素

O(N)

quicklistDelRange

删除区间元素

O(N)

quicklistPushHead

头部插入元素

O(1)

quicklistPushTail

尾部插入元素

O(1)

dict

dictCreate

创建一个新字典

O(1)

dictAdd

添加新键值对到字典

O(1)

dictReplace

添加或更新给定键的值

O(1)

dictFind

在字典中查找给定键所在的节点

O(1)

dictFetchValue

在字典中查找给定键的值

O(1)

dictGetRandomKey

从字典中随机返回一个节点

O(1)

dictDelete

根据给定键，删除字典中的键值对

O(1)

dictRelease

清空并释放字典

O(N)

dictEmpty

清空并重置（但不释放）字典

O(N)

dictResize

缩小字典

O(N)

dictExpand

扩大字典

O(N)

dictRehash

对字典进行给定步数的 rehash

O(N)

dictRehashMilliseconds

在给定毫秒内，对字典进行rehash

O(N)

skiplist

zslCreate

创建一个新的跳跃表。

O(1)

zslFree

释放给定跳跃表，以及表中包含的所有节点。

O(N) N跳跃表长度

zslInsert

将包含给定成员和分值的新节点添加到跳跃表中。

O(N) N跳跃表长度

zslDelete

删除跳跃表中包含给定成员和分值的节点。

O(N) N跳跃表长度

zslGetRank

返回包含给定成员和分值的节点在跳跃表中的排位。

O(N) N跳跃表长度

zslGetElementByRank

返回跳跃表在给定排位上的节点。

O(N) N跳跃表长度

zslIsInRange

给定一个分值范围（range）， 比如 0 到 15 ， 20 到 28，诸如此类， 如果给定的分值范围包含在跳跃表的分值范围之内， 那么返回 1 ，否则返回 0 。

通过跳跃表的表头节点和表尾节点， 这个检测可以用O(1)复杂度完成

zslFirstInRange

给定一个分值范围， 返回跳跃表中第一个符合这个范围的节点。

O(N) N跳跃表长度

zslLastInRange

给定一个分值范围， 返回跳跃表中最后一个符合这个范围的节点。

O(N) N跳跃表长度

zslDeleteRangeByScore

给定一个分值范围， 删除跳跃表中所有在这个范围之内的节点。

O(N) N节点删除数量

zslDeleteRangeByRank

给定一个排位范围， 删除跳跃表中所有在这个范围之内的节点

O(N) N节点删除数量