1前言
此篇文章主要对Redis的5种基本数据类型，即字符串(String)、列表(List)、散列(Hash)、集合(Set)、有序集合(Sorted Set)，从使用场景和底层结构出发，进行多维度深入分析。
21、String1.1、使用场景
string是Redis中最常使用的类型，使用场景如下：
缓存功能：String字符串是最常用的数据类型，不仅仅是Redis，各个语言都是最基本类型，因此，利用Redis作为缓存，配合其它数据库作为存储层，利用Redis支持高并发的特点，可以大大加快系统的读写速度、以及降低后端数据库的压力。计数器：许多系统都会使用Redis作为系统的实时计数器，可以快速实现计数和查询的功能。而且最终的数据结果可以按照特定的时间落地到数据库或者其它存储介质当中进行永久保存。共享用户Session:用户重新刷新一次界面，可能需要访问一下数据进行重新登录，或者访问页面缓存Cookie，但是可以利用Redis将用户的Session集中管理，在这种模式只需要保证Redis的高可用，每次用户Session的更新和获取都可以快速完成。大大提高效率。1.2、底层结构（SDS）
Redis是用C语言写的，但是Redis并没有使用C的字符串表示（C是字符串是以\0空字符结尾的字符数组），而是自己构建了一种简单动态字符串（simple dynamic string，SDS）的抽象类型，并作为Redis的默认字符串表示
在Redis中，包含字符串值的键值对底层都是用SDS实现的
SDS的定义在Redis 3.2版本之后有一些改变，由一种数据结构变成了5种数据结构，会根据SDS存储的内容长度来选择不同的结构，以达到节省内存的效果
staticinlinecharsdsReqType(size_tstring_size){if(string_size<1<<5)//32returnSDS_TYPE_5;if(string_size<1<<8)//256returnSDS_TYPE_8;if(string_size<1<<16)//6553664kreturnSDS_TYPE_16;if(string_size<1ll<<32)//42949672964GreturnSDS_TYPE_32;returnSDS_TYPE_64;}1）、源码实例
下面以3.2版本的sdshdr8看一个示例
img
len：记录当前已使用的字节数（不包括’\0’），获取SDS长度的复杂度为O(1)
alloc：记录当前字节数组总共分配的字节数量（不包括’\0’）
flags：标记当前字节数组的属性，是sdshdr8还是sdshdr16等，flags值的定义可以看下面代码
buf：字节数组，用于保存字符串，包括结尾空白字符’\0′
2）、SDS与C字符串的区别1、常数复杂度获取字符串长度C字符串不记录字符串长度，获取长度必须遍历整个字符串，复杂度为O(N)；而SDS结构中本身就有记录字符串长度的len属性，所有复杂度为O(1)。Redis将获取字符串长度所需的复杂度从O(N)降到了O(1)，确保获取字符串长度的工作不会成为Redis的性能瓶颈2、杜绝缓冲区溢出，减少修改字符串时带来的内存重分配次数C字符串不记录自身的长度，每次增长或缩短一个字符串，都要对底层的字符数组进行一次内存重分配操作。修改字符串长度N次必然会需要执行N次内存重分配3.2版本则是alloc属性记录总的分配字节数量。通过未使用空间，SDS实现了空间预分配和惰性空间释放两种优化的空间分配策略，解决了字符串拼接和截取的空间问题，修改字符串长度N次最多会需要执行N次内存重分配3）、内存分配及回收策略内存分配策略:当SDS的len属性长度小于1MB时，redis会分配和len相同长度的free空间。至于为什么这样分配呢，上次用了len长度的空间，那么下次程序可能也会用len长度的空间，所以redis就为你预分配这么多的空间。但是当SDS的len属性长度大于1MB时，程序将多分配1M的未使用空间。这个时候我在根据这种惯性预测来分配的话就有点得不偿失了。所以redis是将1MB设为一个风险值，没过风险值你用多少我就给你多少，过了的话那这个风险值就是我能给你临界值.内存回收策略:redis的内存回收采用惰性回收，即你把字符串变短了，那么多余的内存空间我先不还给操作系统，先留着，万一马上又要被使用呢。短暂的持有资源，既可以充分利用资源，也可以不浪费资源。这是一种很优秀的思想。32、List
List本身就是我们在开发过程中比较常用的数据结构了，为有序列表，可以通过 List 存储一些列表型的数据结构，类似粉丝列表、文章的评论列表之类的东西。
2.1、使用场景消息队列：Redis的链表结构，可以轻松实现阻塞队列，可以使用左进右出的命令组成来完成队列的设计。lpush生产消息，lpop消费消息 ，当lpop没有消息时，可以sleep一段时间，然后再检查有没有信息，如果不想sleep的话，可以使用blpop, 在没有信息的时候，会一直阻塞，直到信息的到来。文章列表或数据分页展示比如我们常用的博客网站的文章列表，当用户量越来越多时，而且每一个用户都有自己的文章列表，而且当文章多时，都需要分页展示，这时可以考虑使用Redis的列表，列表不但有序同时还支持按照范围内获取元素，可以完美解决分页查询功能。大大提高查询效率。2.2、底层结构（链表）
链表是一种比较常见的数据结构了，特点是易于插入和删除、内存利用率高、且可以灵活调整链表长度，但随机访问困难。许多高级编程语言都内置了链表的实现，但是C语言并没有实现链表，所以Redis实现了自己的链表数据结构
链表在Redis中应用的非常广，列表（List）的底层实现就是链表。
此外，Redis的发布与订阅、慢查询、监视器等功能也用到了链表
1）、源码示例typedefstructlist{//链表头节点listNode*head;//链表尾节点listNode*tail;//节点值复制函数void*(*dup)(void*ptr);//节点值释放函数void(*free)(void*ptr);//节点值对比函数int(*match)(void*ptr,void*key);//链表所包含的节点数量unsignedlonglen;}list;
每个节点listNode可以通过prev和next指针分布指向前一个节点和后一个节点组成双端链表，同时每个链表还会有一个list结构为链表提供表头指针head、表尾指针tail、以及链表长度计数器len，还有三个用于实现多态链表的类型特定函数
dup：用于复制链表节点所保存的值free：用于释放链表节点所保存的值match：用于对比链表节点所保存的值和另一个输入值是否相等
img2）、链表特性
双端链表：带有指向前置节点和后置节点的指针，获取这两个节点的复杂度为O(1)
无环：表头节点的prev和表尾节点的next都指向NULL，对链表的访问以NULL结束
链表长度计数器：带有len属性，获取链表长度的复杂度为O(1)
多态：链表节点使用 void*指针保存节点值，可以保存不同类型的值
43、Hash3.1、使用场景存储结构化数据:Hash类似 Map，一般可以将结构化的数据，比如一个对象（前提是这个对象没嵌套其他的对象）缓存在 Redis 里，然后每次读写缓存的时候，可以就操作 Hash 里的某个字段。但是因为现在很多对象都是比较复杂的，比如你的商品对象可能里面就包含了很多属性，其中也有对象，不适宜用hash3.2、底层结构（字典）
字典，又称为符号表（symbol table）、关联数组（associative array）或映射（map），是一种用于保存键值对（key-value pair）的抽象数据结构。字典中的每一个键都是唯一的，可以通过键查找与之关联的值，并对其修改或删除
Redis的键值对存储就是用字典实现的，散列（Hash）的底层实现之一也是字典
1）、源码示例
Redis的字典底层是使用哈希表实现的，一个哈希表里面可以有多个哈希表节点，每个哈希表节点中保存了字典中的一个键值对
dict的ht属性是两个元素的数组，包含两个dictht哈希表，一般字典只使用ht[0]哈希表，ht[1]哈希表会在对ht[0]哈希表进行rehash（重哈希）的时候使用，即当哈希表的键值对数量超过负载数量过多的时候，会将键值对迁移到ht[1]上
rehashidx也是跟rehash相关的，rehash的操作不是瞬间完成的，rehashidx记录着rehash的进度，如果目前没有在进行rehash，它的值为-1
2）、执行流程
当一个新的键值对要添加到字典中时，会根据键值对的键计算出哈希值和索引值，根据索引值放到对应的哈希表上，即如果索引值为0，则放到ht[0]哈希表上。
当哈希表的键值对太多或太少，就需要对哈希表进行扩展和收缩，通过rehash(重新散列)来执行
Redis的Hash，在数组 链表的基础上，进行了一些rehash优化即渐进式rehash等。采用链表来处理哈希冲突，没有使用红黑树优化。在实际开发过程中，这个rehash 操作并不是一次性、集中式完成的，而是分多次、渐进式地完成的。采用渐进式rehash 的好处在于它采取分而治之的方式，避免了集中式rehash 带来的庞大计算量。
3）、渐进式rehash为ht[1] 分配空间，让字典同时持有ht[0]和ht[1]两个哈希表维持一个索引计数器变量rehashidx，并将它的值设置为0，表示rehash 开始在rehash 进行期间，每次对字典执行CRUD操作时，程序除了执行指定的操作以外，还会将ht[0]中的数据rehash 到ht[1]表中，并且将rehashidx加一当ht[0]中所有数据转移到ht[1]中时，将rehashidx 设置成-1，表示rehash 结束4）、小结
dict 结构内部包含两个 hashtable，通常情况下只有一个 hashtable 是有值的。但是在 dict 扩容缩容时，需要分配新的 hashtable，然后进行渐进式搬迁，这时候两个 hashtable 存储的分别是旧的 hashtable 和新的 hashtable。待搬迁结束后，旧的 hashtable 被删除，新的 hashtable 取而代之。
rehash就是采用分而治之的思想，将庞大的迁移工作量划分到每一次CURD中，避免了服务繁忙。
54、Set4.1、使用场景
Set 是无序集合，会自动去重。可以基于 Set 玩交集、并集、差集的操作。
Set底层使用了intset和hashtable两种数据结构存储的，intset我们可以理解为数组，hashtable就是普通的哈希表。set的底层存储intset和hashtable是存在编码转换的，使用intset存储必须满足下面两个条件，否则使用hashtable，条件如下：
结合对象保存的所有元素都是整数值集合对象保存的元素数量不超过512个
本次重点讲整数集合（intset），整数集合（intset）是Redis用于保存整数值的集合抽象数据结构，可以保存类型为int16_t、int32_t、int64_t的整数值，并且保证集合中不会出现重复元素。
1）、源码示例
contents数组：整数集合的每个元素在数组中按值的大小从小到大排序，且不包含重复项
length记录整数集合的元素数量，即contents数组长度
encoding决定contents数组的真正类型，如INTSET_ENC_INT16、INTSET_ENC_INT32、INTSET_ENC_INT64
img2）、整数集合升级
当想要添加一个新元素到整数集合中时，并且新元素的类型比整数集合现有的所有元素的类型都要长，整数集合需要先进行升级1. （upgrade），才能将新元素添加到整数集合里面。每次想整数集合中添加新元素都有可能会引起升级，每次升级都需要对底层数组已有的所有元素进行类型转换
升级添加新元素：
根据新元素类型，扩展整数集合底层数组的空间大小，并为新元素分配空间把数组现有的元素都转换成新元素的类型，并将转换后的元素放到正确的位置，且要保持数组的有序性添加新元素到底层数组
整数集合的升级策略可以提升整数集合的灵活性，并尽可能的节约内存
另外,整数集合不支持降级，一旦升级，编码就会一直保持升级后的状态
65、Sorted Set（Zset）
Sorted set 是排序的 Set，去重但可以排序，写进去的时候给一个分数，自动根据分数排序。
5.1、使用场景排行榜：有序集合经典使用场景。例如视频网站需要对用户上传的视频做排行榜，榜单维护可能是多方面：按照时间、按照播放量、按照获得的赞数等。例如微博热搜榜，就是有个后面的热度值，前面就是名称
它的内部实现用的是一种叫做 「跳跃表」 的数据结构
5.2、底层结构（跳跃表skiplist）1）、为什么使用跳跃表
首先，因为 zset 要支持随机的插入和删除，所以它 不宜使用数组来实现，关于排序问题，我们也很容易就想到 红黑树/ 平衡树 这样的树形结构，为什么 Redis 不使用这样一些结构呢？
性能考虑： 在高并发的情况下，树形结构需要执行一些类似于 rebalance 这样的可能涉及整棵树的操作，相对来说跳跃表的变化只涉及局部 (下面详细说)；实现考虑： 在复杂度与红黑树相同的情况下，跳跃表实现起来更简单，看起来也更加直观；
基于以上的一些考虑，Redis 基于 William Pugh 的论文做出一些改进后采用了 跳跃表 这样的结构。
2）、复杂度分析
查找的时间复杂度分析 O(logn) ,插入与删除的时间复杂度分析 O(logn)
我们采用逆向分析的方法。假设我们现在在目标节点，想要走到跳跃表最左上方的开始节点。这条路径的长度，即可理解为查找的时间复杂度。而跳跃表的高度又是logn级别的，故查找的复杂度也为logn级别。
插入和删除都由查找和更新两部分构成。查找的时间复杂度为O(logn)，更新部分的复杂度又与跳跃表的高度成正比，即也为O(logn)。所以，插入和删除操作的时间复杂度都为O(logn)
3）、实例解析
一个普通的单链表查询一个元素的时间复杂度为O(N)，即便该单链表是有序的。使用跳跃表（SkipList）是来解决查找问题的，它是一种有序的数据结构，不属于平衡树结构，也不属于Hash结构，它通过在每个节点维持多个指向其他节点的指针，而达到快速访问节点的目的
跳跃表本质是解决查找问题，其不要求上下相邻两层链表之间的节点个数有严格的对应关系，而是为每个节点随机出一个层数(level)。比如，一个节点随机出的层数是 3，那么就把它链入到第 1 层到第 3 层这三层链表中。
假设我们现在在目标节点，想要走到跳跃表最左上方的开始节点。这条路径的长度，即可理解为查找的时间复杂度。而跳跃表的高度又是logn级别的，故查找的复杂度也为logn级别。
插入和删除都由查找和更新两部分构成。查找的时间复杂度为O(logn)，更新部分的复杂度又与跳跃表的高度成正比，即也为O(logn)。
为了表达清楚，下图展示了如何通过一步步的插入操作从而形成一个 skiplist 的过程：
从上面的创建和插入的过程中可以看出，每一个节点的层数（level）是随机出来的，而且新插入一个节点并不会影响到其他节点的层数，因此，插入操作只需要修改节点前后的指针，而不需要对多个节点都进行调整，这就降低了插入操作的复杂度。
现在我们假设从我们刚才创建的这个结构中查找 23 这个不存在的数，那么查找路径会如下图：
33 (1)通俗解释
想象你是一家创业公司的老板，刚开始只有几个人，大家都平起平坐。后来随着公司的发展，人数越来越多，团队沟通成本逐渐增加，渐渐地引入了组长制，对团队进行划分，于是有一些人又是员工又有组长的身份。
再后来，公司规模进一步扩大，公司需要再进入一个层级：部门。于是每个部门又会从组长中推举一位选出部长。
跳跃表就类似于这样的机制，最下面一层所有的元素都会串起来，都是员工，然后每隔几个元素就会挑选出一个代表，再把这几个代表使用另外一级指针串起来。然后再在这些代表里面挑出二级代表，再串起来。最终形成了一个金字塔的结构。
想一下你目前所在的地理位置：亚洲 > 中国 > 某省 > 某市 > ….，就是这样一个结构！
