动态字符串
我们都知道Redis中保存的key是字符串，value 往往是字符串或者字符串的集合。可见字符串是Redis中最常用的一种数据结构
不过Redis没有直接使用C语言中的字符串，因为C语言字符串存在很多问题：
1.获取字符串长度需要进行计算
2.非二进制安全
3.不可修改
Redis构建了一种新的字符串结构，称为简单动态字符串（Simple Dynamic String）,简称SDS
例如我们执行命令：
那么Redis将在底层创建两个SDS,其中一个包含"name"的SDS,另一个是包含"虎哥"的SDS
Redis是C语言实现的，其中SDS是一个结构体，源码如下
例如，一个包含字符串"name"的sds结构如下：
1.SDS读取字符串时，不会以结束标识作为结束来读取，SDS从起始读len：4个，二进制安全
2.需要知道整个字符串长度时，不需要遍历计数，不需要计算，直接长度是len
SDS之所以叫做动态字符串，是因为它具备动态扩容的能力，例如一个内容为"hi"的SDS
假如我们要给SDS追加一段字符串",Amy",这里首先会申请内存空间：
如果新字符串小于1M,则新空间为扩展后字符串长度的两倍+1；
如果新字符串大于1M,则新空间为扩展后字符串长度的两倍+1M+1。称为内存预分配
备注：加1，结束标识保证和C语言兼容
SDS优点
1.获取字符串长度的时间复杂度为O（1）
2.支持动态扩容
3.减少内存分配次数
4.二进制安全
intSet
intSet是Redis中set集合的一种实现方式，基于整数数组来实现，并且具备长度可变、有序等特征
结构如下：
其中的encoding包含三种模式，表示存储的整数大小不同
为了方便查找，Redis会将intset中所有的数据按照升序一次保存在contents数组中，结构如图：
现在，数组中每个数字都在int16_t范围内，因此采用的编码方式是INTSET_ENC_INT16,每部分占用的字节大小为：
-
encoding:4字节
-
length:4字节
-
contents:2字节*3=6字节
intSet升级
现在，假设有一个intset，元素为[5,10,20],采用的编码是INTSET_ENC_INT16，则每个整数占2个字节
我们向该其中添加一个数字：50000，这个数字超出了int16_t的范围，intset会自动升级编码方式到合适的大小
以当前案例来说流程如下：
1.升级编码为INTSET_ENC_INT32，每个整数占4个字节，并按照新的编码方式及元素个数扩容数组
2.倒叙依次将数组中的元素拷贝到扩容后的正确位置（正序5的位置会把原来的10覆盖）
20是第2号元素并占4个字节：起始的字节是2*4=8
3.将待添加的元素放入数组末尾
4.最后，将intset的encoding属性改为INTSET_ENC_INT32,将length属性改为4
intSet新增流程
源码如下：
intSet可以看做是特殊的整数数组，具备一些特点
1.Redis会确保intset中的元素唯一、有序
2.具备类型升级机制，可以节省内存空间
3.底层采用二分查找方式来查询
Dict
我们知道Redis是一个键值型的数据库，我们可以根据键实现快速的增删改查。而键与值的映射关系是通过Dict来实现的
Dict由三部分组成，分别是：哈希表（DictHashTable）、哈希节点（DictEntry）、（Dict）
当我们向Dict添加键值对时，Redis首先根据key计算出Hash值（h），然后利用h&sizemask来计算元素应该存储到数组中的哪个索引位置。我们存储k1=v1,假设k1的哈希值h=1,则1&3=1，因此k1=v1要存储到数组角标1位置
Dict的扩容
Dict的HashTable就是数组结合单向链表的实现，当集合中元素较多时，必然导致哈希冲突增多，链表过长，则查询效率会大大降低
Dict在每次新增键值对时都会检查负载因子（LoadFacttor=use/size）,满足以下两种情况会触发扩容：
1.哈希表的loadFactor>=1,并且服务器没有执行BGSAVE或者BGREWRITEAOF等后台进程
2.哈希表的loadFactor>5
Dict的收缩
Dict除了扩容以外，每次删除元素时，也会对负载因子做检查，当loadFactor<0.1时，会做哈希表收缩
Dict的ReHash
不管是扩容还是收缩，必定会创建新的hash表，导致哈希表的size和sizemask变化，而key的查询和sizemask有关，因此必须对哈希表中的每一个key重新计算索引，插入新的索引表，这个过程称为rehash。过程是这样的：
1.计算哈希表的realeSize,值取决于当前要做的是扩容还是收缩：
-
如果是扩容，则新的size为第一个大于等于dict.ht[0].used+1的2ⁿ
-
如果是收缩，则新的size为第一个大于等于dict.ht[0].used的2ⁿ（不得小于4）
2.按照新的realesize申请内存空间，创建dictht,并赋值给dict.ht[1]
3.设置dict.rehashidx=0,标识开始rehash
4.将dict.ht[0]中的每一个dictEntry都rehash到dict.ht[1]
5.将dict.ht[1]赋值给dict.ht[0]，给dict.ht[1]初始化为空哈希表，释放原来的dict.ht[0]的内存
Dict的Rehash并不是一次性完成的。试想一下，如果Dict中包含数百万的的entry,要在一次性hash完成，极有可能导致主线程阻塞。因此Dict的rehash是分多次、渐进式的完成，因此称为渐进式的rehash.流程如下：
1.计算哈希表的size,值取决于当前要做的是扩容还是收缩：
-
如果是扩容，则新的size为第一个大于等于dict.ht[0].used+1的2ⁿ
-
如果是收缩，则新的size为第一个大于等于dict.ht[0].used的2ⁿ（不得小于4）
2.按照新的size申请内存空间，创建dictht,并赋值给dict.ht[1]
3.设置dict.rehashidx=0,标识开始rehash
4.每次执行新增、查询、修改、删除操作时，都检查一下dict.rehashidx是否大于-1，如果是则将dict.ht[0].table[rehashidx]的entry链表rehash到dict.ht[1],并且将rehashidx++，直至dict.ht[0]的所有数据都rehash到dict.ht[1]
5.将dict.ht[1]赋值给dict.ht[0]，给dict.ht[1]初始化为空哈希表，释放原来的dict.ht[0]的内存
6.将rehashidx赋值为-1，代表rehash结束
7.在rehash过程中，新增操作，则直接写入ht[1],查询、修改、删除则会在dict.ht[0]和dict.ht[1]依次查找并执行，这样可以确保ht[0]的数据只减不增，随着rehash最终为空
Dict总结
Dict结构：
类似java的hashTable,底层数组加链表解决哈希冲突
Dict包含两个hash表，ht[0]平常用，ht[1]用来rehash
Dict的伸缩：
当LoadFactor大于5或者LoadFacto大于1并且没有子进程任务时，Dict扩容
当LoadFactor小于0.1时，Dict收缩
扩容大小为第一个大于等于used+1的2ⁿ
收缩大小为第一个大于等于used的2ⁿ
Dict采用渐进式rehash,每次访问时执行一次rehash
rehash时ht[0]只减不增，新增操作只在ht[1]执行，其他操作在两个哈希表
ZipList
ZipList是一种特殊的"双端链表"，由一系列特殊编码的连续内存块组成，可以在任意一端进行压入/弹出操作，并且读操作的时间复杂度是O(1)。
ZipList中的entry并不像普通链表那样记录前后节点的指针，因为记录两个指针要占用16个字节，浪费内存，而是采用了下面的结构：
1.previous_entry_length:前一个节点的长度，占一个或5个字节
-
如果前一节点的长度小于254字节，则采用1个字节来保存这个长度值
-
如果前一节点的长度小于254字节，则采用5个字节来保存这个长度值，第一个字节为oxfe,后四个字节才是真实长度数据
2。encoding:编码属性，记录content的数据类型（字符串还是整数）以及长度，占用1个、2个或5个字节
3.contents:负责保存节点的数据，可以是字符串或整数
注意：
ZipList中所有的存储长度的数值俊采用小端字节序，即低位字节在前，高位字节在后，例如：0x1234,采用小端字节序后实际存储值为：0x3412
Encoding编码
ZipListEntry的encoding编码方式分为字符串和整数两种
字符串：如果encoding是以"00","01"或者"10"开头,则content是字符串
例如，我们要保存字符串：“ab"和"bc”
字符串：如果encoding是以"11"开头,则证明content是整数，且encoding固定只占用1个字节
ZipList连锁更新问题
ZipList的每个Entry都包含previous_entry_length来记录上一个节点的大小，长度是1个或5个字节
如果前一节点的长度小于254字节，则采用1个字节来保存这个长度的值
如果前一节点的长度大于等于254字节，则采用5个字节来保存这个长度的值，第一个字节为0xfe,后四个字节才是真实长度数据
现在，假设我们有N个连续的，长度为250~253字节之间的entry,因此entry的previous_entry_length属性用于1个字节即可表示，如图所示：
ZipList这种特殊情况下产生的连续多次空间扩展操作称之为连锁更新，新增、删除都可能导致连锁更新的发生
zipList总结
1.压缩列表可以看做一种连续内存空间的"双向链表"
2.列表的节点之间不是通过指针连接，而是记录上一节点和本节点长度来寻址，内存占用较低
3.如果列表数据较多，导致链表过长，可能影响查询性能
4.增或删较大数据时有可能发生连续更新问题
QuickList
问题1：ZipList虽然节省内存，但是申请内存必须是连续空间，如果内存占用较多，申请内存效率较低。怎么办？
为了缓解这个问题，我们必须限制ZipList的长度和entry大小
问题2：但是我们要存储大量数据，超出了ZipList最佳的上限该怎么办？
我们可以创建多个ZipList来分片存储数据
问题三：数据拆分后比较分散，不方便管理和查找，这多个ZipList如何建立联系？
Redis在3.2版本引入了新的数据结构QuickList,它是一个双端链表，只不过每个节点都是一个ZipList
为了避免QuickList中的每个ZipList中的entry过多，Redis提供了一个配置项：list-max-ziplist-size来限制
1.如果值为正，则代表ZipList的允许的entry个数的最大值
2.如果值为负，则代表ZipList的最大内存大小，分五种情况：
① -1：每个ZipList的内存占用不能超过4kb
② -2：每个ZipList的内存占用不能超过8kb
③ -3：每个ZipList的内存占用不能超过16kb
④ -4：每个ZipList的内存占用不能超过32kb
⑤ -5：每个ZipList的内存占用不能超过64kb
默认值为 -2：
除了控制ZipList的大小，QuickList还可以对节点的ZipList做压缩。通过配置项list-compress-depth来控制。因为链表一般都是从首尾访问较多，所以首尾是不压缩的。这个节点是控制首尾不压缩的节点的个数：
-
0:特殊值，代表不压缩
-
1：标识QuickList的首尾各有1个节点不压缩，中间节点压缩
-
2：标识QuickList的首尾各有2个节点不压缩，中间节点压缩
-
以此类推
默认值：
以下是QuickList和QuckListNode的结构源码：
QuickList总结
1.是一个节点为ZipList的双端链表
2.节点采用ZipList,解决了传统链表的内存占用问题
3.控制了ZipList大小，解决了连续内存空间申请效率问题
4.中间节点可以压缩，进一步节省了内存
SkipList
SkipList(跳表)首先是链表，但与传统的链表相比有几点差异：
1.元素按照升序排列存储
2.节点可能包含多个指针，指针跨度不同
SkipList总结
1.跳跃表是一个双向链表，每个节点都包含score和ele值
2.节点按照score值排序，score一样则按照ele排序
3.每个节点都可以包含多层指针，层数是1到32的随机数
4.不同层指针到下一个节点的跨度不同，层数越高，跨度越大
5，增删改查效率和红黑树基本一致，实现却更简单
RedisObject
Redis中的任意数据类型的键和值都会被封装为一个RedisObject,也叫做Redis对象，源码如下：
Redis的编码方式
Redis会根据存储的数据类型不同，选择不同的编码方式，共包含11种不同类型
五种数据结构
Redis中会根据存储的数据类型的不同，选择不同的编码方式，每种数据类型的使用的编码方式不同
String
String是Redis中最常见的数据存储类型：
1.其基本编码方式是RAW,基于简单动态字符串（SDS）实现，存储上限为512mb
2.如果存储的SDS长度小于44字节，则会采用EMBSTR编码，此时object head与SDS是一段连续空间。申请内存时只需要调用一次内存分配函数，效率更高
3.如果存储的字符串是整数值，并且大小在LONG_MAX范围内，则会采用INT编码：直接将数据保存在RedisObject的ptr指针位置（刚好8字节），不再需要SDS了
RAW
EMBSTR
INT
list
Redis的list类型可以从首、尾操作列表中的元素
哪一个数据结构能够满足上述特征？
-
LinkedList:普通链表，可以从双端访问，内存占用较高，内存碎片较多
-
ZipList:压缩列表，可以从双端访问，内存占用低，存储上限低
-
QuickList:LinkedList+ZipList,可以从双端访问，内存占用较低，包含多个ZipList,存储上限高
1.在3.2版本之前，Redis采用ZipList和LinkedList来实现List,当元素数量小于512并且元素大小小于64字节时采用ZipList,超过则采用LinkedList编码
2.在3.2版本之后，Redis统一采用QuickList来实现List
Set
Set是Redis中的单列集合，满足下列特点
1.不保证有序性
2.保证元素唯一（可以判断元素是否存在）
3.求交集、并集、差集
可以看出Set对查询元素的效率要求非常高，思考一下，什么样的数据结构可以满足？
- HashTable:也就是Redis中的Dict,不过Dict是双列集合（可以存储键值对）
Set是Redis中的集合，不一定要确保元素有序，可以满足元素唯一、查询效率要求极高
-
为了查询效率和唯一性，set采用HT编码（Dict）,Dict中的key用来存储元素，value统一为null
-
当存储的所有数据都是整数，并且元素数量不超过set-max-intset-entries,Set会采用intset编码，以节省内存
set-max-intset-entries的默认值是512
ZSet
ZSet就是SortedSet,其中每一个元素都需要指定一个score值和member值：
1.可以根据score值排序
2.member必须唯一
3.可以根据member查询分数
因此，zset底层数据结构必须满足键值存储、键必须唯一、可排序这几个需求。之前学习的那种编码结构可以满足？
-
SkipList:可以排序，并且可以同时存储score和ele值（member）
-
HT(Dict):可以键值，并且可以根据key找value
当元素数量不多时，HT和SkipList的优势不明星，而且更耗内存。因此zset会采用ZipList结构来节省内存，不过需要同时满足两个条件：
① 元素数量小于zset-max-ziplist-entries,默认值是128
② 每个元素都小于zset-max-ziplist-value字节,默认值是64
ZipList本身没有排序功能，而且没有键值对的概念，因此需要有ZSet通过编码实现：
-
ZipList是连续内存，因此score和member紧挨在一起的两个entry，element在前，score在后
-
score越小越接近队首，score越大越接近队尾，按照score值升序排列
Hash
Hash结构与Redis中的Zset非常类似
1.都是键值存储
2.都需要根据键获取值
3.键必须唯一
区别如下：
1.zset的键是member,值是score,hash的键和值都是任意值
2.zset要根据score排序，hash则无需排序
因此，Hash底层采用的编码与Zset也基本一致，只需要把排序有关的SkipList去掉即可：
1.Hash结构默认采用ZipList编码，用以节省内存。ZipList中相邻的两个entry分别保存field和value
2.当数据量较大时，hash结构会转为HT编码，也就是Dict,触发条件有两个：
① ZipList中的元素数量超过了hash-max-ziplist-entries(默认512)
② ZipList中的任意entry大小超过了hash-max-ziplist-valus(默认64字节)
视频地址
