• 0

  • 0

面试必会!Redis 数据类型与数据结构

1个月前

一、Redis的数据类型

  在新版Redis(version>5.0)中共有九种数据类型,其中包含常用的基础数据类型分为String(字符串)、List(列表)、Hash(哈希)、Set(集合)和 Sorted Set(有序集合);以及四个高级数据类型:Bitmaps(位集合)、HyperLogLogs(基数统计的算法)、Geospatial Indexes(地理空间索引)、Streams(流信息)。
  本文着重介绍我们常用的五大基础数据类型:

1.1 String(字符串)

  string 是 redis 最基本的类型,一个 key 对应一个 value。string 类型是二进制安全的,string 可以包含任何数据,最大能存储 512MB。
常用命令

SET key value
设置指定 key 的值
GET key
获取指定 key 的值。
GETRANGE key start end
返回 key 中字符串值的子字符
GETSET key value
将给定 key 的值设为 value ,并返回 key 的旧值(old value)。
GETBIT key offset
对 key 所储存的字符串值,获取指定偏移量上的位(bit)。
MGET key1 [key2..]
获取所有(一个或多个)给定 key 的值。
SETBIT key offset value
对 key 所储存的字符串值,设置或清除指定偏移量上的位(bit)。
SETEX key seconds value
将值 value 关联到 key ,并将 key 的过期时间设为 seconds (以秒为单位)。
SETNX key value
只有在 key 不存在时设置 key 的值。
SETRANGE key offset value
用 value 参数覆写给定 key 所储存的字符串值,从偏移量 offset 开始。
STRLEN key
返回 key 所储存的字符串值的长度。
MSET key value [key value ...]
同时设置一个或多个 key-value 对。
MSETNX key value [key value ...]
同时设置一个或多个 key-value 对,当且仅当所有给定 key 都不存在。
PSETEX key milliseconds value
这个命令和 SETEX 命令相似,但它以毫秒为单位设置 key 的生存时间,而不是像 SETEX 命令那样,以秒为单位。
INCR key
将 key 中储存的数字值增一。
INCRBY key increment
将 key 所储存的值加上给定的增量值(increment) 。
INCRBYFLOAT key increment
将 key 所储存的值加上给定的浮点增量值(increment) 。
DECR key
将 key 中储存的数字值减一。
DECRBY key decrement
key 所储存的值减去给定的减量值(decrement) 。
APPEND key value
如果 key 已经存在并且是一个字符串, APPEND 命令将指定的 value 追加到该 key 原来值(value)的末尾。

1.2 List(列表)

  List是简单的字符串列表,按照插入顺序排序。可以添加一个元素到列表的头部(左边)或者尾部(右边)。List经常会被用于消息队列的服务,以完成多程序之间的消息交换。list类型最多可存储 232 - 1 元素 (4294967295, 每个列表可存储40多亿)。

BLPOP key1 [key2 ] timeout
移出并获取列表的第一个元素, 如果列表没有元素会阻塞列表直到等待超时或发现可弹出元素为止。
BRPOP key1 [key2 ] timeout
移出并获取列表的最后一个元素, 如果列表没有元素会阻塞列表直到等待超时或发现可弹出元素为止。
BRPOPLPUSH source destination timeout
从列表中弹出一个值,将弹出的元素插入到另外一个列表中并返回它; 如果列表没有元素会阻塞列表直到等待超时或发现可弹出元素为止。
LINDEX key index
通过索引获取列表中的元素
LINSERT key BEFORE|AFTER pivot value
在列表的元素前或者后插入元素
LLEN key
获取列表长度
LPOP key
移出并获取列表的第一个元素
LPUSH key value1 [value2]
将一个或多个值插入到列表头部
LPUSHX key value
将一个值插入到已存在的列表头部
LRANGE key start stop
获取列表指定范围内的元素
LREM key count value
移除列表元素
LSET key index value
通过索引设置列表元素的值
LTRIM key start stop
对一个列表进行修剪(trim),就是说,让列表只保留指定区间内的元素,不在指定区间之内的元素都将被删除。
RPOP key
移除列表的最后一个元素,返回值为移除的元素。
RPOPLPUSH source destination
移除列表的最后一个元素,并将该元素添加到另一个列表并返回
RPUSH key value1 [value2]
在列表中添加一个或多个值
RPUSHX key value
为已存在的列表添加值

1.3 Hash(哈希)

  Redis hash 是一个键值(key=>value)对集合;是一个 string 类型的 field 和 value 的映射表,每个 hash 可以存储 232 -1 键值对(40多亿)。

HDEL key field1 [field2]
删除一个或多个哈希表字段
HEXISTS key field
查看哈希表 key 中,指定的字段是否存在。
HGET key field
获取存储在哈希表中指定字段的值。
HGETALL key
获取在哈希表中指定 key 的所有字段和值
HINCRBY key field increment
为哈希表 key 中的指定字段的整数值加上增量 increment 。
HINCRBYFLOAT key field increment
为哈希表 key 中的指定字段的浮点数值加上增量 increment 。
HKEYS key
获取所有哈希表中的字段
HLEN key
获取哈希表中字段的数量
HMGET key field1 [field2]
获取所有给定字段的值
HMSET key field1 value1 [field2 value2 ]
同时将多个 field-value (域-值)对设置到哈希表 key 中。
HSET key field value
将哈希表 key 中的字段 field 的值设为 value 。
HSETNX key field value
只有在字段 field 不存在时,设置哈希表字段的值。
HVALS key
获取哈希表中所有值。
HSCAN key cursor [MATCH pattern] [COUNT count]
迭代哈希表中的键值对。

1.4 Set(集合)

  Set是string类型的无序集合。和List一样,在执行插入和删除和判断是否存在某元素时,效率是很高的。集合最大的优势在于可以进行交集并集差集操作。Set中最大的成员数为 232 - 1(4294967295, 每个集合可存储40多亿个成员)。

SADD key member1 [member2]
向集合添加一个或多个成员
SCARD key
获取集合的成员数
SDIFF key1 [key2]
返回第一个集合与其他集合之间的差异。
SDIFFSTORE destination key1 [key2]
返回给定所有集合的差集并存储在 destination 中
SINTER key1 [key2]
返回给定所有集合的交集
SINTERSTORE destination key1 [key2]
返回给定所有集合的交集并存储在 destination 中
SISMEMBER key member
判断 member 元素是否是集合 key 的成员
SMEMBERS key
返回集合中的所有成员
SMOVE source destination member
将 member 元素从 source 集合移动到 destination 集合
SPOP key
移除并返回集合中的一个随机元素
SRANDMEMBER key [count]
返回集合中一个或多个随机数
SREM key member1 [member2]
移除集合中一个或多个成员
SUNION key1 [key2]
返回所有给定集合的并集
SUNIONSTORE destination key1 [key2]
所有给定集合的并集存储在 destination 集合中
SSCAN key cursor [MATCH pattern] [COUNT count]
迭代集合中的元素

1.5 Zset(有序集合)

  Zset 和 set 一样也是string类型元素的集合,且不允许重复的成员。Zset是插入有序的,即自动排序。
  Zset每个元素都会关联一个double类型的分数。Redis是通过分数来为集合中的成员进行从小到大的排序。zset的成员是唯一的,但分数(score)却可以重复。

ZADD key score1 member1 [score2 member2]
向有序集合添加一个或多个成员,或者更新已存在成员的分数
ZCARD key
获取有序集合的成员数
ZCOUNT key min max
计算在有序集合中指定区间分数的成员数
ZINCRBY key increment member
有序集合中对指定成员的分数加上增量 increment
ZINTERSTORE destination numkeys key [key ...]
计算给定的一个或多个有序集的交集并将结果集存储在新的有序集合 key 中
ZLEXCOUNT key min max
在有序集合中计算指定字典区间内成员数量
ZRANGE key start stop [WITHSCORES]
通过索引区间返回有序集合指定区间内的成员
ZRANGEBYLEX key min max [LIMIT offset count]
通过字典区间返回有序集合的成员
ZRANGEBYSCORE key min max [WITHSCORES] [LIMIT]
通过分数返回有序集合指定区间内的成员
ZRANK key member
返回有序集合中指定成员的索引
ZREM key member [member ...]
移除有序集合中的一个或多个成员
ZREMRANGEBYLEX key min max
移除有序集合中给定的字典区间的所有成员
ZREMRANGEBYRANK key start stop
移除有序集合中给定的排名区间的所有成员
ZREMRANGEBYSCORE key min max
移除有序集合中给定的分数区间的所有成员
ZREVRANGE key start stop [WITHSCORES]
返回有序集中指定区间内的成员,通过索引,分数从高到低
ZREVRANGEBYSCORE key max min [WITHSCORES]
返回有序集中指定分数区间内的成员,分数从高到低排序
ZREVRANK key member
返回有序集合中指定成员的排名,有序集成员按分数值递减(从大到小)排序
ZSCORE key member
返回有序集中,成员的分数值
ZUNIONSTORE destination numkeys key [key ...]
计算给定的一个或多个有序集的并集,并存储在新的 key 中
ZSCAN key cursor [MATCH pattern] [COUNT count]
迭代有序集合中的元素(包括元素成员和元素分值)

二、Redis的数据结构

imgimg

2.1 简单动态字符串

  Redis并未使用c语言的string,而是自己构建简单动态字符串(SDS,simple dynamic string)抽象类型表示字符串。SDS相对于C字符串有以下优势:

  • SDS由于记录了len,所有strlen获取字符串长度O(1),C中遍历O(n)。
  • SDS杜绝缓冲区溢出
    C中字符串不记录长度容易造成缓冲区溢出,SDS API修改SDS时,API先检查空间是否足够,不够自动空间扩展后再修改(全自动避免缓冲区溢出)
  • 减少修改字符串时带来的内存重分配次数
    SDS通过未使用空间接触了字符串长度和底层数组长度之间的关联.有了free属性在,buf数组长度不一定是+1,因为其中可以包含未使用字节。未使用空间帮助SDS实现了以下两种优化策略:
    • 空间预分配(增)
      用于优化SDS字符串增长操作
    • 惰性空间释放(减)
      用于优化SDS字符串缩短操作
  • 二进制安全
    SDS处理存放在buf数组中的数据不会做任何改变,所以buf属性被称为字节数组—>redis不是用buf字节数组保存字符,而是保存二进制数据.
    ​ 1、保存二进制数据,存入数据不变化.
    ​ 2、用len属性而不是空字符串或者判断字符串是否结束

2.2 双向链表

  双向链表是顺序读写,通过数组下标或者链表的指针逐个元素访问,操作复杂度基本是 O(N),操作效率比较低;双向链表会记录表头和表尾的偏移量。在列表的头尾增删元素,就可以通过偏移量直接定位,所以它们的复杂度也只有 O(1),可以实现快速操作。

2.3 压缩列表

  压缩列表实际上类似于一个数组,数组中的每一个元素都对应保存一个数据。和数组不同的是,压缩列表在表头有三个字段 zlbytes、zltail 和 zllen,分别表示列表长度、列表尾的偏移量和列表中的 entry 个数;压缩列表在表尾还有一个 zlend,表示列表结束。在压缩列表中,如果我们要查找定位第一个元素和最后一个元素,可以通过表头三个字段的长度直接定位,复杂度是 O(1)。而查找其他元素时,就没有这么高效了,只能逐个查找,此时的复杂度就是 O(N) 了。

2.4 哈希表

  在Redis中,键值对就是通过哈希表存储。哈希表就是一个数组,数组中每个元素称为一个哈希桶。每个哈希桶中保存了键值对数据。哈希桶中的元素保存的并不是值本身,而是指向具体值的指针。
哈希表的最大好处就是可以用 O(1) 的时间复杂度来快速查找到键值对。
  当哈希表存储了大量数据后,哈希表就会存在冲突问题和 rehash 可能带来的操作阻塞。Redis 解决哈希冲突的方式,就是链式哈希。链式哈希就是指同一个哈希桶中的多个元素用一个链表来保存,它们之间依次用指针连接。
  Redis 通过rehash来解决哈希链表过长的问题。rehash就是增加现有的哈希桶数量,让逐渐增多的 entry 元素能在更多的桶之间分散保存,减少单个桶中的元素数量,从而减少单个桶中的冲突。
  Redis默认使用了两个全局哈希表,轮询使用 。rehash过程分为三步:

  • 给哈希表 2 分配更大的空间
  • 把哈希表 1 中的数据重新映射并拷贝到哈希表 2 中
  • 释放哈希表 1 的空间

2.5 跳表

  有序链表只能逐一查找元素,导致操作起来非常缓慢,于是就出现了跳表。具体来说,跳表在链表的基础上,增加了多级索引,通过索引位置的几个跳转,实现数据的快速定位。当数据量很大时,跳表的查找复杂度就是 O(logN)。

2.6 整数数组

  整数数组是顺序读写,通过数组下标或者链表的指针逐个元素访问,操作复杂度基本是 O(N),操作效率比较低;整数数组这些数据结构时,这些结构中专门记录了元素的个数统计,因此可以高效地完成相关操作。

免责声明:文章版权归原作者所有,其内容与观点不代表Unitimes立场,亦不构成任何投资意见或建议。

0

相关文章推荐

未登录头像

暂无评论