引言
Redis是一款基于键值对的数据结构存储系统，它的特点是基于内存操作、单线程解决命令、IO多路复用模型解决网络申请、键值对存储与简略丰盛的数据结构等等
这篇文章次要围绕Redis中的对象与数据结构来具体阐明键值对存储与简略丰盛的数据结构这两大特点
Redis中的数据以Key,Value键值对的模式存储在字典中，字典的实现是哈希表
键Key只能应用字符串对象来示意，值Value可能应用其余所有对象
对象与数据结构
Redis中存在丰盛的对象，罕用的对象（数据类型）有字符串对象string、列表对象list、散列对象hash、汇合对象set、有序汇合对象zset等
还有其余的数据类型如Bitmap、Hyperloglog、Geospatial、布隆过滤器等，但这篇文章只波及罕用的对象，其余数据类型再当前的文章中再开展阐明
redis中的对象RedisObject由类型、编码、援用次数、lru、指向编码应用的数据结构对象形成
类型标识这个对象是什么类型对象
- 比方字符串、列表、哈希、汇合、有序汇合等
- 编码表示形成对应类型对象时应用哪种数据结构
援用次数示意这个对象被援用了多少次
- redis内存回收应用援用计数法，回收援用次数为0的对象 redis只依赖字符串对象，而不存在循环依赖所以不存在循环援用，因而能够应用援用计数法
- lru记录这个对象最近被调用的工夫，当空间回收算法应用lru时会优先回收很久未用的对象（后续删除回收的文章会介绍）
数据结构
sds简略动静字符串
sds应用字节数组保护，len记录字符串长度（示意结尾的'\0'不算），free示意字节数组中闲暇的长度
在增加元素前会判断数组长度是否足够，不够则会进行扩容；扩容有空间预调配策略，会留有一部分闲暇空间
如果下次批改字符串未超出数组长度就可能间接批改，节俭了扩容的开销
hashtable字典
字典应用哈希表实现，哈希表的原理本篇文章不会具体概述
哈希抵触应用链地址法解决，查找时先通过 hash%数组长度-1 来获取索引，失去索引后再遍历链表节点，如果是新增则间接应用头插法，插入链表头部
为了避免大字典扩容时产生阻塞，字典中哈希表的扩容是循序渐进的，在产生扩容时会有俩个哈希表
旧哈希表和新哈希表中都可能存储数据，再收到hget等申请时先在旧哈希表中查找，找到了就顺便把它迁徙到新哈希表中；在旧哈希表中没找到就去新哈希表中找
在实现迁徙时，新哈希表将旧哈希表替换
skiplist跳表
跳表保护多层级的有序链表，利用高层可能疾速达到后续节点，实现简略，保护不便，增删改查工夫复杂度均匀log n
比方查找值为2.0的节点，查找程序为图中虚线
先找到虚构头节点，从以后保护的最高层（L5）开始寻找，往后找到o3对象值为3.0，阐明曾经找过头了，于是要去下一层进行寻找；来到L4先后遍历，o1对象值为1.0，比目标值2.0小，阐明没有目标值在o1对象前面，于是来到o1对象L4层；持续在o1对象L4向后遍历，发现o3值为3.0大于目标值，于是降层来到o1对象L3层；L3层前面也是o3于是持续降层，来到L2层，L2层向后遍历为o2对象，值为2.0并比拟o2对象雷同阐明找到了
从保护的最高层开始查问，查问为空或者查问值大于目标值则降层，以后在最初一层还须要降层阐明找不到
当排序值雷同时，依照对象大小排序，这里的对象都是字符串对象
减少节点时的层数是随机生成的，越高层几率越小；其余批改操作，也是通过查问再进行，同时还要保护一些如最高层级等其余属性
intset整数汇合
intset 保护了一个有序，无反复的数组
在实现上应用数组、长度（记录元素数量）和编码（编码可能标识元素类型，如16、32、64位的整型）
当退出的元素为以后数组内不存在的高位整型时（比方数组中都是32位整型，此时退出一个64位整型）产生降级：先申请内存重调配，再将旧元素挪动到对应地位上，而后退出新元素同时批改编码，当删除高位整型时不会产生降级
intset的降级无效的节约内存，当set对象都为整型且数据量较小时应用intset实现以此来节约内存
ziplist压缩列表
ziplist用间断空间的节点形成，节点由记录前驱节点偏移量（逆序遍历）、编码（字节数组或整型的编码）、内容（内容能够是字节数组或整型）组成
因为ziplist的内容不是固定的，比方记录前驱节点偏移量是可变长的，这会影响节点的长度，又因为ziplist是空间间断的，这会导致后续的节点空间都要变动，被称为连锁更新（产生的概率小）
为了节俭空间，用于数量量小场景下列表、哈希、有序汇合的实现
quicklist疾速列表
疾速列表能够当作双向链表，只不过节点应用ziplist，罕用来实现数据量大场景下的列表对象
对象
阐明：
下文中数据量代表着占用字节状况和数据元素数量
本篇文章不介绍各个对象的命令应用规定，须要学习命令的同学能够去官网查看
字符串对象
字符串对象string由sds简略动静字符串来实现
sds有不同的编码：int、embstr、row
- int 用来存储整型字符串，计算时可能产生整型与字符串的转换
- embstr 用来存储短的字符串，只调配一次内存，分配内存时同时调配redisobject和sds
- row 用来存储长字符串，分配内存时须要调配两次：redisobject、sds
字符串对象是Redis中最罕用的对象，也是惟一会被其余对象依赖应用的对象
字符串对象常见的应用场景：整存整取的缓存、计数器、分布式锁
列表对象
列表对象list是一个队列，能够操作队头队尾，由ziplist或quicklist来实现
数据量小时应用ziplist，数据量大时应用quicklist( linkedlist+ziplist )
列表的应用场景是FIFO队列保障元素拜访程序
哈希对象
哈希对象hash是保护KV键值对的无序数据结构，由ziplist或hashtable来实现
数据量少应用ziplist、数据量大应用hashtable
哈希的应用场景是缓存的局部存取（比方一个大礼包下有A商品B商品等）
汇合对象
汇合对象set的特点是无序、无重，由intset或hashtable来实现
数据量少且数据为整型应用intset、数据量大或数据不为整型应用hashtable且值永远为null
汇合的应用场景是唯一性元素或交加并集（独特关注、可能意识）等（无序、无反复）
有序汇合对象
有序汇合对象zset是有序、无重的数据结构，由ziplist或skiplist + hashtable实现
数据量少时应用ziplist、数据量大时应用skiplist + hashtable（为了满足依据对象查问分指常量级性能，共享对象，不造成内存开销）
有序汇合的应用场景是排行榜、关注水平榜单等（有序、无反复）
总结
本篇文章围绕Redis以键值对存储、丰盛多元的数据结构为特点具体介绍了Redis中的对象与数据结构
对象由类型、编码、数据结构指针等形成
为了节俭空间，每种类型的对象都有多种编码类型的数据结构可能实现
字符串对象罕用来做缓存、分布式锁、计数器等，被其余对象依赖应用
- 由sds实现次要有int、embstr、row三种编码来解决不同类型的字符串，embstr解决短字符串优化内存调配
- sds是动静字符串，利用空间预调配策略在批改不超过数组长度状况下能够不须要进行扩容，节俭开销
<!---->
列表对象罕用来保护队列元素有序性
- 当数据量小时应用压缩列表ziplist实现，数据量大时应用疾速列表quicklist实现
- 压缩列表应用间断空间，节点中存储能够时字符串也能够是整型
- 疾速列表则能够当作链表，节点为压缩列表
<!---->
哈希对象罕用来保护局部存取的缓存
- 当数据量小时应用压缩列表zpilist实现，数据量大时应用哈希表hashtable实现
- 哈希表为了避免阻塞，在扩容时应用新旧两个哈希表存储元素，在解决命令的同时实现迁徙
<!---->
汇合对象有无序、无重的特点，罕用来做惟一、交加（独特好友）、并集（可能意识）
- 当数据量小且元素都为整型时应用整型汇合intset实现，当数据量大应用哈希表实现
- 整型汇合有不同的编码模式，充沛节俭了空间；应用哈希表时Value为空
<!---->
有序汇合对象有有序、无重的特点，罕用来做排行榜
- 当数据量小时应用压缩列表实现；当数据量大时应用跳表skiplist+哈希表实现，哈希表保留K对象V比拟值
- 跳表是多层级有序的链表，均匀工夫复杂度在log n，简略易保护
最初（一键三连求求拉~）
本篇文章笔记以及案例被支出 gitee-StudyJava、 github-StudyJava 感兴趣的同学能够stat下继续关注喔\~
有什么问题能够在评论区交换，如果感觉菜菜写的不错，能够点赞、关注、珍藏反对一下\~
关注菜菜，分享更多干货，公众号：菜菜的后端私房菜
本文由博客一文多发平台 OpenWrite 公布！