美文网首页
彻底了解Redis基础数据结构

彻底了解Redis基础数据结构

作者: b335eb9201c3 | 来源:发表于2021-04-21 11:41 被阅读0次

    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

    注意 性能优于平衡树

    相关文章

      网友评论

          本文标题:彻底了解Redis基础数据结构

          本文链接:https://www.haomeiwen.com/subject/ftgalltx.html