彻底了解Redis基础数据结构

前言

Redis有五种数据类型,分别是(String, Hash,List,Set, Sorted Set)每种数据类型都提供了最少两种的内部编码格式,而且每个数据类型内部编码方式的选择对用户来说是完全透明的,Redis会根据数据选择最自适应的优化内部编码格式。
Redis是内存数据库。

String 字符串

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

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

内部结构

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

struct SDS<T> {
  T capacity; // 数组容量
  T len; // 数组长度
  byte flags; // 特殊标识位,不理睬它
  byte[] content; // 数组内容
}

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

字符串编码格式

  1. int编码(长度小于20),当保存的值是64位的有符号整数类型的时候会采用int编码,这个时候使用键值自增的操作,Redis启动时会预先建立10000个分别保存1-9999的redisObject变量作为共享对象,这就意味着如果set字符串的键值在0-1000之间的话,可以直接指向共享对象,而不需要再次建立新的对象,此时键值对不占用空间。
  2. embstr编码(长度小于44),对于嵌入式的String,从内存结构上说,就是字符串sds结构体与其对应的redisObject对象分配在同一块连续的内存空间,这就是字符串嵌入在redisObject对象之中一样。
  3. 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
}

如图所示

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

entry的内部实现

其内部实现如下所示

struct entry{
    int<var> prevlen;           //前一个 entry 的长度
    int<var> 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的排序权重,
其结构如下图所示。

注意 性能优于平衡树

发表评论

电子邮件地址不会被公开。 必填项已用*标注