Redis 常见数据类型和应用场景
常见的有五种：String、Hash、List、Set、Zset
新版本增加的：BitMap、HyperLogLog、GEO、Stream
Redis为什么那么快？
1.是内存数据库，所有操作都在内存上进行
2.Redis实现的数据结构使得我们在对数据进行增删改查操作时，Redis能高效处理
（Redis实现的数据结构支持对数据进行高效的增删改查操作）
PS:
Redis数据结构并不是数据类型（String、List、Hash、Zset、Set），数据类型是Redis键值对中value的数据类型，即数据的保存形式。这些对象的底层实现方式就用到了数据结构
1.那么键值对数据库是怎么实现的的？Redis的键值对中的key一般是String，而value则可以是字符串对象，也可以是集合数据类型的对象（List对象、Hash对象、Set对象、Zset对象）
2.为什么String适合做Key？String对象不可变，一旦创建就无法修改。这确保了key的稳定性。若key可变，则可能导致hashCode和equals方法不一致，进而影响HashMap的正确性。
3.（不同数据类型的）键值对如何保存在Redis中？使用 →哈希表← 保存所有键值对，O(1)查询。哈希表（一种数组）中元素叫做哈希桶。
4.Redis的哈希桶如何保存键值对数据？哈希桶存放的是指向键值对数据的指针（dictEntry*），通过指针寻找键值对数据。因为键值对的Value可以保存字符串对象和几何数据类型的对象，所以键值对的数据结构中并不是直接保存值本身，而是保存了void * key和void * value指针，分别指向实际的键对象和值对象，这样一来即使是集合数据也可以通过void * value指针找到。
旧版（Redis 3.0）：SDS、双向链表、压缩列表、哈希表、整数集合、跳表
新版（2021-11-29）：SDS、quicklist、listpack、哈希表、整数集合、跳表
细说各种数据结构：
一、SDS
Redis是由C语言实现的，但因为char* 字符数组无法满足需求，所以Redis自己封装了一个名为简单动态字符串（simple dynamic string，SDS）的数据结构来表示字符串
C语言字符串的缺陷
我们首先应该知道C语言字符串以"\0"作为结尾位置，也是字符串的一部分，且字符串操作函数读取到"\0"时停止操作。
①C语言通过遍历获取字符串长度，时间复杂度为O(N)
②因为以"\0"作为结尾位置，导致字符串里面不能含"\0"字符，否则会被误认为字符串结尾，导致C语言的字符串只能保存文本数据，不能保存图片、音频、视频等二进制数据。
③C语言的字符串在拼接的时候，不会记录自身的缓冲区大小，如果分配的内存不够时，就会发生缓冲区溢出，造成程序运行终止。同时，拼接操作时间复杂度也是O(N)
SDS如何解决问题
①从数据结构来说
len（字符串长度，获取字符串长度时复杂度降低为O(1)）
alloc（分配的空间长度，判断不够用时自动扩大）
flags（sds类型，表示不同类型的SDS，灵活保存不同大小的字符串，节省空间）
buf[]（字节数组，保存实际数据，因为无需"\0"判断结尾，所以可以存二进制数据）
二、链表
List对象的底层实现之一就是链表，C语言本身没有链表这个数据结构，Redis自己设计了一个链表数据结构
链表节点设计：前置节点+后置节点+节点值
链表结构设计：头节点+尾节点+节点值复制函数+节点值释放函数+节点值比较函数+链表节点数量
优势：获取当前节点的前后节点时间复杂度为O(1)，无环链表（指针可以指向null）；获取头/尾节点、节点数量的时间复杂度为O(1)；链表节点可以保存不同类型的值。
缺陷：内存不连续，无法很好利用CPU缓存；内存开销大(每保存一个链表节点都需要一个链表节点结构头的分配)；
三、压缩列表:
结构设计：由连续内存块组成的顺序型数据结构，即zlbytes（占用的内存字节数）+zltail（尾部节点距离起始地址多少字节，换言之列表尾的偏移量）+zllen（压缩列表包含的节点数量）+entry1+entry2+...+entryN+zlend（结束点，固定值0xFF，十进制里面的255）
节点设计：prevlen（前一个节点的长度）+encoding（当前节点的数据类型和长度）+data（当前节点的数据）
如果前一个节点长度<254字节，则prevlen需要1字节空间，否则需要5字节空间
当前节点数据类型为整数，encoding需要1字节空间，若为字符串，则需要1/2/5字节空间
①问题：由于结构设计导致查找居于中间的元素时，复杂度会偏高
②问题：新增/修改某元素时，若空间不够，则需要重新分配压缩列表占用的内存空间，就好像多米诺骨牌一样，造成连锁更新的后果。
四、哈希表
最大优点：查询时间复杂度O(1)——key通过Hash函数的计算，进而定位数据在表中位置，哈希表（实际上是数组）可以通过索引值快速查询到数据。
哈希冲突——链式哈希解决，将具有相同哈希值的数据串联起来，形成单向链表。
哈希冲突太严重时，需要对哈希表的大小进行扩展——即rehash，
rehash有多种做法，主要的区别在于数据迁移部分。
做法1：直接迁移，不适合数据量大的情况，因为大量数据拷贝会阻塞Redis，导致其他请求无法得到服务。
做法2：渐进式，在rehash进行期间，每次哈希表元素增删改查时，还会顺序将 →哈希表1← 中索引位置上的所有key-value迁移到 →哈希表2←上。
什么时候触发rehash？（负载因子=哈希表已经保存节点数量/哈希表大小）
情况1：负载因子 >= 1 且 Redis没有执行bgsave（RDB快照）/bgrewiteaof（AOF重写）
情况2：负载因子 >=5 强制进行rehash
五、整数集合
整数升级操作：新增一个元素，其类型比现有的所有元素的类型都要长时，在原本的空间大小（contents.length）之上扩容，（（contents.length+1） * 新元素类型长度）-（contents.length * 原元素类型长度））
好处是避免用长类型数组存放短类型数组，可以节省内存资源，但不支持降级操作
六、跳表——Zset，时间复杂度O(logN)
结构设计：基于链表实现多层有序链表，所以跳表是一个带有层级关系的链表，每一层级可以包含多个节点，每个节点通过指针连接，这一特性依赖于zskiplistLevel结构体类型的level数组。
节点查询过程
节点层数设置
为什么不用平衡树？
①内存占用来说，跳表相对平衡树更灵活，每个节点包含的指针数目平均为1/(1-p),Redis里p=1/4，平均包含1.33个指针，小于平衡树的2个
②范围查找来说，跳表相对平衡树更简单，找到指定范围的小值后，对第一层链表进行若干步遍历即可，平衡树则需要以中序遍历的顺序继续寻找其他不超过大值的节点。
③实现难度来说，跳表相对平衡树更简单，跳表的插入和删除只需要修改相邻节点的指针，平衡树则可能引发子树的调整。