• 1.1 Redis有哪些数据类型
• 1.2 Redis本质是哈希表
• 1.3 Redis的哈希冲突与渐进式rehash
• 1.4 数据结构底层
  • 1.4.1 简单动态字符串SDS
  • 1.4.2 双向链表LinkedList（后续已废弃）
  • 1.4.3 压缩列表ZipList
  • 1.4.4 哈希表HashTable
  • 1.4.5 跳表SkipList
  • 1.4.6 整数数组IntSet
  • 1.4.7 RedisObject
  • 1.4.8 Redis的编码方式

• 3.1 简介
• 3.2 数据结构
• 3.3 压缩列表ZipList
• 3.4 双向链表LinkedList（后续已废弃）
• 3.5 快速链表QuickList

• 5.1 简介
• 5.2 数据结构

• 6.1 简介
• 6.2 什么时候采用压缩列表、什么时候采用跳表
• 6.3 跳表
  • 6.3.1 跳表是什么（what）
  • 6.3.2 跳表怎么做的（how）
  • 6.3.3 为什么需要跳表（WHY）
  • 6.3.4 为什么用跳表而不用红黑树或者二叉树呢
  • 6.3.5 zset为什么用跳表而不用二叉树或者红黑树呢，MySQL为什么不用跳表

一、Redis数据结构概述

1.1 Redis有哪些数据类型

1.2 Redis本质是哈希表

• 一个哈希表，其实就是一个数组，数组的每个元素称为一个哈希桶。也就是说，一个哈希表是由多个哈希桶组成的，每个哈希桶中保存了键值对数据；
• 不管是键类型还是值类型，哈希桶中的元素保存的都不是值本身，而是指向具体值的指针

• 哈希表的最大好处是可以用 O(1) 的时间复杂度来快速查找到键值对——我们只需要计算键的哈希值，就可以知道它对应的哈希桶位置，然后就可以访问相应的 Entry元素；
• 这个查找过程主要依赖于哈希计算，和数据量的多少并没有直接关系。也就是说，不管哈希表里有 10 万个键还是 100 万个键，我们只需要一次计算就能找到相应的键。

1.3 Redis的哈希冲突与渐进式rehash

1.4 数据结构底层

1.4.1 简单动态字符串SDS

1. 无法存储“\0”这种特殊字符，因为“\0”代表结束（非二进制安全）；
2. 每次字符串扩容和缩容，都需要使用新的char数组；
3. 没有记录字符串的长度，每次都需要进行遍历到结束、或者通过运算 才能知道长度。
4. 不可修改

• 获取字符串长度的时间复杂度为O(1)
• 支持动态扩容
• 减少内存分配次数
• 二进制安全。遍历字符串时不是以介绍标识为标记、而是以长度为基准，

• len：目前已使用的长度；
• alloc：buf的总长度，就是已经分配空间的长度;
• flags：sds的类型，用低三位标识，高5位暂时不用。sdshdr5这种类型该字段为空；sdshdr8、sdshdr16、sdshdr32、sdshdr64用标识进行表示。
• buf：保存具体的字符串。注意这里也会以\0结尾，但它不会计算在len中。

1.4.2 双向链表LinkedList（后续已废弃）

• 双端：链表节点带有 prev 和 next 指针，获取某个节点的前一节点和后一节点的复杂度都是 O(1)；
• 无环：表头节点的 prev 指针和表尾节点的 next 指针都指向 NULL，对链表的访问以 NULL 为终点；
• 表头指针/表尾指针：通过 list 结构的 head 指针和 tail 指针，获取链表的表头节点和表尾节点的复杂度为 O(1)；
• 链表长度计数器：通过 list 结构的 len 属性来对 list 的链表节点进行计数，获取节点数量的复杂度为O(1)；
• 多态：链表节点使用 void* 指针来保存节点值，并通过 list 结构的 dup、free、match 三个属性为节点值设置类型特定函数，所以链表可以用于保存各种不同类型的值。
• 使用链表的附加空间相对太高，因为 64bit 系统中指针是 8 个字节，所以 prev 和 next 指针需要占据 16 个字节，且链表节点在内存中单独分配，会加剧内存的碎片化，影响内存管理效率

1.4.3 压缩列表ZipList

• 如果查找定位首个元素或最后1个元素，可以通过表头 “zlbytes”、“zltail_offset” 元素快速获取，复杂度是 O(1)。但是查找其他元素时，就没有这么高效了，只能逐个查找下去，比如 entryN 的复杂度就是 O(N)
• ZipList虽然节省内存，但申请内存必须是连续空间，如果内存占用较多，申请效率较低。

1.4.4 哈希表HashTable

  
  
  
  
  
  

   
   
   
   
   
   

    typedef struct dictEntry {
   
   
   
   
   
   
   
   
   
   
   
   

        void *key;
   
   
   
   
   
   
   
   
   
   
   
   

        void *val;
   
   
   
   
   
   
   
   
   
   
   
   

        struct dictEntry *next;
   
   
   
   
   
   
   
   
   
   
   
   

    } dictEntry;
   
   
   
   
   
   
   
   
   
   
   
   

    
   
   
   
   
   
   
   
   
   
   
   
   

    typedef struct dictht {
   
   
   
   
   
   
   
   
   
   
   
   

        dictEntry **table;
   
   
   
   
   
   
   
   
   
   
   
   

        unsigned long size;
   
   
   
   
   
   
   
   
   
   
   
   

        unsigned long sizemask;
   
   
   
   
   
   
   
   
   
   
   
   

        unsigned long used;
   
   
   
   
   
   
   
   
   
   
   
   

    } dictht;
   
   
   
   
   
   
   
   
   
   
   
   

    
   
   
   
   
   
   
   
   
   
   
   
   

    typedef struct dict {
   
   
   
   
   
   
   
   
   
   
   
   

        dictht ht[2];
   
   
   
   
   
   
   
   
   
   
   
   

        long rehashidx; /* rehashing not in progress if rehashidx == -1 */
   
   
   
   
   
   
   
   
   
   
   
   

        int iterators; /* number of iterators currently running */
   
   
   
   
   
   
   
   
   
   
   
   

    } dict;
   
   
   
   
   
   
  
  
  
  
  
  

• dictEntry 结构体表示散列表中的一个节点，包含键（key）、值（val）和指向下一个节点的指针（next）。
• dictht 结构体表示一个散列表，包含指向哈希表数组的指针（table）、哈希表数组的大小（size）、哈希表数组大小掩码（sizemask）和已使用的节点数量（used）。
• dict 结构体表示一个字典，包含两个散列表（ht）、当前进行 rehash 的索引（rehashidx）和当前运行的迭代器数量（iterators）。

1.4.5 跳表SkipList

• 元素按照升序排列存储
• 节点可能包含多个指针，指针跨度不同

• 跳跃表是一个双向链表，每个节点都包含score和ele值
• 节点按照score值排序，score值一样则按照ele字典排序
• 每个节点都可以包含多层指针，层数是1到32之间的随机数
• 不同层指针到下一个节点的跨度不同，层级越高，跨度越大
• 增删改查效率与红黑树基本一致，实现却更简单

1.4.6 整数数组IntSet

1. 升级编码为INTSET_ENC_INT32，每个整数占4字节，并按照新的编码方式及元素个数扩容数组
2. 倒序依次将数组中的元素拷贝到扩容后的正确位置
3. 将待添加的元素放入数组末尾
4. 最后，将inset的encoding属性改为INTSET_ENC_INT32，将length属性改为4

1.4.7 RedisObject

1.4.8 Redis的编码方式

二、String类型

• 缓存：将查询结果、页面内容等缓存在 Redis 的 String 结构中，提高系统访问速度。
• 计数器：Redis String 结构可以将字符串解析为整数进行自增或自减操作，适合做各种计数器。
• 分布式锁：利用 Redis String 结构的原子性操作，可以实现分布式锁。

1. 无法存储“\0”这种特殊字符，因为“\0”代表结束；
2. 每次字符串扩容和缩容，都需要使用新的char数组；
3. 没有记录字符串的长度，每次都需要进行遍历到结束才能知道长度。

• len：目前已使用的长度；
• alloc：buf的总长度，就是已经分配空间的长度;
• flags：sds的类型，用低三位标识，高5位暂时不用。sdshdr5这种类型该字段为空；sdshdr8、sdshdr16、sdshdr32、sdshdr64用标识进行表示。
• buf：保存具体的字符串。注意这里也会以\0结尾，但它不会计算在len中。

• int：8字节的长整形，值时数字类型，并且数字长度小于20；
• embstr：长度小于等于44字节的字符串；（3.2版本之前是39字节）
• raw：长度大于44字节的字符串。

三、List列表类型

3.1 简介

• 消息队列：可以利用 List 的 push 和 pop 操作，实现生产者消费者模型。
• 时间线、动态消息：比如微博的时间线，可以将最新的内容放在 List 的最前面。
• 常用来存储一个有序数据，例如：朋友圈点赞列表，评论列表等

• 在3.2版本之前，Redis List底层采用压缩链表ZipList和双向链表LinkedList来实现List。当元素数量小于512并且元素大小小于64字节时采用ZipList编码，超过则将自动采用LinkedList编码
• 在3.2版本之后，Redis统一采用快速链表QuickList来实现List

3.2 数据结构

• 在Redis 3.2版本之前，Redis List底层采用压缩链表ZipList和双向链表LinkedList来实现List。当元素数量小于512个并且元素大小小于64字节时采用ZipList编码，超过则将自动采用LinkedList编码。
• 在3.2版本之后，Redis统一采用快速链表QuickList结构来实现List

• 压缩列表 ZipList：插入元素过多或字符串太大，就需要调用 Realloc 扩展内存；
• 双向链表 LinkedList：需附加指针 Prev 和 Next，较浪费空间，加重内存的碎片化

3.3 压缩列表ZipList

• 如果查找定位首个元素或最后1个元素，可以通过表头 “zlbytes”、“zltail_offset” 元素快速获取，复杂度是 O(1)。但是查找其他元素时，就没有这么高效了，只能逐个查找下去，比如 entryN 的复杂度就是 O(N)
• ZipList虽然节省内存，但申请内存必须是连续空间，如果内存占用较多，申请效率较低。

3.4 双向链表LinkedList（后续已废弃）

3.5 快速链表QuickList

• 是一个节点为ZipList的双端链表
• 节点采用ZipList，解决了传统链表的内存占用问题
• 控制了ZipList大小，解决连续内存空间申请效率问题
• 中间节点可以压缩，进一步节省了内存

四、Set集合类型

• 不保证有序性
• 保证元素唯一（可以判断元素是否存在）
• 求交集、并集、差集

1. 社交网络中的好友关系、共同好友、二度好友等功能。
2. 利用集合支持的交集、并集、差集等操作，可以计算共同喜好、全部的喜好、自己独有的喜好等。

• 为了查询效率和唯一性，Set采用HT编码（Dict）。Dict中的key用来存储元素，Value统一为null。
• 当存储的所有数据都是整数，并且元素数量不超过set-max-intset-entries时，Set会采用lntSet编码，以节省内存。

1. 集合中的元素是无序的，如果需要获取有序的数据，可以使用 Sorted Set 数据类型。
2. 集合中的元素不允许重复，如果需要存储重复元素，可以使用 List 数据类型。

五、Hash哈希类型

5.1 简介

• 都是键值存储
• 都需求根据键获取值
• 键必须唯一

• zset的键是member，值是score；hash的键和值都是任意值
• zset要根据score排序；hash则无需排序

• 存储对象：Hash 结构可以看作是 String 类型的 field 和 value 的映射表，非常适合用于存储对象。例如，你可以使用 Hash 类型存储用户的信息，如用户名、密码、邮箱等；
• 数据缓存：可以将数据库中的一条记录映射成一个 Hash 结构，Hash 的每个字段对应记录的每个列；
• 数据分析：你可以使用 Hash 类型存储各种统计数据，例如用户的行为数据，然后进行数据分析；
• 社交网络：在社交网络应用中，你可以使用 Hash 类型存储用户的朋友列表、粉丝列表等

• Hash结构默认采用ZipList编码，用以节省内存。ZipList中相邻的两个entry分别保存field和value
• 当数据量较大时，Hash结构会转为HT编码，也就是Dict，触发条件有两个：
  • ZipList中的元素数量超过了hash-max-ziplist-entries（默认512）
  • ZipList中的任意entry大小超过了hash-max-ziplist-value（默认64字节）

5.2 数据结构

• Hash结构默认采用ZipList编码，用以节省内存。ZipList中相邻的两个entry分别保存field和value
• 当数据量较大时，Hash结构会转为HT编码，也就是Dict，触发条件有两个：
  • ZipList中的元素数量超过了hash-max-ziplist-entries（默认512）
  • ZipList中的任意entry大小超过了hash-max-ziplist-value（默认64字节）

• hash-max-ziplist-entries：这个参数用于设置压缩列表可以存储的最大节点数量。如果一个 Hash 类型的元素数量超过这个值，那么就会从压缩列表切换到散列表。默认值为 512；
• hash-max-ziplist-value：这个参数用于设置压缩列表中每个节点的最大值大小（以字节为单位）。如果一个 Hash 类型的任何元素的大小超过这个值，那么就会从压缩列表切换到散列表。默认值为 64。

• 从压缩列表转换到散列表：当 Hash 类型存储的字段和值的数量超过 hash-max-ziplist-entries 的值，或者任何字段或值的大小超过 hash-max-ziplist-value 的值时，Redis 会将底层结构从压缩列表转换为散列表。这个过程是自动进行的，对用户来说是透明的。
• 从散列表转换到压缩列表：一旦 Hash 类型的底层结构被转换为散列表，就无法再转换回压缩列表。这是因为散列表的性能更高，而且在大多数情况下，一旦一个 Hash 类型的大小超过了一定的阈值，那么它的大小就很可能会继续增长。

六、ZSet类型

6.1 简介

• 可排序。根据score值排序
• 元素不重复，member必须唯一
• 查询速度快，也可以根据member查询分数

• 排行榜应用：有序集合使得我们能够方便地实现排行榜，比如网站的文章排行、学生成绩排行等。
• 带权重的消息队列：可以通过 score 来控制消息的优先级。

• Redis ZSet 的底层实现为跳跃列表和哈希表两种，跳跃列表保证了元素的排序和快速的插入性能，哈希表则提供了快速查找的能力。
• 当元素数量不多时，HT和SkipList的优势不明显，而且更耗内存。因此zset还会采用ZipList结构来节省内存，不过需要同时满足两个条件：
  • 元素数量小于zset_max_ziplist_entries，默认值128
  • 每个元素都小于zset_max_ziplist_value字节，默认值64

• ZipList是连续内存，因此score和element是紧挨在一起的两个entry，element在前，score在后
• score越小越接近队首，score越大越接近队尾，按照score值升序排列

1. 有序集合中的元素是唯一的，但分数（score）可以重复。
2. 插入、删除、查找的时间复杂度都是 O(log(N))。对于获取排名（排行榜）的操作，Redis 有序集合是非常高效的。

6.2 什么时候采用压缩列表、什么时候采用跳表

• 有序集合保存的元素数量小于128个
• 有序集合保存的所有元素的长度小于64字节

6.3 跳表

6.3.1 跳表是什么（what）

• 元素按照升序排列存储
• 节点可能包含多个指针，指针跨度不同

• 跳跃表是一个双向链表，每个节点都包含score和ele值
• 节点按照score值排序，score值一样则按照ele字典排序
• 每个节点都可以包含多层指针，层数是1到32之间的随机数
• 不同层指针到下一个节点的跨度不同，层级越高，跨度越大
• 增删改查效率与红黑树基本一致，实现却更简单

6.3.2 跳表怎么做的（how）

6.3.3 为什么需要跳表（WHY）

6.3.4 为什么用跳表而不用红黑树或者二叉树呢

• ZSet有个核心操作，范围查找：跳表效率比红黑树高，跳表可以做到 logn 时间复杂度内，快速查找，找到区间起点、依次往后遍历即可，但红黑树范围查找的效率没有跳表高（每一层加了指针）
• 跳表实现比红黑树及平衡二叉树简单、易懂：可以有效控制跳表的索引层级来控制内存的消耗，

6.3.5 zset为什么用跳表而不用二叉树或者红黑树呢，MySQL为什么不用跳表

七、Stream类型

• 消息队列：Stream 可以作为生产者消费者模型的一种实现，生产者添加消息到 Stream，消费者从 Stream 中读取消息并处理。
• 日志记录：由于 Stream 中的每个元素都有唯一的 ID，并且这个 ID 是自动递增的，因此非常适合用来记录日志。