摘要

文章介绍了 Redis 常见数据结构（字符串、列表、集合、映射、有序集合）的底层原理、进化过程、读写时间复杂度、不同版本有不同底层实现的原因以及一种数据类型有多种底层实现的原因等内容。

一、Redis 数据结构总览

Redis 是常用的内存数据库，了解其数据类型的底层原理有助于在业务场景中选择正确的数据类型，也是面试常见考点。

（一）阅读引导问题

1. 各种结构读写一条数据的时间复杂度是多少？
2. 为什么不同 Redis 版本有不同的底层实现？
3. 为什么一种数据类型有多种底层实现？

二、字符串类型

（一）C 语言字符串的问题

在 C 语言中定义字符串存在一些问题，如无法存储特殊字符�，字符串扩容缩容需新的数组，没有记录长度需遍历获取。

（二）Redis 的 SDS 结构

Redis 自定义了 SDS 结构，包含已使用长度len、总长度alloc、类型标识flags和存储字符串的buf。Redis 可根据字符串大小使用不同类型的 SDS 节省内存，同时有默认最大字符限制且可配置。

（三）字符串的编码

Redis 还定义了三种编码：int（8 字节长整形，数字小于 20）、embstr（小于等于 44 字节字符串）、raw（大于 44 字节字符串）。

三、列表类型（List）

（一）List 的基本操作与使用场景

List 类似 Java 中的 list，可当作队列或栈使用，能通过命令获取头尾部元素。

（二）底层结构的演进

1. linkedlist（3.2 版本之前）
   • 代码定义包含头指针、尾指针和链表长度等。
   • 是双端链表，但存在存储小值时指针占用空间大、查询效率低的问题。
2. ziplist（3.2 版本之前）
   • 结构代码包含压缩列表占用字节数、最后元素偏移量、元素个数、元素内容和结束标识等。
   • 可节省内存，但查询第 k 个数据时间复杂度为 O(N)，存在空间连续相关的问题。
3. quicklist（3.2 版本引入）
   • 结合 linkedlist 和 ziplist，整体为 linkedlist，每个节点是 ziplist。
   • 可控制 ziplist 元素个数，查询第 k 个元素时间复杂度为 O(logN)。
4. listpack（5.0 版本推出）
   • 内部结构包含总字节数、元素个数、存储元素、结束标识等。
   • 也是使用连续内存空间保存数据的数据结构。

四、集合类型（Set）

（一）intset 结构

当 Set 中的元素是 64 位以内整数且数量不超过 512 时使用 intset 结构，结构包含编码方式、元素个数和存储整数的数组。元素类型可升级不能降级，可通过二分法查询，时间复杂度为 O(logN)。

（二）map 结构

map 中的 key 是 set 的值，value 为 null。

五、映射类型（Map）

（一）ziplist 和 listpack

在满足一定条件（如 field - value 字节小于默认值、数量小于默认值）时使用，会对 field 和 value 加标识位区分。

（二）dict 结构

1. 由数组和链表构成，数组元素占用的槽位为 hash 桶，有 hash 冲突时在桶下挂链表。
2. 实体代码包含类型、两张散列表数组、散列表使用情况、rehash 标记位等。
3. 扩容缩容时机与负载因子有关，扩容是渐进式的，有详细的扩容过程。

六、有序集合类型（Sorted Set）

（一）ziplist 和 listpack

在元素数量和 member 占用字节数满足一定条件时使用，会把 member 和 score 组成 entry 并排序。

（二）skiplist + dict

1. dict 把 member 存于 key，score 存于 value，ZSCORE 命令时间复杂度为 O(1)。
2. skiplist（跳表）是多层级有序链表，上层是下层索引，查询时可根据跨度计算排名，节点层级采用随机方式确定。

七、总结

1. 之前文章多只描述数据类型所用结构，本文详细说明原理，有助于记忆。
2. 不同数据结构的读写时间复杂度不同，参考文章描述。
3. 底层实现更改原因与 ziplist 的连锁更新、linkedlist 的指针占用和内存不连续等有关。
4. 一种数据类型有多种底层实现是为了节约内存。