Redis数据结构总结

Redis 是一款开源的，内存中的数据结构存储系统，它可以用作数据库、缓存和消息代理。Redis 支持多种类型的数据结构，如字符串（String）、哈希（Hashes）、列表（Lists）、集合（Sets）、有序集合（Sorted Sets）、位图（Bitmaps）、HyperLogLogs 和地理空间索引（Geospatial）。这些数据结构提供了丰富的操作，使得 Redis 能够应对各种各样的场景。 在这篇博客中，我们将详细介绍 Redis 的各种数据结构，包括它们的特性、底层实现、常用命令以及应用场景。无论你是 Redis 的新手，还是想深入了解 Redis，这篇博客都将为你提供有价值的信息。让我们开始这次的学习之旅吧！

1、Redis数据结构概述

1.1、Redis本质就是哈希表

Redis 本身是一个键值对数据库，这种键值对的存储方式就是哈希映射（Hashmap）的一种体现，即通过键（Key）来快速查找对应的值（Value）。

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

如下图中可以看到，哈希桶中的 entry 元素中保存了 ‘*key’ 和 '*value ’ 指针，分别指向了实际的键和值，这样一来，即使值是一个集合，也可以通过 '*value 指针被查找到：

因为这个哈希表保存了所有的键值对，所以，它也叫做全局哈希表。

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

也就是说，整个数据库就是一个全局 Hash 表，而 Hash 表的时间复杂度就是 O(1)，只需要计算每个键的 Hash 值，就知道对应的 Hash 桶的位置，定位桶里面的 Entry 找到对应数据，这个也是 Redis 快的原因之一。

但是，如果我们只是了解哈希表 O(1) 复杂度和快速查找特性，那么，当我们向 Redis 中写入大量数据之后，就可能发现操作有时候会突然变慢了。原因是哈希表的冲突问题和 rehash 可能带来的操作阻塞。

1.2、Redis的哈希冲突与渐进式rehash

Redis 使用哈希表作为其底层数据结构，哈希冲突是哈希表中常见的问题。当两个或更多的键被哈希函数映射到同一个哈希桶时，就会发生哈希冲突。Redis 通过链地址法来解决哈希冲突，即在每个哈希桶中维护一个链表，所有哈希到同一个桶的键值对都存储在这个链表中。

当哈希表中的元素数量增长到一定程度，或者哈希表中的元素数量减少到一定程度，Redis 会触发哈希表的扩容或收缩，这个过程称为 rehash。为了避免 rehash 过程中一次性复制所有元素导致的长时间阻塞，Redis 使用了一种称为“渐进式 rehash”的策略。

在渐进式 rehash 过程中，Redis 会同时维护新旧两个哈希表，并在每次对哈希表进行操作时，将一部分桶从旧哈希表移动到新哈希表。同时，为了保证查询操作的正确性，Redis 在查询时会同时查找新旧两个哈希表。这样，通过分摊在一段时间内完成 rehash，避免了一次性操作带来的性能问题

1.3、Redis数据结

Redis 中的数据结构有 2 种意思：

1. Redis 键值对中的值的数据类型，也就是数据的保存形式，其包含 6 种基本类型（String（字符串）、List（列表）、Hash（哈希）、Set（集合）、Sorted Set（有序集合）、Stream（流、Redis5.0引入）），和三种特殊类型（geospatial（地理位置）、Bitmap（位存储）、HyperLogLogs（基数统计））
2. 数据结构的底层实现：底层数据结构一共有 6 种，分别是简单动态字符串、双向链表、压缩列表、哈希表、跳表和整数数组

从上图可以看出：String 的底层是简单动态字符串；List 的底层是双向链表和压缩链表；Hash 的底层是压缩链表和哈希表；Set 的底层是整数数组和哈希表；Sorted Set 底层压缩链表和跳表。也就是说 String 类型的底层实现只有一种数据结构，也就是简单动态字符串。而 List、Hash、Set 和 Sorted Set这 四种数据类型，都有两种底层实现结构。通常情况下，我们会把这四种类型称为集合类型，它们的特点是一个键对应了一个集合的数据。

Redis 之所以采用不同的数据结构，其实是在性能和内存使用效率之间的平衡。

2、Redis基本数据类型

2.1、String数据结构简介

详细链接：Redis数据结构：String类型全面解析

String 是 Redis 最简单的数据类型，也是最常用的数据类型。它可以包含任何数据，包括字符串、整数或者浮点数。在 Redis 中，字符串的最大长度可以达到 512MB。

应用场景：

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

底层结构：

Redis 的 String 类型是二进制安全的，它的底层实际上是一个字节数组，因此 String 类型可以包含任何数据，例如 jpg 图片或者序列化的对象。

常用命令：

1. SET key value：设置键的值。
2. GET key：获取键的值。
3. DEL key：删除键。
4. INCR key：将键的值增加 1。
5. DECR key：将键的值减少 1。
6. APPEND key value：将给定 value 值追加到原值的末尾。
7. STRLEN key：返回键值的长度。

2.2、List数据结构简介

详细链接：Redis数据结构：List类型全面解析

List 是 Redis 的一种数据类型，它是简单的字符串列表，按插入顺序排序。你可以添加一个元素到头部（左边）或尾部（右边）。在 Redis 中，列表最多可以包含 2^32 - 1 个元素。

应用场景：

1. 消息队列：可以利用 List 的 push 和 pop 操作，实现生产者消费者模型。
2. 时间线、动态消息：比如微博的时间线，可以将最新的内容放在 List 的最前面。

底层结构：

Redis List 的底层实现为双向链表和压缩列表两种，当列表中的元素个数较少且每个元素的大小较小的时候，Redis 会选择压缩列表作为底层实现，这样可以更加节省内存。当数据量变大时，Redis 会自动将底层实现从压缩列表切换为双向链表。

常用命令：

1. LPUSH key value：将一个或多个值插入到列表头部。
2. RPUSH key value：将一个或多个值插入到列表尾部。
3. LPOP key：移除并返回列表的第一个元素。
4. RPOP key：移除并返回列表的最后一个元素。
5. LRANGE key start stop：返回列表中指定区间内的元素。
6. LINDEX key index：返回列表中指定位置的元素。
7. LLEN key：返回列表的长度。

2.3、Hash数据结构简介

详细链接：Redis数据结构：Hash类型全面解析

Hash 是 Redis 的一种数据类型，它是键值对集合。是一个字符串字段和字符串值之间的映射表，其字段和值的最大长度都是 512MB。在 Redis 中，哈希可以存储超过 4 亿个键值对。

应用场景：

1. 存储对象：Hash 结构可以看作是 String 类型的 field 和 value 的映射表，特别适合用于存储对象。
2. 数据缓存：可以将数据库中的一条记录映射成一个 Hash 结构，Hash 的每个字段对应记录的每个列。

底层结构：

Redis Hash 的底层实现为压缩列表和哈希表两种，当 Hash 中的元素个数较少且每个元素的大小较小的时候，Redis 会选择压缩列表作为底层实现，这样可以更加节省内存。当数据量变大时，Redis 会自动将底层实现从压缩列表切换为哈希表。

常用命令：

1. HSET key field value：将哈希表 key 中的字段 field 的值设为 value。
2. HGET key field：获取存储在哈希表中指定字段的值。
3. HDEL key field：删除哈希表 key 中的一个或多个指定字段。
4. HGETALL key：获取在哈希表中指定 key 的所有字段和值。
5. HLEN key：获取哈希表中字段的数量。
6. HEXISTS key field：查看哈希表 key 中，指定的字段是否存在。

2.4、Set数据结构简介

详细链接：Redis数据结构：Set类型全面解析

Set 是 Redis 的一种数据类型，它是字符串类型的无序集合。和列表一样，你可以添加、删除、查找元素。但是，它保证每个元素只出现一次。在 Redis 中，集合最多可以包含 2^32 - 1 个元素。

应用场景：

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

底层结构：

Redis Set 的底层实现为整数集合和哈希表两种，当集合中的元素都是整数且元素数量较少时，Redis 会选择整数集合作为底层实现，这样可以更加节省内存。当数据量变大或者集合中的元素不全是整数时，Redis 会自动将底层实现从整数集合切换为哈希表。

常用命令：

1. SADD key member：将一个或多个成员元素加入到集合中。
2. SMEMBERS key：返回集合中的所有成员。
3. SISMEMBER key member：判断 member 元素是否是集合 key 的成员。
4. SREM key member：移除集合中一个或多个成员元素。
5. SCARD key：返回集合中的元素的数量。

注意事项：

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

2.5、ZSet数据结构简介

详细链接：Redis数据结构：Zset类型全面解析

ZSet（有序集合）是 Redis 的一种数据类型，它在 Set 的基础上增加了一个权重参数 score，使得集合中的元素能够按 score 进行有序排列。在 Redis 中，有序集合的最大成员数是 2^32 - 1。

应用场景：

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

底层结构：

Redis ZSet 的底层实现为跳跃列表和哈希表两种，跳跃列表保证了元素的排序和快速的插入性能，哈希表则提供了快速查找的能力。

常用命令：

1. ZADD key score member：向有序集合添加一个或多个成员，或者更新已存在成员的分数。
2. ZRANGE key start stop WITHSCORES：返回有序集中，指定区间内的成员。
3. ZREM key member：移除有序集合中的一个或多个成员。
4. ZCARD key：获取有序集合的成员数。
5. ZSCORE key member：返回有序集中，成员的分数值。

注意事项：

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

2.6、Stream数据结构简介

详细链接：Redis数据结构：Stream类型全面解析

Stream 是 Redis 5.0 版本引入的新特性，它是一种类似于日志系统的数据结构，用于存储多个键值对的列表，每个键值对都会被分配一个自动递增的ID。Stream 主要用于实现消息队列的功能，如 Apache Kafka。

应用场景：

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

底层结构：

Redis Stream 的底层实现为一种叫做快速列表（quicklist）的数据结构，这是一种同时包含了压缩列表（ziplist）和双向链表特性的数据结构，既可以利用压缩列表节省内存，又可以利用双向链表在两端进行快速的添加、删除操作。

常用命令：

1. XADD key ID field value field value …：向 Stream 中添加元素。
2. XRANGE key start end COUNT count：获取 Stream 中指定范围的元素。
3. XREAD COUNT count STREAMS key key … ID ID …：从 Stream 中读取数据。
4. XDEL key ID ID …：从 Stream 中删除指定 ID 的元素。
5. XLEN key：获取 Stream 中的元素数量。

注意事项：

1. Stream 是 Redis 中唯一一个可以安全地进行多个写入操作的数据结构，因为每个元素都有一个唯一的、自动递增的 ID。
2. Stream 中的元素一旦被添加，就不能被修改，只能被删除。

3、Redis特殊数据类型

3.1、Bitmap位存储

Redis 的 Bitmap 是一种特殊的字符串数据结构，它可以用来存储位（bit）数据。每个位可以存储 0 或 1 两种值，因此 Bitmap 可以非常高效地存储大量的布尔值。

Redis 的 Bitmap 数据结构可以用于多种场景，特别是需要高效存储和操作大量布尔值的场景。以下是一些常见的使用场景：

1. 用户活跃度统计：可以用 Bitmap 来记录用户的登录情况，每个位对应一个用户，位的值表示用户是否登录。通过统计位值为 1 的数量，就可以得到活跃用户的数量。
2. 功能开关：如果一个系统有很多可开启或关闭的功能，可以用 Bitmap 来存储每个功能的开关状态。
3. 用户权限管理：可以用 Bitmap 来存储用户的权限信息，每个位对应一个权限，位的值表示用户是否拥有该权限。
4. 统计和分析：Bitmap 可以用于各种统计和分析任务，例如统计特定条件的用户数量，或者分析用户的行为模式等。

需要注意的是，虽然 Bitmap 可以非常高效地存储大量的布尔值，但是它的索引是基于位的，因此如果需要存储的数据有自己的特定索引（如用户 ID），那么可能需要额外的数据结构来维护这种映射关系。

Bitmap 的主要特点是空间效率极高，因为每个布尔值只占用一个位。此外，Redis 提供了一系列的命令，可以对 Bitmap 进行各种位操作，如设置、获取、统计位值为 1 的数量等。

以下是一些常用的 Bitmap 命令：

SETBIT：设置 Bitmap 中指定位置的位值。

SETBIT mykey 7 1

GETBIT：获取 Bitmap 中指定位置的位值。

GETBIT mykey 7

BITCOUNT：统计 Bitmap 中位值为 1 的数量。

BITCOUNT mykey

BITOP：对一个或多个 Bitmap 进行位操作，如 AND、OR、NOT、XOR 等。

BITOP AND destkey mykey1 mykey2

需要注意的是，虽然 Bitmap 可以非常高效地存储大量的布尔值，但是它的索引是基于位的，因此如果需要存储的数据有自己的特定索引（如用户 ID），那么可能需要额外的数据结构来维护这种映射关系。

3.2、HyperLogLogs基数统计

HyperLogLogs 是 Redis 提供的一种概率型的数据结构，用于估计集合的基数（不重复元素的数量）。HyperLogLogs 的优点是，无论集合中包含多少元素，它只需要使用固定大小的内存（大约 12KB）。

应用场景：

1. 统计在线用户数：如果需要统计一个网站的独立访客数量，使用传统的 Set 结构可能会消耗大量的内存，而使用 HyperLogLogs 只需要消耗固定大小的内存。
2. 统计大数据集合的基数：例如统计一亿个用户中，有多少不同的搜索关键词。

常用命令：

1. PFADD key element element …：将指定元素添加到 HyperLogLog 中。
2. PFCOUNT key key …：返回给定 HyperLogLog 的基数估算值。
3. PFMERGE destkey sourcekey sourcekey …：将多个 HyperLogLog 合并为一个 HyperLogLog。

注意事项：

1. HyperLogLogs 提供的是基数的估计值，而不是精确值，但误差率通常不超过 0.81%。
2. 一旦一个元素被添加到 HyperLogLog，就不能再被移除。
3. HyperLogLog 对元素的顺序没有要求，也就是说，无论元素以何种顺序被添加，最后的基数估算值都是一样的。

3.3、Geospatial地理位置

Geospatial（地理空间索引）是 Redis 提供的一种特殊类型的 Sorted Set，用于存储地理位置信息（如经纬度），并能够快速计算出两个地点之间的距离。

应用场景：

1. 地理位置相关的功能：例如查找附近的人、查找附近的商家等。
2. 计算两个地点之间的距离。

常用命令：

1. GEOADD key longitude latitude member longitude latitude member …：添加一个或多个地理空间位置到指定的 key 中。
2. GEODIST key member1 member2 unit：计算两个给定位置之间的距离。
3. GEOHASH key member member …：返回一个或多个位置元素的 Geohash 表示。
4. GEOPOS key member member …：返回一个或多个位置元素的经纬度。
5. GEORADIUS key longitude latitude radius m|km|ft|mi WITHCOORD WITHHASH：查询指定半径内的地理信息位置。

注意事项：

1. Geospatial 使用的是地球模型，所以计算出的距离是大圆距离。
2. Geospatial 的底层实现是 Sorted Set，所以它的一些操作（如添加、删除、查找）的时间复杂度和 Sorted Set 是一样的。