设为首页 - 加入收藏 鹤壁站长网 (http://www.0392zz.com)- 国内知名站长资讯网站,提供最新最全的站长资讯,创业经验,网站建设等!
热搜: 2019 产业 优化 服务器
当前位置: 首页 > 运营中心 > 建站资源 > 优化 > 正文

Redis基本类型及其数据结构

发布时间:2019-09-04 07:31 所属栏目:[优化] 来源:xy的技术圈
导读:以前在使用Redis的时候,只是简单地使用它提供的基本数据类型和接口,并没有深入研究它底层的数据结构。最近打算重新学习梳理一下Redis方面的知识,所以打算从介绍Redis的基本类型及其数据结构入手。 redisObject Redis的key是顶层模型,它的value是扁平化

以前在使用Redis的时候,只是简单地使用它提供的基本数据类型和接口,并没有深入研究它底层的数据结构。最近打算重新学习梳理一下Redis方面的知识,所以打算从介绍Redis的基本类型及其数据结构入手。

Redis基本类型及其数据结构

redisObject

Redis的key是顶层模型,它的value是扁平化的。Redis中,所有的value都是一个object,它的结构如下:

  1. typedef?struct?redisObject?{?
  2. ?unsigned?[type]?4;?
  3. ?unsigned?[encoding]?4;?
  4. ?unsigned?[lru]?REDIS_LRU_BITS;?
  5. ?int?refcount;?
  6. ?void?*ptr;?
  7. }?robj;?

简单介绍一下这几个字段:

  • type:数据类型,就是我们熟悉的string、hash、list等。
  • encoding:内部编码,其实就是本文要介绍的数据结构。指的是当前这个value底层是用的什么数据结构。因为同一个数据类型底层也有多种数据结构的实现,所以这里需要指定数据结构。
  • REDIS_LRU_BITS:当前对象可以保留的时长。这个我们在后面讲键的过期策略的时候讲。
  • refcount:对象引用计数,用于GC。
  • ptr:指针,指向以encoding的方式实现这个对象的实际地址。
Redis基本类型及其数据结构

string

在Redis内部,string类型有两种底层储存结构。Redis会根据存储的数据及用户的操作指令自动选择合适的结构:

  • int:存放整数类型;
  • SDS:存放浮点、字符串、字节类型;
  1. SDS:?简单动态字符串?simple?dynamic?string?

SDS

SDS的内部数据结构:

  1. typedef?struct?sdshdr?{?
  2. ?//?buf中已经占用的字符长度?
  3. ?unsigned?int?len;?
  4. ?//?buf中剩余可用的字符长度?
  5. ?unsigned?int?free;?
  6. ?//?数据空间?
  7. ?char?buf[];?
  8. }?

可见,其底层是一个char数组。buf最大容量为512M,里面可以放字符串、浮点数和字节。所以你甚至可以放一张序列化后的图片。它为什么没有直接使用数组,而是包装成了这样的数据结构呢?

因为buf会有动态扩容和缩容的需求。如果直接使用数组,那每次对字符串的修改都会导致重新分配内存,效率很低。

buf的扩容过程如下:

  • 如果修改后len长度将小于1M,这时分配给free的大小和len一样,例如修改过后为10字节, 那么给free也是10字节,buf实际长度变成了10 + 10 + 1 = 21byte
  • 如果修改后len长度将大于等于1M,这时分配给free的长度为1M,例如修改过后为30M,那么给free是1M.buf实际长度变成了30M + 1M + 1byte?
Redis基本类型及其数据结构

惰性空间释放指的是当字符串缩短时,并没有真正的缩容,而是移动free的指针。这样将来字符串长度增加时,就不用重新分配内存了。但这样会造成内存浪费,Redis提供了API来真正释放内存。

list

list底层有两种数据结构:链表linkedlist和压缩列表ziplist。当list元素个数少且元素内容长度不大时,使用ziplist实现,否则使用linkedlist。

链表

Redis使用的链表是双向链表。为了方便操作,使用了一个list结构来持有这个链表。如图所示:

Redis基本类型及其数据结构
  1. typedef?struct?list{?
  2. ?//表头节点?
  3. ?listNode?*head;?
  4. ?//表尾节点?
  5. ?listNode?*tail;?
  6. ?//链表所包含的节点数量?
  7. ?unsigned?long?len;?
  8. ?//节点值复制函数?
  9. ?void?*(*dup)(void?*ptr);?
  10. ?//节点值释放函数?
  11. ?void?*(*free)(void?*ptr);?
  12. ?//节点值对比函数?
  13. ?int?(*match)(void?*ptr,void?*key);?
  14. }list;?

data存的其实也是一个指针。链表里面的元素是上面介绍的string。因为是双向链表,所以可以很方便地把它当成一个栈或者队列来使用。

压缩列表

与上面的链表相对应,压缩列表有点儿类似数组,通过一片连续的内存空间,来存储数据。不过,它跟数组不同的一点是,它允许存储的数据大小不同。每个节点上增加一个length属性来记录这个节点的长度,这样比较方便地得到下一个节点的位置。

Redis基本类型及其数据结构

上图的各字段含义为:

  • zlbytes:列表的总长度
  • zltail:指向最末元素
  • zllen:元素的个数
  • entry:元素的内容,里面记录了前一个Entry的长度,用于方便双向遍历
  • zlend:恒为0xFF,作为ziplist的定界符

压缩列表不只是list的底层实现,也是hash的底层实现之一。当hash的元素个数少且内容长度不大时,使用压缩列表来实现。

hash

hash底层有两种实现:压缩列表和字典(dict)。压缩列表刚刚上面已经介绍过了,下面主要介绍一下字典的数据结构。

字典

【免责声明】本站内容转载自互联网,其相关言论仅代表作者个人观点绝非权威,不代表本站立场。如您发现内容存在版权问题,请提交相关链接至邮箱:bqsm@foxmail.com,我们将及时予以处理。

网友评论
推荐文章