彻底了解Redis基础数据结构

String 字符串

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

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

内部结构

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

struct SDS {

T capacity; // 数组容量

T len; // 数组长度

byte flags; // 特殊标识位，不理睬它

byte[] content; // 数组内容

}

其中capacity表示所分配的数组长度，len表示字符串的实际长度。content保存的就是字符串的内容，和C语言一样以0x\0作为结束字符，但是这个结束字符不包括在len中。

字符串编码格式

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

embstr编码（长度小于44），对于嵌入式的String，从内存结构上说，就是字符串sds结构体与其对应的redisObject对象分配在同一块连续的内存空间，这就是字符串嵌入在redisObject对象之中一样。

raw编码（长度大于44的）这个时候，redisObject内存不在连续，采用指针的形式，实现连接。

list列表

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

内部结构

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

内部编码

struct ziplist{

int32 zlbytes;          //压缩列表占用字节数

int32 zltail_offset;    //最后一个元素距离起始位置的偏移量,用于快速定位到最后一个节点

int16 zllength;         //元素个数

T[] entries;            //元素内容

int8 zlend;             //结束位 0xFF

}

如图所示

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

entry的内部实现

其内部实现如下所示

struct entry{

int prevlen;           //前一个 entry 的长度

int encoding;          //元素类型编码

optional byte[] content;    //元素内容

}

增加元素

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

如下图所示

如下所示的数据结构

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也是一致的，同样是数组+链表的二维结构，在一维发生碰撞的时候，会使用碰撞的元素把链表串接起来。

内部结构

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的排序权重， 其结构如下图所示。

注意 性能优于平衡树

小明菜市场