夏溪辰的博客

xiaxichen's blog

Redis 数据结构

63
2023-12-04

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是返回的元素数量。