String 字符串

Redis字符串是简单动态的字符串，是可以修改的字符串，内部结构上实现了类似于Java的ArrayList，采用预分配冗余空间的方式来减少内存的频繁分配。如下图所示

image.png

如图所示，内部为当前字符串实际分配的空间，一般是要高于实际字符串长度的len。当字符串长度小于1M的时候，扩容都是加倍现有的空间，如果超过1M，扩容时一次只会多扩容1M的空间，需要注意的是字符串的最大长度为512M。

内部结构

在内存中以字节数组的形式存在，数组的结构是带有长度信息的字节数组。其C语言形式如下

struct SDS<T> { T capacity; // 数组容量 T len; // 数组长度 byte flags; // 特殊标识位，不理睬它 byte[] content; // 数组内容}其中capacity表示所分配的数组长度，len表示字符串的实际长度。content保存的就是字符串的内容，和C语言一样以0x\0作为结束字符，但是这个结束字符不包括在len中。

字符串编码格式

image.png

int编码（长度小于20），当保存的值是64位的有符号整数类型的时候会采用int编码，这个时候使用键值自增的操作，Redis启动时会预先建立10000个分别保存1-9999的redisObject变量作为共享对象，这就意味着如果set字符串的键值在0-1000之间的话，可以直接指向共享对象，而不需要再次建立新的对象，此时键值对不占用空间。

image.png

embstr编码（长度小于44），对于嵌入式的String，从内存结构上说，就是字符串sds结构体与其对应的redisObject对象分配在同一块连续的内存空间，这就是字符串嵌入在redisObject对象之中一样。raw编码（长度大于44的）这个时候，redisObject内存不在连续，采用指针的形式，实现连接。list列表

Redis列表相当于Java语言的LinkedList，它是双向链表而不是数组，意味着List的插入和删除操作相当的快，时间复杂度O(1)，获取头结点和尾结点也会相当的快，但是索引定位由于需要遍历链表，导致速度很慢，尝尝用作消息队列。当列表最后出来一个元素之后，数据结构将会被自动删除，内存回收。

内部结构

Redis内部结构不是简单的双向链表，在数据量少的时候作为一块连续的内存，数据量多的时候会变成链表的结构，后来因为链表需要指针的内存太多，所以采用了ziplist+链表的混合结构，称之为快速链表。

内部编码

struct ziplist<T>{ int32 zlbytes; //压缩列表占用字节数 int32 zltail_offset; //最后一个元素距离起始位置的偏移量,用于快速定位到最后一个节点 int16 zllength; //元素个数 T[] entries; //元素内容 int8 zlend; //结束位 0xFF}如图所示

image.png

其中，ztail_offset 可以快速定位到最后一个节点，这样可以实现倒序遍历，ziplist支持双向便利。

entry的内部实现

其内部实现如下所示

struct entry{ int<var> prevlen; //前一个 entry 的长度 int<var> encoding; //元素类型编码 optional byte[] content; //元素内容}增加元素

后期版本都使用了quickList，因为zipList对于内存空间耗费过大，所以都使用了quickList

如下图所示

image.png

如下所示的数据结构

struct quicklist{ quicklistNode* head; //指向头结点 quicklistNode* tail; //指向尾节点 long count; //元素总数 int nodes; //quicklistNode节点的个数 int compressDepth; //压缩算法深度 LZF ...}把每个zipList进行切分，使用quicList作为其中的一部分，其代码如上所示。其中quicklist内部默认单个ziplist长度为8k直接，超过这个字节会重新启动一个ziplist

hash字典

Redis中的字典相当于Java的HashMap，其内部结构与HashMap也是一致的，同样是数组+链表的二维结构，在一维发生碰撞的时候，会使用碰撞的元素把链表串接起来。

image.png

内部结构

struct dictEntry { void* key; void* val; dictEntry* next; // 链接下一个 entry}struct dictht { dictEntry** table; // 二维 long size; // 第一维数组的长度 long used; // hash 表中的元素个数 ...}第一维保存的是数组，第二维保存的是链表，数组中保存的是第二个链表的第一个元素指针。

关于扩容

当hash表中的元素个数在等于第一维的数组长度的时候，就会进行扩容，扩容的新数组是原数组大小的2倍。

set 集合

redis集合相当于java里的hashset，其内部的键值对是无序的唯一的，其内部实现相当于hash，但是和hash不同的是，所有的value都是一个值为NULL。

zset 有序集合

常用的场景为保存粉丝的列表，value的是粉丝的用户ID，score是关注的时间，。其是一个set，保证内部value的唯一性，另外一方面给每个value赋予一个score，代表value的排序权重， 其结构如下图所示。

image.png

注意 性能优于平衡树