今天来我们来聊一聊redis的数据结构

redis有哪些数据类型？

Sting(字符串)、List(列表)、Hash(哈希)、set(去重无序集合)、zset(去重有序结合)，以上为redis的数据类型

数据类型的应用场景有哪些呢？

字符串(String)

1、缓存 比如：验证码、数据缓存

2、计数 比如：redis 相关命令incr key ，incr命令可以进行自增操作

3、分布式锁

哈希（hash）:hash类型存储时一个键值对

1、用于存储用户信息 比string更加直观

列表(List):

1、队列 例如运用 Lpop Lpush rpop rpush 方法实现队列

2、设计秒杀系统，可以存储秒杀商品

集合（set）: 有序去重集合

1、用户点赞列表

2、抽奖功能

3、用户标签

有序集合(zset)：

1、排行榜

2、点击量排行

redis底层数据结构？

String:

字符串在redis中很常用的，键值对中的key就是字符串类型，值有时也是字符串类型

众所周知，redis时由c语言实现的。但是它没有直接使用c语言中的char类型来实现redis中的string类型，而是自己封装了一个名为SDS(simple dynamic string)的数据结构来表示自己的字符串的，也就是redis String数据类型的底层结构就是SDS。

　　弃用C语言的char类型肯定是有原因的。C语言的字符串其实就是一个字符数组，数组中每个元素时字符串中的一个字符：

　　比如下图：下图为ww字符串的数据结构

　　C语言中，对字符串进行操作时，char 指针只是指向字符数组得起始位置，而字符数组得的结尾位置就用  "\0" 表示，意思是指字符串的结束。

　　所以在C语言中字符串操作函数就通过判断"\0" 决定要不要停止操作。举个例子，strlen函数就是通过检测  "\0"  位置就会停止遍历。这样设计的话，char类型只能存储纯文本字符，并且字符中间时不可以出现 "\0" 字符的，这样就导致不能保存图片、音频、视频等等二进制数据

　　正是因为c语言的char类型的问题存在，就衍生出了redis SDS的数据结构

SDS数据结构设计：

结构种每个元素的介绍：

len 记录了字符串长度，这样在获取字符串长度的时候，只需要返回结构中的成员变量值就行了，

alloc 分配给字符串数组得空间长度，根据key修改值时就可以需改alloc-len计算剩余空间大小，可以用来判断空间是否满足修改需求，不满足的话就会自动扩展至修改所需的大小，然后再执行实际的修改操作

flags 用来表示不同类型的sds，一共有5种类型分别是 sdshdr5、sdshdr8、sdshdr16、sdshdr32 和 sdshdr64

buf[]  字符数组，用来保存实际数据，不仅可以保存字符串，还可以保存二进制数据

redis 的SDS数据结构上比C语言的char 增加了三个元素来解决一些缺陷。

C语言在获取字符串长度时，需要一个一个遍历字符串中的元素，但是redis 的SDS数据结构直接获取 len元素就可以了。想对于C语言而言时间复杂度更高效一些

链表

Redis 的List对象的底层实现之一就是链表。

链表分为 单项链表、双向链表、循环链表

列表的节点结构设计的样子：

typedef struct listNode {
    //前置节点
    struct listNode *prev;
    //后置节点
    struct listNode *next;
    //节点的值
    void *value;
} listNode

上述的数据结构种有前置节点、有后置节点 是一个双向链表结构。

listNode表中有自带了一个prev 、next 指针。指向前一个节点、后一个节点。如果prev  、next都指向null 就证明这个链表时无环链表。

链表中每一个节点之间的内存时不连续得，数组得数据结构在内存存储上是连续得内存，能够很好的利用cpu缓存，可以利用cpu缓存加速数据的访问。

因此，在数据量比较少的情况下list对象会才采用【压缩列表】作为底层数据结构的实现，它的优势在于节省内存空间，并且在内存紧凑型的数据结构。

压缩列表(List对象、Hash对象、Zset对象在数据比较少的情况，会采用压缩列表)：

压缩列表的最大特点，就是它被设计成一种内存紧凑型的数据结构，占用一块连续的内存空间，不仅可以利用 CPU 缓存，而且会针对不同长度的数据，进行相应编码，这种方法可以有效地节省内存开销。

但是，压缩列表的缺陷也是有的：

• 不能保存过多的元素，否则查询效率就会降低；

• 新增或修改某个元素时，压缩列表占用的内存空间需要重新分配，甚至可能引发连锁更新的问题。

压缩列表是redis为了节约内存而开发的，它是由连续得内存空间组成的顺序性数据结构，类似于数组一样。

压缩列表在查找数据时，如果只是查找头部、尾部数据比较简单时间复杂度就是O(1) ,但是如果查找中间其他的元素就需要逐个进行遍历，复杂度就是O(N)了。因此压缩列表不适合存储数据大的数据。

压缩列表节点包含三部分内容：

• prevlen，记录了「前一个节点」的长度；

• encoding，记录了当前节点实际数据的类型以及长度；

• data，记录了当前节点的实际数据；

压缩列表里的每个节点中的  prevlen 属性都记录了「前一个节点的长度」，而且 prevlen 属性的空间大小跟前一个节点长度值有关，比如：

• 如果前一个节点的长度小于 254 字节，那么 prevlen 属性需要用 1 字节的空间来保存这个长度值；

• 如果前一个节点的长度大于等于 254 字节，那么 prevlen 属性需要用 5 字节的空间来保存这个长度值；

上面我们提到了连锁更新问题：

压缩列表除了在查询数据上时间复杂度比较高以外

压缩列表在新增或者修改某个数据的时候，如果空间不够的话，压缩列表占用的内存空间就需要重新分配，而插入的时间元素比较大，可能或导致后面的所有数据的prevlen占用空间都发生变化了，从而引起了【连锁更新问题】，导致每个元素的占用空间都进行分配。

哈希表

哈希表是一种保存键值对（key-value）的数据结构。

哈希表中的每一个 key 都是独一无二的，程序可以根据 key 查找到与之关联的 value，或者通过 key 来更新 value，又或者根据 key 来删除整个 key-value等等。

在讲压缩列表的时候，提到过 Redis 的 Hash 对象的底层实现之一是压缩列表。

Hash 对象的另外一个底层实现就是哈希表。

哈希表优点在于，它能以 O(1) 的复杂度快速查询数据。怎么做到的呢？将 key 通过 Hash 函数的计算，就能定位数据在表中的位置，因为哈希表实际上是数组，所以可以通过索引值快速查询到数据。

但是存在的风险也是有，在哈希表大小固定的情况下，随着数据不断增多，那么哈希冲突的可能性也会越高。

Redis 采用了「链式哈希」来解决哈希冲突，在不扩容哈希表的前提下，将具有相同哈希值的数据串起来，形成链接起，以便这些数据在表中仍然可以被查询到。

typedef struct dictht {
    //哈希表数组
    dictEntry **table;
    //哈希表大小
    unsigned long size;  
    //哈希表大小掩码，用于计算索引值
    unsigned long sizemask;
    //该哈希表已有的节点数量
    unsigned long used;
} dictht;

哈希冲突：当有两个以上数量的 key 被分配到了哈希表中同一个哈希桶上时，此时称这些 key 发生了冲突。

Redis 采用了「链式哈希」的方法来解决哈希冲突。也可以采用开发寻址法解决hash冲突，不过开发寻址法在数据量比较大情况下，影响性能。

实现的方式就是每个哈希表节点都有一个 next 指针，用于指向下一个哈希表节点，因此多个哈希表节点可以用 next 指针构成一个单项链表，被分配到同一个哈希桶上的多个节点可以用这个单项链表连接起来，这样就解决了哈希冲突。

当链表长度的增加，哈希冲突就越来越严重，对于查询数据而言时间复杂度就时O(N)了

rehash：

哈希表结构设计的这一小节，我给大家介绍了 Redis 使用 dictht 结构体表示哈希表。不过，在实际使用哈希表时，Redis 定义一个 dict 结构体，这个结构体里定义了两个哈希表（ht[2]）。

typedef struct dict {
    …
    //两个Hash表，交替使用，用于rehash操作
    dictht ht[2]; 
    …
} dict;

之所以定义了 2 个哈希表，是因为进行 rehash 的时候，需要用上 2 个哈希表了。

在正常服务请求阶段，插入的数据，都会写入到「哈希表 1」，此时的「哈希表 2 」 并没有被分配空间。

随着数据逐步增多，触发了 rehash 操作，这个过程分为三步：

• 给「哈希表 2」 分配空间，一般会比「哈希表 1」 大 2 倍；

• 将「哈希表 1 」的数据迁移到「哈希表 2」 中；

• 迁移完成后，「哈希表 1 」的空间会被释放，并把「哈希表 2」 设置为「哈希表 1」，然后在「哈希表 2」 新创建一个空白的哈希表，为下次 rehash 做准备。

伴随着数据量越来越大，在数据迁移过程中就会给redis造成阻塞，redis服务就没办法处理其他的请求。

渐进式hash：

     1、在 rehash 进行期间，每次哈希表元素进行新增、删除、查找或者更新操作时，Redis 除了会执行对应的操作之外，还会顺序将「哈希表 1 」中索引位置上的所有 key-value 迁移到「哈希表 2」 上

     2、随着处理客户端发起的哈希表操作请求数量越多，最终在某个时间嗲呢，会把「哈希表 1 」的所有 key-value 迁移到「哈希表 2」，从而完成 rehash 操作。

     3、这样就巧妙地把一次性大量数据迁移工作的开销，分摊到了多次处理请求的过程中，避免了一次性 rehash 的耗时操作。

触发 rehash 操作的条件，主要有两个：

• 当负载因子大于等于 1 ，并且 Redis 没有在执行 bgsave 命令或者 bgrewiteaof 命令，也就是没有执行 RDB 快照或没有进行 AOF 重写的时候，就会进行 rehash 操作。

• 当负载因子大于等于 5 时，此时说明哈希冲突非常严重了，不管有没有有在执行 RDB 快照或 AOF 重写，都会强制进行 rehash 操作。

整数集合：（set对象的底层数据结构就是整数集合）

　　当set对象的数据对象时包含了整数值元素，并且元素的数量不多时，就会采用了整数集合作为数据结构。

typedef struct intset {
    //编码方式
    uint32_t encoding;
    //集合包含的元素数量
    uint32_t length;
    //保存元素的数组
    int8_t contents[];
} intset;

跳表（zset对象采用了跳表数据结构）：

　　Redis 只有在 Zset 对象的底层实现用到了跳表，跳表的优势是能支持平均 O(logN) 复杂度的节点查找。

　　Zset 对象是唯一一个同时使用了两个数据结构来实现的 Redis 对象，这两个数据结构一个是跳表，一个是哈希表。这样的好处是既能进行高效的范围查询，也能进行高效单点查询。

typedef struct zset {
    dict *dict;
    zskiplist *zsl;
} zset;