Redis 数据结构

简介

Redis（Remote Dictionary Server）是一个使用ANSI C编写的开源、支持网络、基于内存、分布式、可选持久性的键值对存储数据库。根据月度排行网站DB-Engines.com的数据，Redis是最流行的键值对存储数据库。其最主要的特性就是速度极快，可以达到QPS10万+。

数据结构

数据格式

string

字符串是Redis中最基本的数据结构。它们可以存储任何类型的数据，例如文本、数字或二进制数据。Redis的字符串数据结构还提供了一些对字符串进行操作的特殊功能，例如计数器递增、截取和追加等。

内部编码分三种： raw int embstr

操作时间复杂度：

• 获取和设置操作：O(1)
• 追加操作：对于小字符串，O(1)；对于大字符串，O(N)，其中N是字符串的长度。

hash

哈希是一个键值对集合，其中每个键都唯一且与一个值相关联。Redis的哈希数据结构非常适合存储对象，并且可以轻松地对对象的字段进行读取、更新和删除操作。通过哈希，您可以将复杂的数据结构表示为单个Redis键，并在需要时对其进行高效的访问和修改。

内部编码分两种：hashtable ziplist

当字符串可以转换为64位有符号整数时，Redis会使用int编码，这样可以减少内存使用和提高性能。对于较长的字符串，Redis使用raw编码，将字符串作为字节数组存储。对于较短的字符串，Redis使用embstr编码，将字符串存储在一个连续的内存块中。

操作时间复杂度：

• 获取和设置操作：O(1)
• 获取所有字段操作：O(N)，其中N是哈希中字段的数量。

list

列表是一个有序的字符串集合，允许在列表的两端进行元素的插入和删除操作。您可以通过索引访问列表中的元素，还可以使用一些内置的命令对列表进行修剪、获取子列表等操作。Redis的列表数据结构可以用于实现队列、堆栈等数据结构。

内部编码分两种：quicklist ziplist

列表数据结构使用双向链表实现。对于较小的列表，Redis使用ziplist编码方式，将列表元素存储在一块连续的内存中，节省了存储空间。对于较大的列表，Redis使用quicklist编码方式，将列表拆分为多个ziplist，并使用一个双向链表来链接它们。（早期版本中是使用linkedlist和ziplist两种编码方式。然而，从Redis版本3.2开始，引入了一种新的编码方式称为quicklist，它是一种将ziplist和linkedlist结合起来的混合编码方式。)

操作时间复杂度：

• 头部和尾部的插入和删除操作：O(1)
• 根据索引获取和设置操作：O(N)，其中N是列表的长度。

set

集合是唯一值的无序集合。Redis的集合数据结构提供了添加、删除和检查元素的高效操作。您可以对集合执行交集、并集和差集等操作，还可以使用集合来解决一些集合运算问题，如查找共同的兴趣、查找唯一的元素等。

内部编码分两种：hashtable intset

intset和hashtable。对于只包含整数元素的小型集合，Redis使用intset编码方式，将整数存储在一个有序的整数数组中，以提高存储和访问性能。对于较大的集合或包含非整数元素的集合，Redis使用hashtable编码方式，使用散列表来存储集合元素。

操作时间复杂度：

• 添加、删除和获取操作：O(1)
• 集合之间的交集、并集和差集操作：O(M+N)，其中M和N是两个集合的大小。

zset

有序集合类似于集合，但每个元素都关联着一个分数（score）。这些分数用于对集合中的元素进行排序，并且允许您按范围进行查询。有序集合在需要按特定顺序访问元素的场景中非常有用，例如排行榜、范围查找等。

内部编码分两种：skiplist ziplist

ziplist和skiplist。对于较小的有序集合，Redis使用ziplist编码方式，将元素存储在一块连续的内存中。对于较大的有序集合，Redis使用skiplist编码方式，使用跳跃列表来存储元素，提供了快速的有序遍历和范围查询功能。

操作时间复杂度：

• 添加、删除和获取操作：O(1)
• 获取指定范围内的元素操作：O(log(N)+M)，其中N是有序集合的大小，M是返回的元素数量。