不同操作的复杂度

集合类型的操作类型很多，有读写单个集合元素的，例如 HGET、HSET，也有操作多个元素的，例如 SADD，还有对整个集合进行遍历操作的，例如 SMEMBERS。这么多操作，它们的复杂度也各不相同。 而复杂度的高低又是我们选择集合类型的重要依据。

1. 单元素操作，指每一种集合类型对单个数据实现的增删改查操作

比如 Hash 类型的 HGET、HSET 和 HDEL，Set 类型的 SADD、SREM 和 SRANDMEMBER 等。这类操作的时间复杂度由集合底层的数据结构决定，例如，HMSET 增加 M 个元素时，复杂度就从 O(1) 变成 O(M) 了。

2. 范围操作，指集合类型的遍历操作，返回集合所有数据

比如 Hash 类型的 HGETALL 和 Set 类型的 SMEMBERS，或者返回一个范围内的部分数据，比如 List 类型的 LRANGE 和 ZSet 类型的 ZRANGE。这类操作的复杂度一般是 O(N)。

Redis 从 2.8 版本增加 SCAN 系列操作，包括 HSCAN，SSCAN 和 ZSCAN），这类操作实现了渐进式遍历，每次只返回有限数量的数据。相比于 HGETALL、SMEMBERS 这类操作来说，就避免了一次性返回所有元素而导致的 Redis 阻塞。

3. 统计操作，指集合类型对集合中所有元素个数的记录

比如 LLEN 和 SCARD，它们操作时间复杂度 O(1)。当集合类型使用压缩列表、双向链表、整数数组等数据结构，这些数据结构专门有个字段记录元素个数统计。

4. 例外情况

一些数据结构的特殊记录，比如压缩列表和双向链表都会记录表头和表尾的偏移量。

List 类型的 LPOP、RPOP、LPUSH、RPUSH 操作是在列表头尾增删元素，可以通过偏移量直接定位，时间复杂度 O(1)。

总结

今天我们学习了 Redis 底层数据结构，包括保存所有键值的全局哈希表，以及实现集合类型的双向链表、压缩列表、整数数组、哈希表和跳表。

我们要注意底层实现结构是双向链表和压缩列表的 List 类型，时间复杂度是 O(N)。它的 POP/PUSH 效率很高，所以更适合 FIFO 队列业务场景，而不是作为随机读写存储数据的集合。

我们应该掌握原理，以不变应万变，掌握底层数据结构原理后就能从原理推断出不同操作的时间复杂度，然后根据业务场景选择合适的集合类型。