共计 3590 个字符，预计需要花费 9 分钟才能阅读完成。
引言
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 公布！