Redis数据库面试——数据结构类型知识

大家好，这里是Good Note，关注 公主号：Goodnote，专栏文章私信限时Free。本文详细介绍Redis 提供的5种基本数据结构类型和4种特殊类型，除此之外，还有8种底层数据结构，每种结构类型有其特点和适用场景。

基本数据类型

1. String（字符串）

• 简介：Redis 最基本的数据类型，一个 key 对应一个 value，支持二进制安全，可存储任意数据（如图片、序列化对象）。
• 特点：
  • 最大可存储 512MB 数据。
  • 用于缓存、计数器、分布式 ID 生成等场景。
• 常用命令：
  • 存储：SET key value、MSET key value [key value ...]
  • 获取：GET key、MGET key [key ...]
  • 计数器操作：INCR key、DECR key、INCRBY key increment
• 底层实现：
  • 使用 SDS（Simple Dynamic String） 存储，支持动态扩容，避免频繁内存分配，减少内存碎片。

二进制安全的核心是：将数据视为纯字节流，不做额外解释或处理。在 Redis 和其他支持二进制安全的工具中，这种特性使得它们能够高效存储和处理多样化的数据类型，确保数据的完整性和兼容性。

使用场景

缓存

可以缓存各种信息（字符串、图片、视频等），存储在 Redis 中作为缓存，减轻持久层的读写压力；或者将 session 存储在 Redis 中用于共享。

1. 存储键值对：

   • SET key value：存入键值对，覆盖旧值，无视类型。
   • MSET key value [key value ...]：批量存储字符串键值对。

2. 获取键值对：

   • GET key：根据键获取对应的值。
   • MGET key [key ...]：批量获取字符串键值对。

3. 删除与设置过期时间：

   • DEL key：删除对应键的键值对。
   • EXPIRE key seconds：设置指定键的有效时间。

计数器

Redis 是单线程模型，命令只能逐个执行，不会出现并发问题导致计数错误。例如，可用于统计文章阅读量。

• INCR key：使键对应的数字加 1。
• DECR key：使键对应的数字减 1。
• INCRBY key increment：使键的值加上指定增量。
• DECRBY key decrement：使键的值减去指定增量。

ID 生成器

在分布式系统中可以保证生成的序列号唯一。

• INCRBY orderId increment：将键对应的数字加上指定的增量值。

分布式锁

方法	是否推荐	问题说明
SETNX + EXPIRE	不推荐	非原子操作，可能导致死锁。
SET NX EX	推荐	原子操作，避免死锁，更安全可靠。

SET NX EX 是现代 Redis 分布式锁的推荐实现方式。

1. 使用 SETNX 命令 + EXPIRE 命令

• 过程：

  1. 使用 SETNX 命令尝试设置锁：
     1. SETNX lock:resource "unique_value"

     复制代码
  2. 如果 SETNX 成功，则设置锁的过期时间：
     1. EXPIRE lock:resource 10

     复制代码

• 问题：

  • 非原子操作：
    • SETNX 和 EXPIRE 是两个独立的命令，执行时无法保证原子性。
    • 如果 SETNX 成功后，客户端崩溃或网络异常，未能执行 EXPIRE，可能导致锁永远存在（死锁）。

• 状态：

  • 由于上述缺陷，这种方式 不推荐使用。
  • 已被原子性更强的 SET NX EX 命令 取代。

---

2. 使用 SET NX EX 命令

• 过程：

  • 使用 SET 命令，同时指定：
    • NX：仅当键不存在时设置。
    • EX：设置键的过期时间（秒）。
  1. SET lock:resource "unique_value" NX EX 10

  复制代码

• 优点：

  • 原子操作：
    • SET NX EX 是单个命令，保证了加锁和设置过期时间的原子性。
  • 避免了非原子操作导致的死锁问题。

• 状态：

  • 推荐使用，已成为 Redis 实现分布式锁的标准方式。

---

2. Hash（哈希）

• 简介：键值对集合，类似于 HashMap，每个 key 是 field，value 是对应的值。
• 特点：
  • 适合存储对象，如用户信息、购物车等。
  • 支持单个字段更新，节省空间。
• 常用命令：
  • 存储：HSET key field value、HMSET key field value [field value ...]
  • 获取：HGET key field、HGETALL key
  • 增量操作：HINCRBY key field increment
• 底层实现：
  • 小数据量时使用 ziplist（压缩列表），节省内存。
  • 大数据量时使用 hashtable（哈希表），支持快速的插入和查询操作。

1. ziplist（压缩列表）：

   • 为了节省内存开销，小规模的 Hash 数据使用紧凑的压缩列表存储。
   • 优点：内存使用极少，适合字段数量少、数据简单的场景。
   • 缺点：随着字段数量或数据大小增长，查找效率降低。

2. hashtable（哈希表）：

   • 当数据量增大或字段较多时，自动切换为哈希表实现。
   • 优点：查找效率高，时间复杂度为 O(1)。
   • 缺点：内存开销相对较大。

通过这两种实现方式，Redis 平衡了内存使用和性能，适应不同数据规模的需求。

切换条件 Redis 在以下情况下，自动将 Hash 的底层存储从 ziplist 切换为 hashtable：

1. 字段数量超出阈值：
   • 默认 hash-max-ziplist-entries=512，即当字段数量超过 512 时，切换为哈希表。
2. 单个字段或值的大小超出阈值：
   • 默认 hash-max-ziplist-value=64，即当字段或值的大小超过 64 字节时，切换为哈希表。

以上两个参数可以通过 Redis 配置文件进行调整，以适应具体业务场景。

---

3. List（链表/列表）

• 简介：双向链表实现的列表，支持插入、删除操作，有序，可通过下标访问。
• 特点：
  • 支持先进先出（FIFO）队列、消息队列等场景。时间轴（timeline）或者消息流：例如微博的时间轴，有人发布微博，用lpush加入时间轴，展示新的列表信息。
  • 插入和删除性能优异，API 丰富。
• 常用命令：
  • 插入：LPUSH key value、RPUSH key value
  • 获取：LRANGE key start stop
  • 阻塞操作：BLPOP key [key ...] timeout、BRPOP key [key ...] timeout
• 底层实现：
  • 使用 quicklist（以 ziplist 为节点的双链表），结合链表的灵活性和 ziplist 的内存高效。

总结

模式	使用命令	描述
Stack (栈)	LPUSH + LPOP	后进先出（LIFO）。
Queue (队列)	LPUSH + RPOP	先进先出（FIFO）。
Capped Collection	LPUSH + LTRIM	保持固定长度的列表。
Message Queue	LPUSH + BRPOP	生产者-消费者消息队列。

1. LPUSH + LPOP = Stack (栈)

• 栈模型：后进先出（LIFO）。
• 命令解释：
  • LPUSH key value：将值插入到列表的左侧（头部）。
  • LPOP key：从列表的左侧（头部）弹出并返回值。
• 使用场景：实现撤销功能、递归算法中的辅助栈。

2. LPUSH + RPOP = Queue（队列）

• 队列模型：先进先出（FIFO）。
• 命令解释：
  • LPUSH key value：将值插入到列表的左侧（头部）。
  • RPOP key：从列表的右侧（尾部）弹出并返回值。
• 使用场景：实现任务队列或请求排队。

3. LPUSH + LTRIM = Capped Collection（有限集合）

• 有限集合：限制列表的长度，仅保留最近的 N 个元素。
• 命令解释：
  • LPUSH key value：将值插入到列表的左侧（头部）。
  • LTRIM key start stop：裁剪列表，仅保留索引范围内的元素（从 start 到 stop）。
• 使用场景：实现固定长度的访问记录、日志系统等。

4. LPUSH + BRPOP = Message Queue（消息队列）

• 消息队列模型：支持阻塞等待，适合生产者-消费者模式。
• 命令解释：
  • LPUSH key value：将消息插入到队列的左侧（头部）。
  • BRPOP key timeout：从队列的右侧（尾部）弹出消息，若队列为空则阻塞直到超时。
    • 如果 timeout=0，则表示永不超时，一直阻塞直到有新消息。
• 使用场景：任务调度系统，消费者从队列中获取任务。

4. Set（集合）

• 简介：保存多个字符串的集合，元素唯一且无序。
• 特点：
  • 支持集合运算（交集、并集、差集）。
  • 常用于标签系统、点赞、好友推荐等。
• 常用命令：
  • 添加：SADD key member、SUNION key [key ...]
  • 查询：SMEMBERS key、SISMEMBER key member
  • 集合运算：SINTER key [key ...]（交集）、SUNION key [key ...]（并集）
• 底层实现：
  • 使用 hashtable 存储，大数据量时支持高效的查找、插入和删除。
  • 小规模集合使用 intset 存储（仅包含整数）。

Redis 根据集合中元素的数量和类型，自动在 intset 和 hashtable 之间切换：

1. 如果集合中的所有元素都是整数，且数量较少，则使用 intset。
2. 如果集合中的元素类型不为整数，或数量超过配置的阈值（默认 512 个），则切换为 hashtable。

---

5. Sorted Set（有序集合）

• 简介：与 Set 类似，但每个元素有一个关联的分数（score），按分数排序。
• 特点：
  • 适用于排行榜、延迟队列等场景。
  • 分数可以重复，但元素值必须唯一。
• 常用命令：
  • 添加：ZADD key score member
  • 获取：ZRANGE key start stop [WITHSCORES]（正序）、ZREVRANGE key start stop [WITHSCORES]（倒序）
  • 增量操作：ZINCRBY key increment member
• 底层实现：
  • 当 ZSet 较小时，Redis 使用 Ziplist 实现，节省内存。
  • 当 ZSet 较大时，Redis 切换到使用 跳跃链表（Skiplist） 和 哈希表（Hash Table） 组合实现：
    • zskiplist 提供高效的范围查找和排序。
    • hashtable 用于快速查找元素。

底层实现：

当满足以下两个条件时，Redis 会使用 ziplist来实现 ZSET：

• 元素数量小于 128：如果集合中存储的元素较少，使用 ziplist 更加高效。它通过压缩数据来节省内存。

• 每个元素的长度小于 64 字节：如果每个元素的长度较短（例如，成员字符串很短），那么 ziplist 的压缩效率就很高。

• ziplist 的结构：在 ziplist 中，ZSET 的成员和分数（score）是交替存储的，数据压缩非常紧凑。

当 ZSET 的元素数量超过一定的阈值（例如超过 128 个元素），或者单个元素的长度较长时，Redis 会自动使用 skiplist（跳跃链表）和哈希表（Hash Table）的组合 来实现 ZSET。这是 Redis ZSET 中的默认数据结构。

1. zskiplist（跳跃表）：

   • 作用：实现有序集合中的元素排序和范围查找。
   • 特点：
     • 跳跃表是一种随机化的数据结构，类似于平衡树，但实现更简单。
     • 支持按照分数（score）排序的高效操作，如范围查询、按分数排序等。
     • 跳跃表中每个节点包含：
       • 成员元素（member）。
       • 分数值（score）。
       • 前后指针（用于维护链表关系）。
   • 时间复杂度：
     • 插入、删除、范围查找：O(log N)。

2. hashtable（哈希表）：

   • 作用：提供成员元素到分数值的快速映射。
   • 特点：
     • 哈希表存储了每个成员元素和对应的分数（member -> score）。
     • 用于快速查找某个成员是否存在，以及其分数值。
   • 时间复杂度：
     • 查找、插入、删除：O(1)。

---

zskiplist 和 hashtable 的组合

• 为什么需要组合两种结构：

  • 跳跃表（zskiplist）：
    • 支持按分数排序的快速操作。
    • 能高效实现范围查询和按分数排序的功能。
  • 哈希表（hashtable）：
    • 提供快速的元素查找和分数更新。
    • 弥补跳跃表在精确查找上的性能不足。

• 两者协同工作：

  1. 插入或删除一个元素时：
     • 在 hashtable 中存储或删除成员和分数的映射。
     • 同时在 zskiplist 中插入或删除节点，保持排序。
  2. 查询元素是否存在时：
     • 使用 hashtable 进行快速查找。
  3. 进行范围查询或排序时：
     • 使用 zskiplist 高效实现按分数排序或范围扫描。

---

优势分析

• 跳跃表的排序和范围操作：
  • 允许快速实现按分数排序和范围查找。
  • 时间复杂度为 O(log N)。
• 哈希表的快速查找：
  • 提供成员到分数的直接映射，查找效率为 O(1)。
• 内存效率：
  • 跳跃表的结构简单，节点的动态分配优化了内存使用。
  • 哈希表避免了重复排序，提高了效率。

---

特殊数据类型

6. Bitmaps（位图）

• 概述：以位的形式存储数据，每个键对应一个字符串，可以操作字符串的二进制位。
• 特点：
  • 位操作效率高，适合存储二进制状态。
  • 最大大小同字符串（512 MB）。
• 常见用途：
  • 用户签到（按日期设置某天状态）。
  • 在线状态记录。
• 常用命令：
  • SETBIT key offset value：设置指定偏移位的值。
  • GETBIT key offset：获取指定偏移位的值。
  • BITCOUNT key：统计所有位为 1 的数量。

---

7. HyperLogLog

• 概述：一种基于概率的数据结构，用于估算集合的基数（去重后的元素数量）。
• 特点：
  • 适合存储大规模数据，内存占用固定为 12 KB。
  • 结果是近似值，但误差在 0.81% 以内。
• 常见用途：
  • 网站 UV 统计（独立访客）。
  • 近似计数。
• 常用命令：
  • PFADD key element：添加元素。
  • PFCOUNT key：返回估算的基数值。

---

8. Geo（地理位置）

• 概述：用于存储地理位置信息（经纬度），并支持基于地理位置的操作。
• 特点：
  • 可以计算两点之间的距离。
  • 支持范围查询（如附近的人）。
• 常见用途：
  • 附近位置查询。
  • 地理信息存储。
• 常用命令：
  • GEOADD key longitude latitude member：添加地理位置。
  • GEODIST key member1 member2：计算两点间距离。
  • GEORADIUS key longitude latitude radius：按范围查询地理位置。

---

9. Streams（流）

• 概述：Redis 的消息队列实现，用于生产者-消费者模型。
• 特点：
  • 支持消费者组、消息确认。
  • 可以持久化消息。
• 常见用途：
  • 实时日志。
  • 消息分发。
• 常用命令：
  • XADD key * field value：添加消息。
  • XRANGE key start end：按范围读取消息。
  • XREADGROUP：消费者组读取消息。

---

底层数据类型

Redis 对用户暴露的基本类型 Value Type（如字符串、哈希、列表等）实际是通过底层多种高效数据结构实现的。这些数据结构在性能、内存占用、以及适用场景上各有特点，以下为详细介绍：
Redis 的 Value Type 基于以下底层数据结构实现：

1. SDS（Simple Dynamic String）：简单动态字符串，支持高效扩容。
2. LinkedList：双向链表。
3. HashTable：哈希表，支持平滑扩容。
4. zskiplist：跳跃表，支持排序和范围查询。
5. IntSet：整数集合，存储小规模整数。
6. ZipList：压缩列表，节省内存。
7. QuickList：结合链表和压缩列表，兼顾内存和效率。
8. ZipMap：轻量级字典，适合小规模场景。

以下是 Redis 的 8 种底层数据结构及其用途汇总：

底层数据结构	数据类型使用场景	特点/用途
SDS	String	存储字符串，支持动态扩容，二进制安全。
intset	Set	存储小规模整数集合，内存节省。
ziplist	Hash、List、Sorted Set	小数据量场景，连续内存存储，节省内存。
linkedlist	List（早期实现）	双向链表，已被 quicklist 替代。
quicklist	List	链表+ziplist 的结合，内存高效、操作灵活。
hashtable	Hash、Set	大数据量场景，提供 O(1) 的查找性能。
zskiplist	Sorted Set	跳跃表，支持范围查询和排序。
dict	Hash、Set、Sorted Set	通用哈希表，动态扩容，支持快速查找。

Redis 的灵活实现结合了不同数据结构的优点，针对不同场景优化性能与内存占用。

---

SDS（Simple Dynamic String）

• 简介：
  SDS 是 Redis 用于存储字符串的动态字符串结构，能够支持二进制数据和动态扩容。
• 特点：
  • 二进制安全：可以存储任意二进制数据（如图片、序列化对象）。
  • 动态扩容：自动扩展和缩小，避免频繁的内存分配。
  • 高效操作：记录已用长度和未用空间，减少字符串拼接时的性能损耗。
• 结构：
  1. struct sdshdr {
  2. int len; // 已使用长度
  3. int free; // 未使用长度
  4. char buf[]; // 字符数组
  5. };

  复制代码
• 应用场景：
  • 用于实现 Redis 的字符串类型。
  • 实现键值对中的键和某些简单值。

---

LinkedList（链表）

• 简介：
  Redis 的链表是一个通用的双向链表，节点通过指针连接。
• 特点：
  • 双向链表：每个节点包含前驱和后继指针。
  • 通用性强：节点的数据由 void* 指针指向，可以存储任意类型数据。
  • 灵活性高：适合频繁插入和删除操作的场景。
• 结构：
  1. typedef struct listNode {
  2. struct listNode *prev; // 前向指针
  3. struct listNode *next; // 后向指针
  4. void *value; // 节点值
  5. } listNode;

  复制代码
• 应用场景：
  • 实现早期 Redis 的列表类型（已被 quicklist 替代）。
  • 用于其他需要链表结构的功能。

---

HashTable

• 简介：
  Redis 的字典使用双哈希表实现，支持高效的查找、插入和删除操作。
• 特点：
  • 双哈希表：一个用于存储数据，另一个在扩容时用于渐进式数据迁移。
  • 平滑扩容：通过渐进式扩展减少扩容对性能的影响。
• 结构：
  1. typedef struct dictht {
  2. dictEntry **table; // 哈希表数组
  3. unsigned long size; // 哈希表大小
  4. unsigned long sizemask; // 掩码，用于计算索引
  5. unsigned long used; // 已用节点数量
  6. } dictht;

  复制代码
• 应用场景：
  • 实现 Redis 的哈希类型。
  • 用于内部数据存储，如保存键空间。

---

zskiplist（跳跃表）

• 简介：
  跳跃表是一种基于链表的有序数据结构，支持高效的范围查询和排序。
• 特点：
  • 多层索引：通过额外的索引层提高查找效率。
  • 简单高效：实现简单，性能接近平衡树。
• 结构：
  1. typedef struct zskiplistNode {
  2. double score; // 分数
  3. robj *obj; // 成员对象
  4. struct zskiplistNode *backward; // 后向指针
  5. struct zskiplistLevel {
  6. struct zskiplistNode *forward; // 前向指针
  7. unsigned int span; // 层跨度
  8. } level[];
  9. } zskiplistNode;

  复制代码
• 应用场景：
  • 实现 Redis 的有序集合（Sorted Set）类型。

---

intset（整数集合）

• 简介：
  Redis 的整数集合是一个有序的整数数组，用于存储小规模整数集合。
• 特点：
  • 有序存储：通过二分查找快速定位元素。
  • 节省内存：自动根据数据类型调整存储大小（如 int16、int32、int64）。
• 结构：
  1. typedef struct intset {
  2. uint32_t encoding; // 当前编码方式
  3. uint32_t length; // 元素数量
  4. int8_t contents[]; // 数据内容
  5. } intset;

  复制代码
• 应用场景：
  • 用于实现 Redis 的 Set 类型（当集合较小时）。

---

ziplist（压缩列表）

• 简介：
  压缩列表是一种内存紧凑型的双向链表，用于存储小规模数据。
• 特点：
  • 节省内存：数据紧凑存储，适合存储少量元素。
  • 操作简单：支持顺序遍历、插入和删除操作。
• 结构：
  1. struct ziplist {
  2. uint32_t zlbytes; // 列表总字节数
  3. uint32_t zltail; // 表尾偏移量
  4. uint16_t zllen; // 列表元素数量
  5. unsigned char entries[]; // 数据条目
  6. };

  复制代码
• 应用场景：
  • 实现 Redis 的列表和哈希类型（当数据量较小时）。

---

quicklist（快速列表）

• 简介：
  quicklist 是 ziplist 和链表的结合体，兼顾内存利用率和操作效率。
• 特点：
  • 高效存储：链表中的每个节点存储一个 ziplist。
  • 灵活性强：既支持高效的插入删除，又节省内存。
• 结构：
  1. typedef struct quicklistNode {
  2. unsigned char *zl; // ziplist 数据
  3. struct quicklistNode *prev; // 前驱节点
  4. struct quicklistNode *next; // 后继节点
  5. } quicklistNode;

  复制代码
• 应用场景：
  • 实现 Redis 的列表类型（List）。

---

zipmap（压缩字典）

• 简介：
  zipmap 是一种轻量级的哈希表结构，用于小规模场景。
• 特点：
  • 内存占用小：适合存储少量键值对。
  • 直接持有数据：不支持嵌套结构。
• 结构：
  • 由紧凑的键值对序列组成，节省内存。
• 应用场景：
  • 实现 Redis 的哈希类型（当数据量较小时）。

---

redisObject：衔接底层数据结构与 Value Type 的桥梁

在 Redis 中，redisObject 是一个核心的数据结构，主要用于衔接 Redis 的 Value Type（数据类型） 和 底层存储实现。每个 Redis 中的 Key 和 Value 实际上都是一个 redisObject 实例。

redisObject 的结构
redisObject 的主要结构如下：

1. typedef struct redisObject {
2. unsigned type:4; // 数据类型（Value Type），如 String、Hash、List、Set、ZSet。
3. unsigned encoding:4; // 数据的底层编码类型，如 raw、int、ziplist、hashtable。
4. unsigned lru:24; // 最近一次访问时间（LRU，用于内存管理）。
5. int refcount; // 引用计数，用于内存回收。
6. void *ptr; // 指向具体数据的指针。
7. } robj;

复制代码

redisObject 的关键字段

1. type（数据类型）：

   • 表示 Value 的逻辑类型。
   • 包括：String、Hash、List、Set、ZSet 等。
   • 决定了 Redis 对外暴露的操作接口。

2. encoding（底层实现编码）：

   • 指定该数据类型使用的底层存储结构。
   • 不同的数据类型可能有多种底层实现，例如：
     • String 类型：raw（普通字符串）或 int（整型优化）。
     • Hash 类型：ziplist（压缩列表）或 hashtable（哈希表）。
     • List 类型：quicklist。
   • Redis 会根据数据规模自动选择最合适的底层结构。

3. lru（最近访问时间）：

   • 用于记录该对象的最近访问时间（以秒为单位）。
   • 配合 Redis 的 LRU 内存淘汰策略，决定是否需要将对象从内存中删除。

4. refcount（引用计数）：

   • 用于引用管理，避免重复内存分配。
   • 当引用计数为 0 时，Redis 会回收该对象的内存。

5. ptr（指针）：

   • 指向实际存储数据的地址。
   • 数据存储的具体形式由 encoding 决定。

---

redisObject 的作用

1. 连接 Value Type 和底层实现：

   • RedisObject 的 type 表示数据的逻辑类型。
   • RedisObject 的 encoding 表示底层实现，负责优化内存和性能。
   • 通过 redisObject，Redis 能在不改变逻辑接口的前提下，动态切换底层实现。

2. 内存管理：

   • 使用 refcount 和 lru 实现高效的内存管理。
   • 支持对象的生命周期管理和 LRU 淘汰机制。

3. 提高灵活性：

   • RedisObject 的多层抽象允许 Redis 在各种场景中灵活优化性能，例如：
     • 小数据用压缩结构（如 ziplist）节省内存。
     • 大数据用高效结构（如 hashtable）提高操作速度。

历史文章

MySQL数据库

1. MySQL数据库笔记——数据库三范式
2. MySQL数据库笔记——存储引擎（InnoDB、MyISAM、MEMORY、ARCHIVE）
3. MySQL数据库笔记——常见的几种锁分类
4. MySQL数据库笔记——索引介绍
5. MySQL数据库笔记——事务介绍
6. MySQL数据库笔记——索引结构之B+树
7. MySQL数据库笔记——索引潜规则（回表查询、索引覆盖、索引下推）
8. MySQL数据库笔记——索引潜规则（最左前缀原则）
9. MySQL数据库笔记——常见慢查询优化方式
10. MySQL数据库笔记——日志介绍
11. MySQL数据库笔记——多版本并发控制MVCC
12. MySQL数据库笔记——主从复制