redis中数据类型的底层结构

  • 时间:
  • 浏览:0
  • 来源:跟我学网络

最后发布:2020-08-19 14:16:19首次发布:2020-08-19 14:16:19

包含一个char数组,数组已使用字节数,未使用字节数。

对比C语言中的字符串,有以下优点。

  • 获取字符串长度O(1)的时间复杂度
  • 杜绝缓存溢出
  • 减少字符串的重新分配次数
  • 二进制安全,兼容C字符串函数

list为一个双向链表,表头节点,表尾节点,节点数等属性。

节点listNode,包含前置节点指针,后置节点指针,节点值指针属性。

使用哈希表作为底层实现与java的哈希表类似。哈希表中包含一个dicEntry数组,哈希表大小,掩码,已有节点数。dicEntry有key和value,还有指向下一个dicEntry的指针。

Redis的字典底层使用哈希表实现,每个字典通常有两个哈希表,一个平时使用,另一个用于rehash时使用,使用链地址法解决哈希冲突。



跳跃表其实是为了解决链表的查找效率低(O(N))的问题,而设计的一种数据结构。(排序好的数组虽然查询效率高(O(logN)),但是插入删除的效率低O(N))。如下所示,跳跃表的查询效率可以接近O(logN)。



跳跃表的特点:

①、搜索:从最高层的链表节点开始,跳跃式搜索。最低层包含所有元素。

②、插入:首先确定插入的层数,有一种方法是假设抛一枚硬币,如果是正面就累加,直到遇见反面为止,最后记录正面的次数作为插入的层数。当确定插入的层数k后,则需要将新元素插入到从底层到k层。

③删除:在各个层中找到包含指定值的节点,然后将节点从链表中删除即可,如果删除以后只剩下头尾两个节点,则删除这一层。

整数集合(intset)是Redis用于保存整数值的集合抽象数据类型,它可以保存类型为int16_t、int32_t 或者int64_t 的整数值,并且保证集合中不会出现重复元素。

压缩列表,并没有进行压缩,而只是按照一定规则编码在一块联连续的内存区域,目的是节省空间。

redis创建一个键值对时,至少会创建两个对象,一个键对象,一个值对象。每个对象都包含type类型,和 encoding编码属性。type也就是我们经常说的5种数据类型(字符串,列表,哈希,集合,有序集合)。

注意:在Redis中,键总是一个字符串对象,而值可以是字符串、列表、集合等对象,所以我们通常说的键为字符串键,表示的是这个键对应的值为字符串对象,我们说一个键为集合键时,表示的是这个键对应的值为集合对象。

各种数据类型对应的底层数据结构,可以通过查看其编码属性得知。



String类型:int(保存整数值),embstr(只分配一次内存,保存长度小于44字节的字符串),raw(分配两次内存,保存长度大于44字节的字符串)

列表对象:linkedlist,ziplist(元素小于512且每个元素长度小于64字节)

哈希对象:ziplist(元素小于512且每个元素长度小于64字节),字典

集合对象:intset(元素不超过512且每个元素都是证书),字典

有序集合:ziplist(保存元素小于128,所有元素长度小于64字节),skiplist(skiplist 编码的有序集合对象使用 zset 结构作为底层实现,一个 zset 结构同时包含一个字典和一个跳跃表,字典的键保存元素的成员,字典的值则保存成员的score;跳跃表节点的 object 属性保存元素的成员,跳跃表节点的 score 属性保存成员的score)

参考文章:

https://www.cnblogs.com/ysocean/p/9102811.html#_label0