Redis数据库（二）：Redis 常用的五种数据结构

Redis 能够做到高性能的原因主要有两个，一是它本身是内存型数据库，二是采用了多种适用于不同场景的底层数据结构。
Redis 常用的数据结构支持字符串、列表、哈希表、集合和有序集合。实现这些数据结构的底层数据结构有 6 种，分别是简单动态字符串、双向列表、压缩列表、哈希表、跳表和整数数组。
在这里插入图片描述

List、 Hash、Set 和 Sorted Set 这四种数据类型，都有两种底层实现结构。通常情况下，我们会把这四种类型称为集合类型，它们的特点是一个键对应了一个集合的数据。
那么，有一些问题值得我们去思考：

既然 Redis 是键值型数据结构，那么键和值本身之间用什么结构组织？
操作集合数据的效率和哪些因素有关？

2.1 键和值用什么数据结构组织？

为了实现从键到值的快速访问，Redis 使用了一个哈希表来保存所有键值对。一个哈希表，其实就是一个数组，数组的每个元素称为一个哈希桶。
因为值本身的类型可以是列表、哈希表等集合类型，因此哈希桶存放的并不是值本身，而是 *key 和 *value 的入口地址。
在这里插入图片描述

使用哈希表的好处就是能够在 O(1) 时间内根据 key 查找到相应的 value。但，哈希表的性能并非一直是 O(1)。当需要解决哈希表冲突和再哈希（rehash）时可能会带来性能的下降。

2.1.1 哈希表冲突

哈希表冲突是指根据不同的 key 计算得到了相同的哈希值，就是说有不同的键值对放到了同一个哈希桶当中。因为哈希桶的个数是有限的，因此总会遇到哈希冲突。
解决哈希冲突的方法有多种，Redis 采用的是链式哈希。具体来说，就是同一个哈希桶中的多个元素用一个链表来保存，它们之间通过指针来连接。
在这里插入图片描述

链式哈希会带一个问题是，当位于同一个桶中的元素太多时，查询桶中元素的时间复杂度会退化到 O(n)，这是我们不愿看到的。解决办法就是对旧的哈希表进行 rehash，将新的哈希值存放在一个更大的哈希桶中。但如果直接进行原地哈希，必然会导致性能急剧下降，解决的办法就是将 rehash 的操作均摊到之后的操作中。

2.1.2 渐进式 rehash

渐进式 rehash 的思想是在拷贝数据时，Redis 仍然正常处理客户端请求，每处理一个请求时，从哈希表 1 中的第一个索引位置开始，顺带着将这个索引位置上的所有 entries 拷贝到哈希表 2 中；等处理下一个请求时，再顺带拷贝哈希表 1 中的下一个索引位置的 entries。
在这里插入图片描述

这样就巧妙地把一次性大量拷贝的开销，分摊到了多次处理请求的过程中，避免了耗时操作，保证了数据的快速访问。

2.2 操作数据集合的效率

查找一个集合类型的值的过程是：先通过全局哈希表找到对应的哈希桶位置，然后在集合进行增删改查。那么，集合的操作效率与哪些因素有关呢？
首先是与集合底层采用的数据结构有关，例如哈希表的查询时间复杂度要优于链表的。其次是与这些操作本身的执行特点有关，例如读取一个元素和读取一个范围的元素。

2.2.1 底层数据结构的特点

Redis 实现集合类型的底层数据结构有双向列表、整数数组、哈希表、压缩列表和跳表。
哈希表的特点刚才已经介绍过了。双向列表和整数数组比较常见，这里就不再详细展开了。
重点介绍一个压缩列表和跳表。

压缩列表

压缩列表类似于一个数组，数组中的每一个元素都对应保存一个数据。和数组不同的是，压缩列表在表头有三个字段 zlbytes、zltail 和 zllen，分别表示列表长度、列表尾的偏移量和列表中的 entry 个数；压缩列表在表尾还有一个 zlend，表示列表结束。
在这里插入图片描述

在压缩列表中，如果我们要查找定位第一个元素和最后一个元素，可以通过表头三个字段的长度直接定位，复杂度是 O(1)。而查找其他元素时，就没有这么高效了，只能逐个查找，此时的复杂度就是 O(N) 了。

跳表

跳表在链表的基础上，增加了多级索引，通过索引位置的几个跳转，实现数据的快速定位，跳表的查询过程如下图所示：
在这里插入图片描述

以上五种数据结构的时间复杂度如下表所示：
在这里插入图片描述

2.2.2 不同操作的复杂度

集合类型的操作方法很多，例如获取单个元素、多个元素、判断某个元素是否在集合当中。而不同数据结构的同一种操作方法的时间复杂度不同，因此有必要了解不同操作方法的时间复杂度。

单元素操作时间复杂度为 O(1)；
范围操作比较耗时。当返回一个范围内的元素时，例如返回集合、List 某个范围的元素，时间复杂度为 O(N)。
统计元素个数比较高效。压缩列表、双向列表、整数数组这些数据结构中专门记录了元素的个数，统计执行效率较高。
特殊位置的元素操作效率与数据结构密切相关。例如对于 List 而言，在头尾进行操作元素的时间复杂度为 O(1)，而在中间位置操作元素的时间复杂度为 O(N)。

2.3 使用数据结构的建议

选择 Redis 的数据结构时，需要综合考虑数据的特点、操作需求、内存占用和性能要求等多个因素。
选择 Redis 数据结构时，应该考虑以下几个因素：

数据访问模式
• 字符串（String）：适用于简单的 key-value 存储，比如缓存用户会话、计数器、或是简单的数据存取。
• 哈希（Hash）：适合存储对象、结构化数据，如用户信息、商品详情等。哈希允许在单一 key 下保存多个字段（字段值对），非常适合于存储较小的对象。
• 列表（List）：适合存储有序的集合，比如消息队列、任务队列、用户操作日志等。支持推入、弹出操作，符合生产者-消费者模型。
• 集合（Set）：适合存储无序且唯一的元素集合，用于去重操作、标签分类等。例如，存储用户订阅的标签列表，或是某些“推荐系统”的推荐项。
• 有序集合（Sorted Set）：适合存储带有权重的有序数据，支持根据分数进行排序。适用于排行榜、优先级队列、延迟队列等应用场景。
性能要求
• 存储效率：不同数据结构的存储方式和空间效率不同。比如，集合（Set）适合去重，哈希（Hash）适合存储对象，如果需要存储大量字段和小值数据，使用哈希结构可以节省内存。
• 操作效率：不同数据结构在操作时的复杂度也不同。一般来说，字符串操作最简单，复杂度为 O(1)，而有序集合（Sorted Set）的某些操作，如添加、删除元素的复杂度可能为 O(log N)。
数据大小与访问频率
• 如果需要频繁对数据进行增、删、改、查等操作，选择操作复杂度较低的数据结构，例如字符串和哈希。
• 对于大数据量和高并发的场景，考虑 Redis 的内存消耗和性能瓶颈。比如，HyperLogLog 在大数据量去重时非常高效。
使用场景
• 缓存：大多数缓存场景使用字符串（String）或哈希（Hash）。例如，缓存一整个页面或用户信息。
• 队列：使用列表（List）或有序集合（Sorted Set）来实现消息队列、任务调度等。
• 去重与标签：集合（Set）适用于去重和标签管理。
• 排行榜与优先级队列：使用有序集合（Sorted Set）存储带权重的数据，并根据分数进行排序。
数据过期与持久化
• Redis 提供了 EXPIRE 命令来为 key 设置过期时间，但不同数据结构的持久化策略可能不同。根据业务需求决定是否需要启用 Redis 的持久化机制（RDB 或 AOF），以及数据结构的持久化需求。