在我们日常开发使用中,常接触到的redis数据结构一般有 string、list、hash、set、zset五种,这五种数据结构在redis中其实对应的是五种不同的对象类型,
每个对象的底层实现都是不同的,有时候list、hash、zset底层的实现其实都是一样的,但为什么要区分开呢?当然不同的对象类型不止一种底层实现,本篇文章先看
下底层的几种数据结构:SDS、list、dict、skiplist、intset、ziplist。

简单动态字符串(SDS)

1
2
3
4
5
6
7
8
struct sdshdr{
//真实值长度
int len;
//可用空间长度
int free;
//数据存储空间
char buf[];
}

  以上为SDS的数据结构,len属性记录的字符的长度,free属性记录当前申请空间剩余的大小,buf属性为记录真实值。

  redis在更新字符串的时候会维护len属性,因此在获取字符串长度操作时间复杂度为o(1)

  redis在更新字符串的时候会维护free属性,在执行类似于字符串追加的操作时,会根据该属性判断剩余空间是否足够承载新的字符串,不够时自动扩容,能够有效的
避免缓冲区溢出问题。

  空间预分配:对字符串执行追加操作且需要扩容时,如果len的值小于1M,程序将为其分配同等大小的free空间;如果len值大于1M,则分配1M的free空间。通过空间
预分配可以减少内存重分配次数,提高执行效率。

  惰性释放:对字符串执行追加缩短操作时,redis不会立即释放多余的空间,而是通过free属性记录下来以便日后使用

  二进制安全:redis只会在字符串最末尾加上’/0’截止符,不会像C一样识别字符串中的截止符;在末尾加入C的截止符是为了能够使用部分C库。

链表(list)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
typedef struct list{
//表头节点
listNode *head;
//表尾节点
listNode *tail;
//链表所包含的节点数量
unsigned long len;
//节点值复制函数
void *(*dup)(void *ptr);
//节点值释放函数
void (*free)(void *ptr);
//节点值对比函数
int (*match)(void *ptr,void *key);
}

typedef struct listNode{
struct listNode *prev;
struct listNode *next;
void *value;
}

  以上就是list的数据结构,这是一个无环的双向链表,而redis对双向链表又做了一层封装,以便以常数级的时间复杂度获取头尾节点和链表长度

字典(dict)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

//字典
typedef struct dict{
//类型特定函数 其中有计算hash值的函数,复制键值函数,销毁键值函数,对比键函数
dictType *type;
//私有数据
void *privdata;
//哈希表
dictht ht[2];
//rehash索引值,当rehash不在进行时,值为-1
int trehashidx;
}

//哈希表
typedef struct dictht{
//哈希表数组
dictEntry **table;
//哈希表大小
unsigned long size;
//哈希表大小掩码,用于计算索引值 =size-1
unsigned long sizemark;
//哈希表已有的节点数量
unsigned long used;
}

//哈希表节点
typedef struct dictEntry{
//键
void *key;

//值 可以是一个指针,一个uint64_t整数,一个int64_t整数
union{
void *val;
uint64_t u64;
int64_t s64;
}v;
//下个节点,哈希值相同的键值对用next指针指向下一个,用于解决键冲突
struct dictEntry *next;
}

  元素插入:通过dictType中的hashFunction函数计算(使用MurmurHash算法)hash值,然后根据hash值和sizemark计算索引值,最后将值放入相应的位置
  键冲突:在dictEntry结构中有个next属性,该属性将冲突的键节点连成一个单向链表(链地址法)
  rehash
Q1:为什么要rehash?
A1:当键值对数据量很大的时候,负载因子(ht[0].used/ht[0].size)会大于1或小于0.1成为一个不合理的值,为了维持负载因子的均衡态,所以需要rehash。可以将其理解为逻辑上的缓冲区溢出或者空间浪费
Q2:什么时候需要rehash?
A2:服务器没有执行BGSAVE或者BGREWRITEAOF命令且负载因子大于1;服务器执行那两个命令且负载因子大于5.
Q3:为什么执行BGSAVE或者BGREWRITEAOF命令时负载因子可以大于5?
A3:因为在执行以上命令的时候系统会为当前进程创建子进程,且子进程会采用写时复制技术优化效率;提高负载因子值可以避免不必要的内存写入。
Q4:redis如何进行rehash?
A4:创建ht[1]哈希表,扩容时大小为ht[0].used*2临近2^n的值,即ht[0].used=20,ht[1].size=64;ht[0].used=15,ht[1].size=32;缩容时大小为ht[0].used临近2^n的值 然后将ht[0]中的键值对从新计算索引放到ht[1]中,全部rehash完成之后ht[1]变成ht[0],ht[0]变成ht[1]。
Q5:数据量很大时扩容会不会产生停顿,这样很影响效率吧?
A5:对的,数据量很大是的确会产生停顿,所以redis采用渐进式扩容。
Q6:什么是渐进式扩容?
A6:在对字典进行操作时会附带一次rehash操作,字典中有个trehashidx属性,操作的就是该属性对应的索引上的键值对,每操作一次该值+1;
Q7:在rehash过程中执行增删查操作怎么办?
A7:这时候,会维护ht[0]和ht[1]两个hash表,增加都去ht[1],删查改,一次从两个hash表中找
Q8:我是不是问题很多?
A8:对的

整数集合(intset)

1
2
3
4
5
typedef struct intset{
uint32_t encoding;
uint32_t length;
int8_t contents[];
}
数组以有序、无重复的方式保存集合元素
可以动态更改数组的类型

压缩列表(ziplist)

  zlbytes|zltail|zlen|entry1|entry2|...|entryN|zlend

  为了提高存储效率将ziplist设计成一个经过特殊编码的双向链表。ziplist可以用于存储字符串或整数,其中整数是按真正的二进制表示进行编码的,而不是编码成字符串序列。
它能以O(1)的时间复杂度在表的两端提供push和pop操作

跳跃表(skiplist)

```c typedef struct zskiplist{ //表头节点和表尾节点 新建跳跃表的时候默认初始化头结点层数是32 structz skiplistNode *header,*tail; //表中节点的数量 unsigned long length; //表中层数最大的节点层数 int level; }
typedef struct zskiplistNode{
    //后退指针
    struct zskiplistNode *backward;
    //分值(每个节点按照分值大小顺序排列)
    double score;
    //成员对象
    robj obj;
    //层 每个元素都包含一个指向其他节点的指针
    //层数是在新插入节点的时候,根据幂次定律生成一个随机数[1,32]
    struct zskiplistLevel{
        //前进指针
        struct zskiplistNode *forward;
        //跨度
        unsigned int span;
    }
}

```
  说明:skiplist 和 zskiplist其实不太一样,redis中对skiplist做了一些改进,比如:使用字典存储元素分值采取skiplist和dict结合,具体对比可自行寻找资料查阅
  应用:
1.有序键集合->zset
2.集群节点中用作内部数据结构