Redis面试（二）：数据结构

2. 数据结构

2.1 Redis有哪些数据结构？

Redis有以下这五种基本类型：

• String（字符串）：SDS 简单动态字符串
• List（列表）：SDS 简单动态字符串
• Hash（字典）：哈希表、压缩列表
• Set（集合）：哈希表、整数集合
• zset（有序集合）：压缩列表、skiplist 跳表

它还有三种特殊的数据结构类型

• Bitmap（位存储）：用一个比特位来映射某个元素的状态，在Redis中，它的底层是基于字符串类型实现的，可以把bitmaps成作一个以比特位为单位的数组。
• Geospatial（地理位置）：地理位置定位，用于存储地理位置信息，并对存储的信息进行操作。
• Hyperloglog（基数统计）：用来做基数统计算法的数据结构，如统计网站的UV。

2.1.1 String（SDS）

1. 介绍

String 是最常用的一种数据类型，普通的 key- value 存储都可以归为此类。其中 Value 既可以是数字也可以是字符串。使用场景：常规 key-value 缓存应用。常规计数: 微博数， 粉丝数。

底层结构：SDS（简单动态字符串）

虽然 Redis 是用 C 语言写的，但是 Redis 并没有使用 C 的字符串表示，而是自己构建了一种 简单动态字符串（Simple Dynamic String，SDS）。

相比于 C 的原生字符串，Redis 的 SDS 不光可以保存文本数据还可以保存二进制数据，并且获取字符串长度复杂度为 O(1)（C 字符串为 O(N)）, 除此之外，Redis 的 SDS API 是安全的，不会造成缓冲区溢出。

SDS结构如下：

 struct sdshdr{ 
     unsigned int len;   // 记录buf数组中已使用字节的数量
     unsigned int free;  // 记录 buf 数组中未使用字节的数量 
     char buf[];         // 字节数组，用于保存字符串
 }

SDS 结构图如下：

2. 常用命令

3. 应用场景

1. 需要存储常规数据的场景：
   • 举例 ：缓存 session、token、图片地址、序列化后的对象 (相比较于 Hash 存储更节省内存)。
   • 相关命令 ： SET、GET
2. 需要计数的场景：
   • 举例 ：用户单位时间的请求数（简单限流可以用到）、页面单位时间的访问数。
   • 相关命令 ：SET、GET、INCR、DECR
3. 分布式锁： 利用 SETNX key value 命令可以实现一个最简易的分布式锁（存在一些缺陷，通常不建议这样实现分布式锁）

2.1.2 Hash（压缩列表、哈希表）

1. 介绍

哈希是一种键值对的集合，其中每个键都对应一个值。哈希适合存储对象或实体的相关属性，可以快速进行单个字段的读写操作。底层实现使用哈希表来存储。

底层结构：ziplist（压缩列表）、hashmap（哈希表）

字符串和哈希类型对比如下图：

2. 常用命令

3. 应用场景

1. 对象数据存储场景：
   • 举例 ：用户信息、商品信息、文章信息、购物车信息。
   • 相关命令 ：HSET （设置单个字段的值）、HMSET（设置多个字段的值）、HGET（获取单个字段的值）、HMGET（获取多个字段的值）

2.1.3 List（压缩列表、双向链表）

1. 介绍

列表（list）类型是用来存储多个有序的字符串，一个列表最多可以存储2^32-1个元素。

底层结构：ziplist（压缩列表）、linkedlist（双向链表）

一图看懂list类型的插入与弹出：

List应用场景参考以下：

• lpush+lpop=Stack（栈）
• lpush+rpop=Queue（队列）
• lpsh+ltrim=Capped Collection（有限集合）
• lpush+brpop=Message Queue（消息队列）

2. 常用命令

3. 应用场景

1. 信息流展示：
   • 举例 ：最新文章、最新动态。
   • 相关命令 ： LPUSH、LRANGE。
2. 消息队列： Redis List 数据结构可以用来做消息队列，只是功能过于简单且存在很多缺陷，不建议这样做。 相对来说，Redis 5.0 新增加的一个数据结构 Stream 更适合做消息队列一些，只是功能依然非常简陋。和专业的消息队列相比，还是有很多欠缺的地方比如消息丢失和堆积问题不好解决。

2.1.4 Set（整数集合、哈希表）

1. 介绍

Redis 中的 Set 类型是一种无序集合，集合中的元素没有先后顺序但都唯一。

当你需要存储一个列表数据，又不希望出现重复数据时，Set 是一个很好的选择，并且 Set 提供了判断某个元素是否在一个 Set 集合内的重要接口，这个也是 List 所不能提供的。

你可以基于 Set 轻易实现交集、并集、差集的操作，比如你可以将一个用户所有的关注人存在一个集合中，将其所有粉丝存在一个集合。这样的话，Set 可以非常方便的实现如共同关注、共同粉丝、共同喜好等功能。这个过程也就是求交集的过程。

底层结构：intset（整数集合）、hashtable（哈希表）

2. 常用命令

3. 应用场景

1. 需要存放的数据不能重复的场景
   • 举例：网站 UV 统计（数据量巨大的场景还是 HyperLogLog 更适合一些）、文章点赞、动态点赞等场景。
   • 相关命令：SCARD（获取集合数量）
2. 需要获取多个数据源交集、并集和差集的场景
   • 举例 ：共同好友 (交集)、共同粉丝 (交集)、共同关注 (交集)、好友推荐（差集）、音乐推荐（差集） 、订阅号推荐（差集 + 交集） 等场景。
   • 相关命令：SINTER（交集）、SINTERSTORE（交集）、SUNION （并集）、SUNIONSTORE（并集）、SDIFF（差集）、SDIFFSTORE （差集）。
   • 集合类型比较典型的使用场景是标签 (tag). 例如一个用户可能对音乐感兴趣, 另一个用户对新闻感兴趣, 这些想去点就是标签. 有了这些数据就可以获得喜欢同一个标签的人, 以及用户的共同喜好的标签, 这些数据对于用户体验来说比较重要.
3. 需要随机获取数据源中的元素的场景：
   • 举例 ：抽奖系统、随机。
   • 相关命令：SPOP（随机获取集合中的元素并移除，适合不允许重复中奖的场景）、SRANDMEMBER（随机获取集合中的元素，适合允许重复中奖的场景）

2.1.5 Zset（压缩列表、跳跃表）

1. 介绍

Sorted Set 类似于 Set，但和 Set 相比，Sorted Set 增加了一个权重参数 score，使得集合中的元素能够按 score 进行有序排列，还可以通过 score 的范围来获取元素的列表。

底层结构：ziplist（压缩列表）、skiplist（跳跃表）。

2. 常用命令

3. 应用场景

1. 需要随机获取数据源中的元素根据某个权重进行排序的场景：
   • 举例 ：各种排行榜比如直播间送礼物的排行榜、朋友圈的微信步数排行榜、王者荣耀中的段位排行榜、话题热度排行榜等等。
   • 相关命令 ：ZRANGE (从小到大排序) 、 ZREVRANGE （从大到小排序）、ZREVRANK (指定元素排名)。
2. 需要存储的数据有优先级或者重要程度的场景：
   • 举例 ：优先级任务队列。
   • 相关命令 ：ZRANGE (从小到大排序) 、 ZREVRANGE （从大到小排序）、ZREVRANK (指定元素排名)。

我正在参与2023腾讯技术创作特训营第二期有奖征文，瓜分万元奖池和键盘手表