跳到主要内容

Redis的基础数据结构

Reids 所有的数据结构都以唯一的 key 字符串作为名称,然后通过这个唯一的 key 值来获取相应的 value 数据。不同的数据结构差异就在于 value 的结构不一样。

# 一、Redis 五大数据类型

【1】String(字符串)StringRedis 最基本的类型,一个 key 对应一个valueString 类型是二进制安全的。意思是 RedisString 可以包含任何数据。一个键最大能存储 512MB
【2】Hash(哈希)Hash 是一个键值对集合,类似 Java 里的 MapRedisHash 是 一个 String 类型的 filedvalue 的映射表,hash 特别适合存储对象。
【3】List(列表)Redis 列表是简单的字符串列表,按照插入顺序排序,可以在列表的头部或者尾部插入新的节点。
【4】Set(集合)RedisSetString 类型的无序集合。集合是通过哈希表(散列表)实现的,所有添加、删除、查找的效率都是一样的。一个集合最多可以包含2^32-1个元素。
【5】Zsetsorted set有序集合 Reids ZsetSet 一样也是 String 类型元素的结合,且不允许重复的成员。不同的是每个元素都会关联一个 double 类型的分数 scoreRedis 正是通过分数来为集合中的成员进行从小到大的排序。Zset 的成员是唯一的,但是分数是可以重复的。
获得 redis常见数据类型操作命令】:链接 (opens new window)

# 二、Redis 字符串String

字符串 StringReids 中最简单的数据结构,如下图所示,它的内部就是一个字符数组。
String
Reids 的字符串是动态字符串,是可以修改的字符串,内部结构的实现类似于 JavaArrayList采用预分配冗余空间的方式来减少内存的频繁分配,如下图所示:内部为当前字符串分配的实际空间 capacity 一般要高于实际字符串长度 len。需要注意的是字符串最大长度为 512MB。
String
String 常用命令: 支持简单的增删改查操作;
SET:将字符串值 value 关联到 key。如果 key 已经持有其它值, SET 就覆盖旧值【SET key value】;
GET:获取某个 keyvalue 值【GET key】;
MGET:一次获得多个 key 的数据【MGET key1 key2 ...】,节省网络耗时开销;
MSET:一次设置多个 key 的数据【MSET key1 value1 key2 value2 ...】,节省网络耗时开销;
EXISTS:判断一个键是否存在,存在返回 1;否则返回 0【EXISTS key】;
DEL:删除某个 key 或者一些列 keyDEL key1 key2 ...】;
KEYS:返回匹配的 key 列表(KEYS foo* 指查找 foo 开头的 keys)【KEYS *】;
RENAME:更改 key 的名字,如果新名字已存在则更改失败【REMANE key1 key2】;
DBSIZE:返回当前 key 的总数【DBSIZE】;
EXPIRE:设置某个 key 的过期时间(单位:秒)【EXPIRE key 秒数】;
TTL:查找某个 key 的过期时间【TTL key】;
SETEX:设置过期时间,等价于 set+expireSETEX key time value】;
SETNX:如果 key 不存在则执行 set 创建,返回 1。否则不创建返回 0【SETNX key value】;
INCR/DECR/INCRBY/DECRBY:前两个是递增 1 和递减 1 【INCR key】,后两个是指定递增和递减的数字【INCRBY KEY 倍数】。前提是一定要是数字才能进行加减;

# 三、Redis列表List

Redis 的列表相当于 Java 语言里面的 LinkedList,注意它是链表而不是数组。这就意味着 list 的插入和删除操作非常快,时间复杂度为 O(1) ,但是索引定位很慢,时间复杂度为 O(n),这点让人非常意外,如下图所示,列表中的每个元素都使用双向指针顺序,串起来可以同时支持向前向后遍历。当列表弹出最后一个元素之后,该数据结构被自动删除,内存被回收。Redis 的列表结构常用来做异步队列使用。将需要延后处理的任务结构体序列化成字符串,塞进 Redis 列表,另一个线程从这个列表中轮询数据进行处理。
List

List 常用命令: 可以通过 pushpop 操作从链表的头部或者尾部添加删除元素。list 既可以用作栈,也可以用作队列。
1)、LPUSH:将一个或多个值插入到列表头部【lpush key value1 [value2 ...]
2)、RPUSH:从尾部加入元素(队列)先进先出【rpush key value1 [value2 ...]
3)、LPOP:移除并获取列表中的第一个元素【lpop key
4)、RPOP:移除并获取列表中的最后一个元素【rpop key
5)、LRANGE:获取列表中指定范围内的元素【lrange key start stop
6)、LLEN:获取 List 的长度【llen key

慢操作:lindex 相对于 Java 链表的 get(int index) 方法,它需要对链表进行遍历,性能会随着参数 index 增大而变差。 ltrim 的两个参数 start_indexend_index 定义了一个区间,在这个区间内的值,ltrim 保留,区间之外的统统丢弃掉。我们可以通过 ltrim 实现一个定长的链表,这一点非常有用。index 可以为负数,index=-1表示倒数第一个元素,同理index=-2表示倒数第二个元素。 1)、LINDEX KEY INDEX:获取下标为 index 的元素(O(n) 慎用); 2)、LRANG KEY START END:根据下标区间获取 value 值; 3)、LTRIM KEY START END:根据下标截取 list,通过 ltrim key 1 0 #表示清空这个列表,因为区间范围长度为负;

快速列表:如果更深入一点,会发现 Redis 底层存储的不是一个简单的 LinkedList,而是称之为 “快速链表”(QuickList)的一个结构。首先在列表元素较少的情况下,会使用一块连续的内存存储,这个结构是 ziplist,即压缩列表。它将所有的元素彼此紧挨着一起存储,分配的是一块连续的内存。当数据比较多的时候才会改成 QuickList。因为普通的链表需要的附加指针空间太大,会浪费空间,还会增加内存的碎片化,比如某个普通链表里面存的只是 int 类型的数据,结构上还需要两个额外的指针 prevnext。所以 Redis链表和 ziplist 结合起来组成了 quicklist,也就是将多个 ziplist 使用双向指针串起来使用。如下图所示,quicklist 即满足快速的插入删除特性,又不会出现太大的空间冗余。
ZipList

# 四、Redis集合Set

Redis 的集合Set 相当于 Java 语言里面的 HashSet,它内部的键值对是无序的、唯一的。它的内部实现相当于一个特殊的HashMapHashMap 中所有的 value 都是一个 NULL 值。当集合中最后一个元素被移除后,数据结构被自动删除,内存被回收。

Set 常用命令: Set 对外提供的功能与 List 类似是一个列表的功能,特殊之处在于 set 是可以自动排重的,并且 set 提供了判断某个成员是否在一个 Set 集合内的重要接口。Redis 还为集合提供了求 交集、并集、差集 等操作。基本命令操作如下:
【1】SADD:向集合添加一个或多个成员【sadd key value1[value2...]
【2】SISMEMBER:判断集合中是否存在 key 的成员【sismember key value
【3】SMEMBERS:返回集合中的所有成员【smembers key
【4】SUNION:返回所有给定集合的并集sunion key1 [key2...]
【5】SINTER:返回所有给定集合的交集sinter key1 [key2...]
【6】SDIFF:返回所有给定集合的差集sinter key1 [key2...]

# 五、有序集合Sorted sets

Zset 可能是 Redis 提供的最有特色的数据结构,它也是在面试中面试官最爱问的数据结构。它类似于 JavaSortedSetHashMap 的结合体,一方面它是一个 set,保证了内部的唯一性,另一方面它可以给每个 value 赋予一个 score,代表这个 value 的排序权重。它的内部实现使用 “跳跃列表” 的数据结构;zset 中最后一个 value 被移除后,数据结构被自动删除,内存被回收;Redis 有序集合非常适合与那些有序无重复数据的存储,例如:游戏开发中的排行榜、登记榜、经验榜等。如果沿用传统的方式,一般是通过后端的定时任务去跑数据来完成排行榜。这种方法一方面无法满足产品对功能实时性的要求,另一方面也消耗了服务器的资源。

ZSet 常用命令: 常用命令如下:
1)、ZADD:向集合中添加一个或多个元素,或者更新已存在的元素【zadd key score1 member1 [score2 member2]】;
2)、ZRANGE:通过索引区间返回有序集合指定的成员【zrange key start stop [WITHSCORES]】;
3)、ZRANK:返回集合中指定成员的索引(下标)【zrank key member】;
4)、ZREM:移除有序集合中一个或多个成员【zrem key member1 [member2 ...]】;
5)、ZREVRANGE:逆向返回有序集中指定区间的成员,通过索引分数从高到低【zrevrange key start stop [WITHSCORES]】;
6)、ZCARD:相当于 count()zcard key】;
7)、ZSCORE:获取指定 valuescorezscore key value】;
8)、ZRANGBYSCORE:根据分值区间遍历 zsetzrangbyscore key start end】;

跳跃列表: zset 内部的排序功能是通过“跳跃列表”数据结构来实现,它的结构非常特殊,也比较复杂。因为 zset 要支持随机的插入和删除,所以它不宜使用数组来表示。我们先看一个普通的链表结构:
zset
此链表将按照 score 进行排序,当我们插入一个新元素的时候,要定位到特定的位置,才可以继续保证链表是有序的。通常我们会通过二分查找来找到插入点,但是二分查找的对象必须是数组,只有数组才可以支持快速位置定位,链表做不到;因此就出现了跳跃列表数据结构; 跳跃列表就类似一个 B树(层级制),最下面一层所有的元素会串起来。然后每隔几个元素挑选一个代表,再将这几个代表使用另外一个指针串起来。然后在这些代表里再调出二级代表,再串起来。最终形成一个金字塔机构。“跳跃列表”之所以“跳跃”是因为内部元素可能“身兼数职”,比如如下图所示:中间这个元素,同时处于L0、L1和L2层中,可以快速在不同层次之间进行“跳跃”。
score
定位插入点时,现在顶层进行定位,然后下潜到下一级定位,一直下潜到最底层找到合适的位置,将新元素插进去。那么新元素如何才有机会“身兼数职”呢?跳跃列表采取一种随机策略决定新元素可以兼职到几层。首先位于 L0 层的概率为是 100%,而兼职L1 层的概率有 50%,到L2层的概率 25%,到L3层只有12.5%的概率,一次类推,一直随机到最顶层L31层。绝大多数元素都过不了几层,只有极少数元素可以深入到顶层。列表中的元素越多,够深入的层次就越深,元素能进入到顶层的可能性就会大。

# 六、哈希Hash

Redis 的字典(Hash)相当于Java 语言里面的 HashMap,它是无序字典,内部存储了很多键值对。实现结构与 JavaHashMap 是一样的,都是“数组+链表”(JDK1.7)。不同的是,Redis 的字典值只能是字符串,另外他们 rehash(扩容后需要重新计算hash值,分配地址)的方式不一样,因为 JavaHashMap 在字典很大时,rehash 是个耗时的操作,需要一次性全部rehashRedis 追求性能,不能堵塞服务,所以采用了渐进式 rehash 策略。渐进式 rehash 会在 rehash 时保留新旧两个 hash 结构,查询时会同时查询两个 hash 结构,然后在后续的定时任务以及 hash 操作指令中,循环渐进地将旧 hash 的内容一点点地迁移到新的 hash 结构中。当迁移完成了,就会使用新的 hash 结构取而代之。

HashMap

Hash 常用命令:hash 移除最后一个元素之后,该数据结构被自动删除,内存被回收。字典常用命令如下:
【1】HSET:将哈希表 key 中的字段 field 的值设为 valuehset key field value】;
【2】HGET:获取存储在哈希表中指定字段的值【hget key field】;
【3】HGETALL:获取哈希表中,指定 key 的所有字段和值【hgetall key】;
【4】HDEL:删除一个或多个哈希表字段【hdel key field1 [field2...]】;
【5】HMSET:同时将多个 field-value(域-值)设置到哈希表 keyhmset key field value [field1 value1 ...]】;
【6】HLEN:获取 key 中存储的元素个数【hlen key】;

# 七、Hyperloglog

当需要做计数统计场景,都可以使用 hyperloglog,只要允许容错,它有 0.81%的错误率,如果不允许容错,就可以使用 set或者自己的数据类型即可。优点是节省内存:占用的内存是固定的,如果要存数据,hyperloglog存 2^64的数据只需要占用 12kb内存。