共计 4953 个字符，预计需要花费 13 分钟才能阅读完成。
自动写代码机器人，免费开通
这篇文章主要介绍了 Redis 中数据结构是什么，具有一定借鉴价值，感兴趣的朋友可以参考下，希望大家阅读完这篇文章之后大有收获，下面让丸趣 TV 小编带着大家一起了解一下。
在实际开发，Redis 使用会频繁，那么在使用过程中我们该如何正确抉择数据类型呢？哪些场景下适用哪些数据类型。而且在面试中也很常会被面试官问到 Redis 数据结构方面的问题：
Redis 为什么快呢？
为什么查询操作会变慢了？
Redis Hash rehash 过程
为什么使用哈希表作为 Redis 的索引
当我们分析理解了 Redis 数据结构，可以为了我们在使用 Redis 的时候，正确抉择数据类型使用，提升系统性能。【相关推荐：Redis 视频教程】
Redis 底层数据结构
Redis 是一个内存键值 key-value 数据库，且键值对数据保存在内存中，因此 Redis 基于内存的数据操作，其效率高，速度快；
其中，Key 是 String 类型，Redis 支持的 value 类型包括了 String、List、Hash、Set、Sorted Set、BitMap 等。Redis 能够之所以能够广泛地适用众多的业务场景，基于其多样化类型的 value。
而 Redis 的 Value 的数据类型是基于为 Redis 自定义的对象系统 redisObject 实现的，
typedef struct redisObject{
// 类型
unsigned type:4;
// 编码
unsigned encoding:4;
// 指向底层实现数据结构的指针
void *ptr;
…..
}redisObject 除了记录实际数据，还需要额外的内存空间记录数据长度、空间使用等元数据信息，其中包含了 8 字节的元数据和一个 8 字节指针，指针指向具体数据类型的实际数据所在位置：
其中，指针指向的就是基于 Redis 的底层数据结构存储数据的位置，Redis 的底层数据结构：SDS，双向链表、跳表，哈希表，压缩列表、整数集合实现的。
那么 Redis 底层数据结构是怎么实现的呢？
Redis 底层数据结构实现
我们先来看看 Redis 比较简单的 SDS, 双向链表，整数集合。
SDS、双向链表和整数集合
SDS，使用 len 字段记录已使用的字节数，将获取字符串长度复杂度降低为 O(1)，而且 SDS 是惰性释放空间的，你 free 了空间，系统把数据记录下来下次想用时候可直接使用。不用新申请空间。
整数集合，在内存中分配一块地址连续的空间，数据元素会挨着存放，不需要额外指针带来空间开销，其特点为内存紧凑节省内存空间，查询复杂度为 O(1)效率高，其他操作复杂度为 O(N)；
双向链表，在内存上可以为非连续、非顺序空间，通过额外的指针开销前驱 / 后驱指针串联元素之间的顺序。
其特点为节插入 / 更新数据复杂度为 O(1)效率高，查询复杂度为 O(N)；
Hash 哈希表
哈希表，其实类似是一个数组，数组的每个元素称为一个哈希桶，每个哈希桶中保存了键值对数据，且哈希桶中的元素使用 dictEntry 结构，
因此，哈希桶元素保存的并不是键值对值本身，而是指向具体值的指针，所以在保存每个键值对的时候会额外空间开销，至少有增加 24 个字节，特别是 Value 为 String 的键值对，每一个键值对就需要额外开销 24 个字节空间。当保存数据小，额外开销比数据还大时，这时为了节省空间，考虑换数据结构。
那来看看全局哈希表全图：
虽然哈希表操作很快，但 Redis 数据变大后，就会出现一个潜在的风险：哈希表的冲突问题和 rehash 开销问题，这可以解释为什么哈希表操作变慢了？
当往哈希表中写入更多数据时，哈希冲突是不可避免的问题，Redis 解决哈希冲突的方式，就是链式哈希，同一个哈希桶中的多个元素用一个链表来保存，它们之间依次用指针连接，如图所示：
当哈希冲突也会越来越多，这就会导致某些哈希冲突链过长，进而导致这个链上的元素查找耗时长，效率降低。
为了解决哈希冲突带了的链过长的问题，进行 rehash 操作，增加现有的哈希桶数量，分散单桶元素数量。那么 rehash 过程怎么样执行的呢？
Rehash
为了使 rehash 操作更高效，使用两个全局哈希表：哈希表 1 和哈希表 2，具体如下：
将哈希表 2 分配更大的空间，
把哈希表 1 中的数据重新映射并拷贝到哈希表 2 中；
释放哈希表 1 的空间
但由于表 1 和表 2 在重新映射复制时数据大，如果一次性把哈希表 1 中的数据都迁移完，会造成 Redis 线程阻塞，无法服务其他请求。
为了避免这个问题，保证 Redis 能正常处理客户端请求，Redis 采用了渐进式 rehash。
每处理一个请求时，从哈希表 1 中依次将索引位置上的所有 entries 拷贝到哈希表 2 中，把一次性大量拷贝的开销，分摊到了多次处理请求的过程中，避免了耗时操作，保证了数据的快速访问。
在理解完 Hash 哈希表相关知识点后，看看不常见的压缩列表和跳表。
压缩列表与跳表
压缩列表，在数组基础上，在压缩列表在表头有三个字段 zlbytes、zltail 和 zllen，分别表示列表长度、列表尾的偏移量和列表中的 entry 个数；压缩列表在表尾还有一个 zlend，表示列表结束。
优点：内存紧凑节省内存空间，内存中分配一块地址连续的空间，数据元素会挨着存放，不需要额外指针带来空间开销；查找定位第一个元素和最后一个元素，可以通过表头三个字段的长度直接定位，复杂度是 O(1)。
跳表，在链表的基础上，增加了多级索引，通过索引位置的几个跳转，实现数据的快速定位，如下图所示：
比如查询 33
特点：当数据量很大时，跳表的查找复杂度为 O(logN)。
综上所述，可以得知底层数据结构的时间复杂度：
数据结构类型时间复杂度哈希表 O(1)整数数组 O(N)双向链表 O(N)压缩列表 O(N)跳表 O(logN)
Redis 自定义的对象系统类型即为 Redis 的 Value 的数据类型，Redis 的数据类型是基于底层数据结构实现的，那数据类型有哪些呢？
Redis 数据类型
String、List、Hash、Sorted Set、Set 比较常见的类型，其与底层数据结构对应关系如下：
数据类型数据结构 StringSDS(简单动态字符串)List 双向链表
压缩列表 Hash 压缩列表 br/ 哈希表 Sorted Set 压缩列表 br/ 跳表 Set 哈希表 br/ 整数数组
数据类型对应特点跟其实现的底层数据结构差不多，性质也是一样的, 且
String，基于 SDS 实现，适用于简单 key-value 存储、setnx key value 实现分布式锁、计数器(原子性)、分布式全局唯一 ID。
List，按照元素进入 List 的顺序进行排序的，遵循 FIFO(先进先出)规则，一般使用在 排序统计以及简单的消息队列。
Hash，是字符串 key 和字符串 value 之间的映射，十分适合用来表示一个对象信息，特点添加和删除操作复杂度都是 O(1)。
Set，是 String 类型元素的无序集合，集合成员是唯一的，这就意味着集合中不能出现重复的数据。基于哈希表实现的，所以添加，删除，查找的复杂度都是 O(1)。
Sorted Set， 是 Set 的类型的升级，不同的是每个元素都会关联一个 double 类型的分数，通过分数排序，可以范围查询。
那我们再来看看这些数据类型，Redis Geo、HyperLogLog、BitMap？
Redis Geo，将地球看作为近似为球体，基于 GeoHash 将二维的经纬度转换成字符串，来实现位置的划分跟指定距离的查询。特点一般使用在跟位置有关的应用。
HyperLogLog，是一种概率数据结构，它使用概率算法来统计集合的近似基数，错误率大概在 0.81%。当集合元素数量非常多时，它计算基数所需的空间总是固定的，而且还很小，适合使用做 UV 统计。
BitMap，用一个比特位来映射某个元素的状态，只有 0 和 1 两种状态，非常典型的二值状态，且其本身是用 String 类型作为底层数据结构实现的一种统计二值状态的数据类型 ，优势大量节省内存空间，可是使用在二值统计场景。
在理解上述知识后，我们接下来讨论一下根据哪些策略选择相对应的应用场景下的 Redis 数据类型？
选择合适的 Redis 数据类型策略
在实际开发应用中，Redis 可以适用于众多的业务场景，但我们需要怎么选择数据类型存储呢？
主要依据就是时间 / 空间复杂度，在实际的开发中可以考虑以下几个点：
数据量，数据本身大小
集合类型统计模式
支持单点查询 / 范围查询
特殊使用场景
数据量，数据本身大小
当数据量比较大，数据本身比较小，使用 String 就会使用额外的空间大大增加，因为使用哈希表保存键值对，使用 dictEntry 结构保存，会导致保存每个键值对时额外保存 dictEntry 的三个指针的开销，这样就会导致数据本身小于额外空间开销，最终会导致存储空间数据大小远大于原本数据存储大小。
可以使用基于整数数组和压缩列表实现了 List、Hash 和 Sorted Set，因为整数数组和压缩列表在内存中都是分配一块地址连续的空间，然后把集合中的元素一个接一个地放在这块空间内，非常紧凑，不用再通过额外的指针把元素串接起来，这就避免了额外指针带来的空间开销。而且采用集合类型时，一个 key 就对应一个集合的数据，能保存的数据多了很多，但也只用了一个 dictEntry，这样就节省了内存。
集合类型统计模式
Redis 集合类型统计模式常见的有：
聚合统计（交集、差集、并集统计）： 对多个集合进行聚合计算时，可以选择 Set；
排序统计（要求集合类型能对元素保序）：Redis 中 List 和 Sorted Set 是有序集合，List 是按照元素进入 List 的顺序进行排序的，Sorted Set 可以根据元素的权重来排序；
二值状态统计（集合元素的取值就只有 0 和 1 两种）：Bitmap 本身是用 String 类型作为底层数据结构实现的一种统计二值状态的数据类型，Bitmap 通过 BITOP 按位 与、或、异或的操作后使用 BITCOUNT 统计 1 的个数。
基数统计（统计一个集合中不重复的元素的个数）：HyperLogLog 是一种用于统计基数的数据集合类型，统计结果是有一定误差的，标准误算率是 0.81%。需要精确统计结果的话，用 Set 或 Hash 类型。
Set 类型，适用统计用户 / 好友 / 关注 / 粉丝 / 感兴趣的人集合聚合操作，比如
统计手机 APP 每天的新增用户数
两个用户的共同好友
Redis 中 List 和 Sorted Set 是有序集合，使用应对集合元素排序需求，比如
最新评论列表
排行榜
Bitmap 二值状态统计，适用数据量大，且可以使用二值状态表示的统计，比如：
签到打卡，当天用户签到数
用户周活跃
用户在线状态
HyperLogLog 是一种用于统计基数的数据集合类型，统计一个集合中不重复的元素个数，比如
统计网页的 UV，一个用户一天内的多次访问只能算作一次
支持单点查询 / 范围查询
Redis 中 List 和 Sorted Set 是有序集合支持范围查询，但是 Hash 是不支持范围查询的
特殊使用场景
消息队列，使用 Redis 作为消息队列的实现，要消息的基本要求消息保序、处理重复的消息和保证消息可靠性，方案有如下：
基于 List 的消息队列解决方案
基于 Streams 的消息队列解决方案
基于 List 基于 Strems 消息保序使用 LPUSH/RPOP 使用 XADD/XREAD 阻塞读取使用 BRPOP 使用 XREAD block 重复消息处理生产者自行实现全局唯一 IDStreams 自动生成全局唯一 ID 消息可靠性使用 BRPOPLPUSH 使用 PENDING List 自动留存消息适用场景消息总量小消息总量大，需要消费组形式读取数据
基于位置 LBS 服务，使用 Redis 的特定 GEO 数据类型实现，GEO 可以记录经纬度形式的地理位置信息，被广泛地应用在 LBS 服务中。 比如: 打车软件是怎么基于位置提供服务的。
Redis 之所以那么快，是因为其基于内存的数据操作和使用 Hash 哈希表作为索引，其效率高，速度快，而且得益于其底层数据多样化使得其可以适用于众多场景，不同场景中选择合适的数据类型可以提升其查询性能。
感谢你能够认真阅读完这篇文章，希望丸趣 TV 小编分享的“Redis 中数据结构是什么”这篇文章对大家有帮助，同时也希望大家多多支持丸趣 TV，关注丸趣 TV 行业资讯频道，更多相关知识等着你来学习!
向 AI 问一下细节
