首页
学习
活动
专区
工具
TVP
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往

彻底了解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的排序权重, 其结构如下图所示。

注意 性能优于平衡树

小明菜市场

  • 发表于:
  • 原文链接https://kuaibao.qq.com/s/20200708A0WA8U00?refer=cp_1026
  • 腾讯「腾讯云开发者社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 cloudcommunity@tencent.com 删除。

扫码

添加站长 进交流群

领取专属 10元无门槛券

私享最新 技术干货

扫码加入开发者社群
领券
http://www.vxiaotou.com