Redis数据结构：高频面试题及解析

概述

Redis 是速度非常快的非关系型（NoSQL）内存键值数据库，可以存储键和五种不同类型的值之间的映射。
键的类型只能为字符串，值支持五种数据类型：字符串、列表、集合、散列表、有序集合。
Redis 支持很多特性，例如将内存中的数据持久化到硬盘中，使用复制来扩展读性能，使用分片来扩展写性能。
数据类型

数据类型可以存储的值操作STRING字符串、整数或者浮点数对整个字符串或者字符串的其中一部分执行操作，对整数和浮点数执行自增或者自减操作LIST列表从两端压入或者弹出元素，对单个或者多个元素进行修剪，只保留一个范围内的元素SET无序集合添加、获取、移除单个元素，检查一个元素是否存在于集合中，计算交集、并集、差集，从集合里面随机获取元素HASH包含键值对的无序散列表添加、获取、移除单个键值对，获取所有键值对，检查某个键是否存在ZSET有序集合添加、获取、删除元素，根据分值范围或者成员来获取元素，计算一个键的排名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 的一个重要组成部分。

1. > set hello world
2. OK
3. > get hello
4. "world"
5. > del hello
6. (integer) 1
7. > get hello
8. (nil)

复制代码

LIST

Redis 的 List 类型底层数据结构可以由双向链表或压缩列表实现。如果列表元素个数小于 512 个且每个元素的值都小于 64 字节，则 Redis 会使用压缩列表作为底层数据结构；否则，Redis 会使用双向链表作为底层数据结构。然而，在 Redis 3.2 版本之后，List 类型底层数据结构只由 quicklist 实现，代替了双向链表和压缩列表。

1. > rpush list-key item
2. (integer) 1
3. > rpush list-key item2
4. (integer) 2
5. > rpush list-key item
6. (integer) 3
8. > lrange list-key 0 -1
9. 1) "item"
10. 2) "item2"
11. 3) "item"
13. > lindex list-key 1
14. "item2"
16. > lpop list-key
17. "item"
19. > lrange list-key 0 -1
20. 1) "item2"
21. 2) "item"

复制代码

SET

Set 类型的底层数据结构可以是哈希表或整数集合。当集合中的元素都是整数并且元素个数小于512时，Redis使用整数集合作为Set类型的底层数据结构；否则，Redis使用哈希表作为Set类型的底层数据结构。

1. > sadd set-key item
2. (integer) 1
3. > sadd set-key item2
4. (integer) 1
5. > sadd set-key item3
6. (integer) 1
7. > sadd set-key item
8. (integer) 0
10. > smembers set-key
11. 1) "item"
12. 2) "item2"
13. 3) "item3"
15. > sismember set-key item4
16. (integer) 0
17. > sismember set-key item
18. (integer) 1
20. > srem set-key item2
21. (integer) 1
22. > srem set-key item2
23. (integer) 0
25. > smembers set-key
26. 1) "item"
27. 2) "item3"

复制代码

HASH

Redis 中的 Hash 类型的底层数据结构可以是压缩列表或哈希表。如果元素个数小于 512 个且每个元素的值都小于 64 字节，Redis 会使用压缩列表作为底层数据结构；否则会使用哈希表。在 Redis 7.0 中，压缩列表已经废弃，改用 listpack 数据结构来实现。

1. > hset hash-key sub-key1 value1
2. (integer) 1
3. > hset hash-key sub-key2 value2
4. (integer) 1
5. > hset hash-key sub-key1 value1
6. (integer) 0
8. > hgetall hash-key
9. 1) "sub-key1"
10. 2) "value1"
11. 3) "sub-key2"
12. 4) "value2"
14. > hdel hash-key sub-key2
15. (integer) 1
16. > hdel hash-key sub-key2
17. (integer) 0
19. > hget hash-key sub-key1
20. "value1"
22. > hgetall hash-key
23. 1) "sub-key1"
24. 2) "value1"

复制代码

ZSET

Zset 类型的底层数据结构可以是压缩列表或跳表。
如果有序集合的元素个数小于 128 个，且每个元素的值小于 64 字节，则 Redis 会使用压缩列表作为 Zset 类型的底层数据结构。
如果有序集合的元素个数大于等于 128 个或者每个元素的值大于等于 64 字节，则 Redis 会使用跳表作为 Zset 类型的底层数据结构。
需要注意的是，Redis 7.0 中废弃了压缩列表数据结构，改用 listpack 数据结构来实现。

1. > zadd zset-key 728 member1
2. (integer) 1
3. > zadd zset-key 982 member0
4. (integer) 1
5. > zadd zset-key 982 member0
6. (integer) 0
8. > zrange zset-key 0 -1 withscores
9. 1) "member1"
10. 2) "728"
11. 3) "member0"
12. 4) "982"
14. > zrangebyscore zset-key 0 800 withscores
15. 1) "member1"
16. 2) "728"
18. > zrem zset-key member1
19. (integer) 1
20. > zrem zset-key member1
21. (integer) 0
23. > zrange zset-key 0 -1 withscores
24. 1) "member0"
25. 2) "982"

复制代码

最后

为了方便其他设备和平台的小伙伴观看往期文章，链接奉上：
牛客，知乎，开源中国，CSDN，思否，掘金，InfoQ，简书，博客园，慕课，51CTO，helloworld，腾讯开发者社区，阿里开发者社区
看完如果觉得有帮助，欢迎点赞、收藏和关注

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！