Redis 数据结构：高频面试题及解析
概述
Redis 是速度非常快的非关系型（NoSQL）内存键值数据库，可以存储键和五种不同类型的值之间的映射。
键的类型只能为字符串，值支持五种数据类型：字符串、列表、集合、散列表、有序集合。
Redis 支持很多特性，例如将内存中的数据持久化到硬盘中，使用复制来扩展读性能，使用分片来扩展写性能。
数据类型
STRING
Redis 的 String 类型使用 SDS（简单动态字符串）作为底层的数据结构实现。SDS 与 C 字符串有所不同，它不仅可以保存文本数据，还可以保存二进制数据。这是因为 SDS 使用 len 属性的值而不是空字符来判断字符串是否结束，并且 SDS 的所有 API 都会以处理二进制的方式来处理 SDS 存放在 buf[] 数组里的数据。因此，SDS 不仅能存放文本数据，还能保存图片、音频、视频、压缩文件等二进制数据。
另外，Redis 的 SDS API 是安全的，拼接字符串不会造成缓冲区溢出。这是因为 SDS 在拼接字符串之前会检查 SDS 空间是否满足要求，如果空间不够会自动扩容，从而避免了缓冲区溢出的问题。
此外，获取字符串长度的时间复杂度是 O(1)，因为 SDS 结构里用 len 属性记录了字符串长度，所以获取长度的复杂度为 O(1)。相比之下，C 语言的字符串并不记录自身长度，所以获取长度的复杂度为 O(n)。这些特性使得 SDS 成为 Redis 的一个重要组成部分。
LIST
Redis 的 List 类型底层数据结构可以由双向链表或压缩列表实现。如果列表元素个数小于 512 个且每个元素的值都小于 64 字节，则 Redis 会使用压缩列表作为底层数据结构；否则，Redis 会使用双向链表作为底层数据结构。然而，在 Redis 3.2 版本之后，List 类型底层数据结构只由 quicklist 实现，代替了双向链表和压缩列表。
SET
Set 类型的底层数据结构可以是哈希表或整数集合。当集合中的元素都是整数并且元素个数小于 512 时，Redis 使用整数集合作为 Set 类型的底层数据结构；否则，Redis 使用哈希表作为 Set 类型的底层数据结构。
HASH
Redis 中的 Hash 类型的底层数据结构可以是压缩列表或哈希表。如果元素个数小于 512 个且每个元素的值都小于 64 字节，Redis 会使用压缩列表作为底层数据结构；否则会使用哈希表。在 Redis 7.0 中，压缩列表已经废弃，改用 listpack 数据结构来实现。
ZSET
Zset 类型的底层数据结构可以是压缩列表或跳表。
如果有序集合的元素个数小于 128 个，且每个元素的值小于 64 字节，则 Redis 会使用压缩列表作为 Zset 类型的底层数据结构。
如果有序集合的元素个数大于等于 128 个或者每个元素的值大于等于 64 字节，则 Redis 会使用跳表作为 Zset 类型的底层数据结构。
需要注意的是，Redis 7.0 中废弃了压缩列表数据结构，改用 listpack 数据结构来实现。
最后
为了方便其他设备和平台的小伙伴观看往期文章，链接奉上：
牛客，知乎，开源中国，CSDN，思否，掘金，InfoQ，简书，博客园，慕课，51CTO，helloworld，腾讯开发者社区，阿里开发者社区
看完如果觉得有帮助，欢迎点赞、收藏和关注
版权声明: 本文为 InfoQ 作者【小万哥】的原创文章。
原文链接:【http://xie.infoq.cn/article/a74ea0f20c991a655aae72174】。文章转载请联系作者。
代码如人生 2023-02-09 加入
编程爱好者
评论