Linux

redis数据结构

redis的数据结构主要有以下几种：SDS(simple dynamic string)，embstr(编码的简单动态字符串)，字典，链表(双端链表)，压缩列表，整数集合，跳表。

SDS的主要结构为：

1
2
3
4
5
6
7
8
9
struct sdshdr{
    //记录buffer中的存储数据的实际长度
	int len;
	//记录buffer当前还剩下的长度
	int free;

	//buffer，实际存储数据的数组,会在存储数据的最后面加一个'\0',以适应于系统的一些字符串处理函数
	char buf[];
}

SDS与C字符串的区别：

  1. 属性len可以使得SDS能够在常数时间内返回字符串的长度
  2. 杜绝缓冲区的溢出，C字符串不记录本身的长度，所以在字符串的复制、拼接(strcat)上面会出现溢出，而SDS有free属性，可以根据属性来确定还有没有空间可以允许安全的字符串操作，没有的话会自动的申请更大的内存空间，并复制原来的数据。
  3. 减少修改字符串所带来的内存重分配次数。由于C字符串没有预分配策略，所以每一次的字符串增加或减少操作都会造成内存的重分配。而SDS有内存预分配策略，所以可以减少相应的内存重分配次数。
  4. 二进制安全的。因为SDS是根据len来确定所存储的字符串的长度的，而不是硬性的根据’\0’来决定字符串的结尾，所以对于二进制等会在数据中出现’\0’的数据，SDS是安全的，可以完整的读取以及存储数据，而C字符串却不能。

链表

redis的链表采用的是双向链表的方式，每一个链表节点都有指向上一个和下一个节点的指针。链表由list数据结构来表示，主要负责管理链表，有链表头、链表尾、链表长度等属性。链表的节点就是简单的几个属性：节点值、上一个节点指针、下一个节点指针。

字典

redis使用字典来表示数据库，也用来作为哈希键的底层实现。哈希表采用数组加链表的方式来实现以及解决哈希冲突的问题。字典的结构与链表一样，有两个数据结构组成。一个是dictht，用来表示整个哈希表的具体信息，另一个数dictEntry，为哈希表的具体节点值，用来存储key
和value数据。每一个dictEntry都有一个对应的指针，来指向下一个哈希冲突的dictEntry。在dictht中，有两个dictEntry** ht[2]元素, 一个用来指向真是的哈希数组，一个在平时的值为nullptr。在哈希数组达到一定的饱和度或是太过于稀疏的时候，redis会进行rehash操作，此时会重新生成哈希数组，指向nullptr的属性会指向该新的数组起始地址，将原来的哈希表数据剪切到新的空间里面，剪切完成后，会将旧的属性赋值为nullptr。

rehash的操作有两种策略，一种是一次性操作，一次性将原有的数据剪切到新的空间里面。另外一种是渐进式的rehash，每次对于字典的操作，都会将对应的key以及value剪切到新的空间里面，该策略在对字典的操作，比如查找时，需要新旧两个哈希数组一起参与，在久的找不到的情况下查找新的。

跳跃表

与链表一样，跳跃表也由两种数据结构组成，redis.h/zskiplistNode和redis.h/zskiplist。zskiplist用来表示整个跳跃表的具体信息，zskiplistNode用来表示跳跃表的节点。

整数集合

整数结合用来保存整数值集合。具体的数据结构为：

1
2
3
4
5
6
7
8
typedef struct inset{
    //编码方式：INSET_ENC_INT16，INSET_ENC_INT32，INSET_ENC_INT64，用来表示content数组里面的数据的真实类型
	uint32_t encoding;
	//集合的元素数量
	uint32_t length;
	//保存集合的数组，数组里面存储的真实数据会根据encoding属性来确定，并不是根据content的int8_t类型来确定的。
	int8_t contents[];
}inset;

content数组中，各个元素按照值的大小递增排序，并且只出现一次。
当向整数集合插入新的元素，并且新元素的类型比原有的类型还大时，redis会对整数集合进行编码升级，所有的数据的类型都会升级为新的类型。所以需要对conetne执行新的内存操作以及数据剪切。由于新元素的值要么大于content中的任何值，要么小于content中的任何值，所以在新的content里面，新元素的位置要么在最后，要么在最前。

升级的好处
  1. 通过升级，整数集合可以存储不同类型的整数，由于C语言是静态类型语言，如果不升级的话，就需要有不同类型的数据结构。通过升级就可以直接使用一种数据结构来表示多种类型整数。
  2. 节约内存。为了能够存储多种数据类型，只在需要的时候才进行升级，这样可以节约内存，不然的话，需要一开始就定义最大的整数类型作为content
    的元素类型。

整数集合是没有降级的，只有升级，一旦升级后，编码就会一直保持升级后的编码，即使content中的元素值很小，也不会执行降级。

压缩列表

压缩列表是列表键和哈希键的底层实现之一。当一个列表键只包含少量列表项，并且每个列表项要么就是小整数值，要么就是长度比较短的字符串，那么redis就会使用压缩列表来做列表键的底层实现。另外，当一个哈希键只包含少量键值对时，并且每个键值对的键和值要么就是小整数值，要么就是长度比较短的字符串，那么redis就会使用压缩列表来做哈希键的底层实现。

1
2
3
4
5
6
7
8
9
10
11
12
redis> RPUSH lst 1 2 3 4 "hello" "world"
(integer)6

redis> OBJECT ENCODING lst
"ziplist"


redis> HMSET profile "name" "Jack" "age" 28 "Job" "Programmer"
OK

redis> OBJECT ENCODING profile
"ziplist"