【每日八股】Redis篇（二）：数据结构

Redis 数据类型？

主要有 STRING、LIST、ZSET、SET 和 HASH。

STRING

String 类型底层的数据结构实现主要是 SDS（简单动态字符串），其主要应用场景包括：

缓存对象：可以用 STRING 缓存整个对象的 JSON；
计数：Redis 处理命令是单线程，所以执行命令的过程是原子的。故 String 适合技术场景，比如计算访问次数、点赞、转发、库存数量等；
分布式锁：利用 SETNX 命令；
共享 Session 信息：服务器都会去同一个 Redis 获取相关的 Session 信息，解决了分布式系统下 Session 存储的问题；

LIST

LIST 类型底层采用双向链表和压缩列表实现。

若列表元素个数小于 512 个，其元素值小于 64 bytes，Redis 用压缩列表作为 List 类型的底层数据结构；
否则使用双向链表；

Redis 3.2 之后，List 类型底层只由 quicklist 实现。Redis 7.0 之后，压缩列表数据结构被废弃，由 listpack 实现。

LIST 的应用场景包括：

微信朋友圈点赞：要求按照点赞顺序显示点赞好友的信息，如果点赞取消则移除相应的好友信息；
消息队列：可以使用左进右出的命令组成来完成队列的设计。

HASH

Hash 类型的底层数据结构是由压缩列表或哈希表实现的：

如果哈希类型元素个数小于 512 个，所有值小于 64 字节的话，Redis 会使用压缩列表作为 Hash 类型的底层数据结构；
如果哈希类型元素不满足上面条件，Redis 会使用哈希表作为 Hash 类型的底层数据结构。

在Redis 7.0 中，压缩列表数据结构被废弃，交由 listpack 来实现。HASH 应用场景主要有：

缓存对象：一般采用 String + JSON 存储，对象中某些频繁变化的属性可以考虑抽出来用 Hash 类型存储；
购物车：以用户 id 为 key，商品 id 为 field，商品数量为 value，恰好构成了购物车的3个要素。

SET

Set 类型的底层数据结构是由哈希表或整数集合实现的：

如果集合中的元素都是整数且元素个数小于 512个，Redis 会使用整数集合作为 Set 类型的底层数据结构；
如果集合中的元素不满足上面条件，则 Redis 使用哈希表作为 Set 类型的底层数据结构。

为什么 Redis 中的 SET 是 Key-Value 结构？

原因在于，Redis 是一个键值对数据库，其中的所有数据类型（String、List、Hash、Set、Sorted Set 等）都以 key-value 的形式存储。对于 Set 来说，key 是集合名称，value 是集合的内容。

SET 应用的主要场景：

点赞：key 是文章 id、value 是用户 id；
共同关注：Set 类型支持交集运算，故可用来计算共同好友或共同关注的公众号。key 是用户 id，value 是已关注的公众号的 id；
去重：存储某活动中中奖的用户名，Set 类型因为有去重功能，可以保证同一个用户不会中奖两次。

ZSET

ZSET 类型（Sorted Set，有序集合）可以根据元素的权重来排序，可以自己来决定每个元素的权重值。比如说，可以根据元素插入Sorted Set 的时间确定权重值，先插入的元素权重小，后插入的元素权重大。应用场景主要有：

在面对需要展示最新列表、排行榜等场景时，如果数据更新频繁或者需要分页显示，可以优先考虑使用 ZSET；
有序集合比较典型的使用场景就是排行榜。例如学生成绩的排名榜、游戏积分排行榜、视频播放排名、电商系统中商品的销量排名等。

BITMAP

bit 是计算机中最小的单位，使用它进行储存将非常节省空间，特别适合一些数据量大且使用二值统计的场景。可以用于签到统计、判断用户登陆态等操作。

HyperLogLog

HyperLogLog用于统计，统计规则是基于概率完成的，不准确，标准误算率是 0.81%。优点是，在输入元素的数量或者体积非常非常大时，所需的内存空间总是固定的、并且很小。比如百万级网页 UV 计数等；

GEO

主要用于存储地理位置信息，并对存储的信息进行操作。底层是由Zset实现的，使用GeoHash编码方法实现了经纬度到Zset中元素权重分数的转换，这其中的两个关键机制就是「对二维地图做区间划分」和「对区间进行编码」。一组经纬度落在某个区间后，就用区间的编码值来表示，并把编码值作为Zset元素的权重分数。

Stream

Redis专门为消息队列设计的数据类型。相比于基于 List 类型实现的消息队列，有这两个特有的特性：自动生成全局唯一消息ID，支持以消费组形式消费数据。

之前方法缺陷：不能持久化，无法可靠的保存消息，并且对于离线重连的客户端不能读取历史消息。

Redis 底层数据结构？

SDS

SDS 不仅可以保存字符串，还可以保存二进制数据。

SDS 可以在 O(1) 内获取字符串长度，因为有 Len 属性。

SDS 不会发生缓冲区溢出，因为 SDS 在拼接字符串之前会检查空间是否满足要求，如果空间不够那么就自动扩容，故不会导致缓冲区溢出的问题。

链表

Redis 封装了名为 listNode 的数据结构，并构成双向链表。双向链表包括节点数量len，以及可以自定义实现的 dup、free、match 函数。

listNode 链表结点的结构中只包含 prev 和 next 指针；
list 提供了 head 和 tail 指针，因此获取链表首尾元素的时间复杂度为O(1)。

缺点：

链表每个节点之间的内存都是不连续的，无法很好利用 CPU 缓存。能很好利用CPU缓存的数据结构是数组，因为数组的内存是连续的。
保存一个链表节点的值都需要一个链表节点结构头的分配，内存开销较大。

压缩列表

压缩列表是由连续内存块组成的顺序型数据结构，类似于数组。不仅可以利用 CPU 缓存，而且会针对不同长度的数据，进行相应编码，这种方法可以有效地节省内存开销。不能保存过多的元素，否则查询效率就会降低；新增或修改某个元素时，压缩列表占用的内存空间需要重新分配，甚至可能引发连锁更新的问题。

缺点：

空间扩展操作也就是重新分配内存，因此连锁更新一旦发生，就会导致压缩列表占用的内存空间要多次重新分配，直接影响到压缩列表的访问性能。
如果保存的元素数量增加了，或是元素变大了，会导致内存重新分配，会有连锁更新的问题。
压缩列表只会用于保存的节点数量不多的场景，只要节点数量足够小，即使发生连锁更新也能接受。

哈希

哈希表是一种保存键值对(key-value)的数据结构。优点在于能以O(1)的复杂度快速查询数据。Redis 采用了拉链法来解决哈希冲突，在不扩容哈希表的前提下，将具有相同哈希值的数据串起来，形成链接。

跳表

跳表（Skip List）是一种基于有序链表的数据结构，通过添加多级索引来实现高效的查找、插入和删除操作。跳表的平均时间复杂度为 O(log n)，接近平衡树的性能，但实现更简单。

跳表的核心思想

一. 多层链表

跳表由多层链表组成，最底层是完整的有序链表，每一层都是下一层的“索引”；
每一层的元素是随机选择的，高层元素少，低层元素多；

二. 跳跃查找：

查找时从最高层开始，如果当前节点的下一个节点小于目标值，则向右移动；否则向下移动一层。
通过跳跃查找，可以快速缩小查找范围。

三. 随机化

插入新节点时，通过随机算法决定节点的高度（即层数），保证跳表的平衡性。

整数集合

整数集合本质上是一块连续内存空间。

整数集合有一个升级规则，就是当将一个新元素加入到整数集合里面，如果新元素的类型（int32_t）比整数集合现有所有元素的类型（int16_t）都要长时，整数集合需要先进行升级，也就是按新元素的类型（int32_t）扩展 contents 数组的空间大小，然后才能将新元素加入到整数集合里，升级的过程中也要维持整数集合的有序性。

quicklist

其实 quicklist 就是双向链表 + 压缩列表组合，quicklist 就是一个链表，而链表中的每个元素又是一个压缩列表。quicklist 解决办法，通过控制每个链表节点中的压缩列表的大小或者元素个数，来规避连锁更新的问题。因为压缩列表元素越少或越小，连锁更新带来的影响就越小，从而提供了更好的访问性能。

listpack

listpack 没有压缩列表中记录前一个节点长度的字段了，listpack 只记录当前节点的长度，当向 listpack 加入一个新元素的时候，不会影响其他节点的长度字段的变化，从而避免了压缩列表的连锁更新问题。

为什么用跳表而不用平衡树？

从内存占用上来说，跳表比平衡树更灵活一些：平衡树每个结点包含 2 个指针，而跳表每个结点平均包含 1/(1-p)。
在做范围查找的时候，跳表比平衡树操作要简单：在平衡树上，找到指定范围的小值之后，还需要以中序遍历的顺序继续寻找其它不超过大值的节点。如果不对平衡树进行一定的改造，这里的中序遍历并不容易实现。而在跳表上进行范围查找就非常简单，只需要在找到小值之后，对第 1 层链表进行若干步的遍历就可以实现。
从算法的实现难度上来说，跳表比平衡树要简单很多：平衡树的插入和删除操作可能引发子树的调整，逻辑复杂，而跳表的插入和删除只需要修改相邻节点的指针，操作简单又快速。