Redis自己创建的数据类型

Redis自己创建的数据类型
- SDS
  - 简单动态字符串SDS
    - C里面一般用字符数组来实现字符串，字符数组是有一些问题的： 1.非二进制安全(也就是说不能包含’\0’，但是可能会有需求在字符串中假如\0这个字符) 2.不可以修改（有些时候我们需要对key进行append操作什么的，所以需要修改字符串）由于C语言字符数组来实现字符串有问题，Redis用着不方便，所以Redis就自己造了个字符串类。
    - Redis会根据字符串的长度进行选择合适的SDS结构体，比如字符串长度小于255，我就给你分配一个可以刚好容纳的下的SDS结构体，所以有不同规格的SDS结构体，可以容纳不同大小的字符串。这样的话是不是就可以节约内存啦
    - SDS之所以叫做动态字符串，是因为它具备动态扩容的能力，例如一个内容为“hi”的SDS结构体
      - 现在要给这个hi后面追加一段字符串“,Amy”，这里首先会申请新内存空间： ● 如果新字符串小于1M，则新空间的大小为扩展后字符串长度的两倍+1； ● 如果新字符串大于1M，则新空间的大小为扩展后字符串长度+1M+1。需要注意的是，下面的新空间的大小是13，但是alloc只显示去掉结束标识’\0’的大小，所以是减去了1。
- IntSet
  - 整数集合IntSet
    - InSet中的整数都是升序存放在底层数组中的他和SDS，按照大小使用不同大小的IntSet结构体，比如数组里如果存放的都是0~32767的数字，就会用int_16编码，如果新添加了一个大于32767的数据，就会自动升级到合适的大小具体流程如下： 1.判断这个新加的这个元素在哪个范围 2.新建对象，分配大小，拷贝源数组到新数组 3.将新加元素加入到新数组末尾有没有发现，这个数据类型只适合存储少量元素，因为如果有一个元素超级大，但是大部分元素都很小，就会很浪费内存。
    - 特点： IntSet中元素唯一，有序类型升级机制，存储不同大小的数据底层查询通过二分查找（用在添加元素或者查找元素）
- Dict
  - Dict由三部分组成，分别是：字典（Dict）、哈希表（Dictht）、哈希节点（DictEntry）看图片，有两个hash表，一个存数据，一个是空，这个空的hash表是在rehash的时候使用的。
    - Dict的新增元素当我们向Dict添加键值对时，Redis首先根据key计算出hash值（h），然后利用 h & sizemask来计算元素应该存储到数组中的哪个索引位置（其实就相当于这个数%size的值）。我们存储k1=v1，假设k1的哈希值h =1，因此k1=v1要存储到数组角标1位置。如果角标1有元素，需要进行链化操作，注意链化是头插，跟Java不一样，Java是尾插，尾插需要遍历整个链表插入，但是解决了多线程下的循环引用问题，但是redis不一样，redis是IO多路复用，就不用担心多线程问题了，直接使用头插提高效率就可以了。
    - Dict的扩容 Dict在每次新增键值对时都会检查负载因子（LoadFactor = used（entry的个数）/size（数组长度）），满足以下两种情况时会触发哈希表扩容： ● 哈希表的 LoadFactor >= 1，并且服务器没有执行 BGSAVE 或者 BGREWRITEAOF 等后台进程（因为这些操作很占用CPU）； ● 哈希表的 LoadFactor > 5 (不用管bgsave等命令，直接进行扩容)；
    - Dict的rehash 扩容/缩容的时候会触发rehash，也就是把旧表的元素重新根据hash算法分配到新表中。但是Dict中的rehash并不是一次性完成的，这点跟Java中的不一样，他是渐进式完成的，称作渐进式rehash。过程如下： 1.计算新表的容量，如果是缩容，新表容量就是第一个大于等于节点数量的2^n。如果是扩容，新表容量是第一个大于等于节点数量+1的2^n(因为要加上一个新节点) 2.按照新的容量申请内存空间，并且赋值给那个空表（用于rehash的那个表） 3.将rehash标志置为0，这个标志位标志着rehash开始（如果为1，就表示移动了1条链表了）。 4.系统每次执行CRUD的时候，都会检查这个标志位是否大于-1（等于-1的时候说明现在这个系统没有在rehash），如果大于-1说明还没rehash结束，就需要继续进行移动，每次移动会移动一条链（也就是数组链化后的那一条），并且把标志位+1。 5. (4的重复执行，直到所有链都移动到新表中。rehash就结束了，但是还要做首尾的工作)把新表和旧表换个位置，让主力表处于0号下标的位置。然后释放旧表的内存。 6.把rehash标志位置为-1，代表rehash结束。此外，在rehash过程中，新增的节点会直接加入到新表中，查询、修改、删除本质上都是查找，找的话新表旧表都会进行找。
    - Dict的收缩 Dict除了扩容以外，每次删除元素时，也会对负载因子做检查，当LoadFactor<0.1时，会做哈希表收缩，直至收缩到第一个大于等于元素的2^n
- ZipList
  - 压缩列表可以看作是一个双端队列。可以在任何一端进行压入/弹出操作。并且他是一块连续的内存，这就导致他不能存储大量数据
    - 对entry中的字段进行解释： ● prelen(previous_entry_length)：前一节点的长度，占1个或5个字节。 ○ 如果前一节点的长度小于254字节，则采用1个字节来保存这个长度值 ○ 如果前一节点的长度大于254字节，则采用5个字节来保存这个长度值，第一个字节为固定值0xfe，后四个字节才是真实长度数据。 ● encoding：编码属性，记录entry-data的数据类型（字符串还是整数）以及长度，要么1个字节，要么2个要么5个字节(具体在笔记里看) ● entry-data：负责保存节点的数据，可以是字符串或整数
    - ZipList的连锁更新问题：现在，假设我们有N个连续的、长度为250字节的entry，因此entry的prelen属性用1个字节即可表示之后头插插入了一个长度等于254字节的entry1，由于之前的节点entry2的大小是250，entry2的prelen的长度是1，但是新加进来需要记录entry1的长度，由于长度是254，所以entry2的prelen需要扩容成5个字节，后面的entry原来大小为250字节的都得扩容，直到有一个entry比较小或者比较大，不在250253这个范围中 ZipList这种特殊情况下产生的连续多次空间扩展操作称之为连锁更新（Cascade Update）。新增、删除都可能导致连锁更新的发生。但是这种概率很小，因为如果不可能一直有N个连续的、长度为250253字节之间的entry在链表中
- QuickList
  - QuickList是一个双端链表，链表中的每个节点都是一个ZipList。解决了ZipList不能存储大量数据的问题。
    - 你可能会问：如果QuickList中每个entry过多，不是还会导致之前的问题吗。redis提供给我们了解决办法，可以进行手动限制每个ZipList的内存大小（默认是每个ZipList不能超过8kb）
- SkipList
  - 跳表，跳表中的元素按照升序排列，每个节点有多个指针指向后面的元素，可能指针跨度不同。但是最多有32级（个）指针。
    - 上面是具体实例跳表增删改查效率与红黑树基本一致，实现却更简单（这就是为什么不用红黑树的原因）
- RedisObject
  - key用一种数据类型：动态字符串。就可以表示了。而value则比较复杂，为了在同⼀个dict内能够存储不同类型的value，这就需要⼀个通⽤的数据结构，这个通用的数据结构就是RedisObject。 RedisObject会根据存储的数据类型不同，选择不同的编码方式。数据类型编码方式 OBJ_STRING int、embstr、raw OBJ_LIST LinkedList和ZipList(3.2以前)、QuickList（3.2以后） OBJ_SET intset、HT OBJ_ZSET ZipList、HT、SkipList OBJ_HASH ZipList、HT