Redis基础数据结构
Redis 有 5 种基础数据结构,分别为:string (字符串)、list (列表)、set (集合)、hash (哈希) 和 zset (有序集合)
Redis 所有的数据结构都是以唯一的 key 字符串作为名称,然后通过这个唯一 key 值来获取相应的 value 数据
不同类型的数据结构的差异在于 value 的结构不一样
string (字符串)
字符串 string 是 Redis 最简单得数据结构
字符串结构使用非常广泛,一个常见的用途就是缓存用户信息
将用户信息结构体使用 JSON 序列化成字符串,然后将序列化后的字符串塞进 Redis 来缓存
取用户信息会经过一次反序列化的过程
Redis 的字符串是动态字符串,是可以修改的字符串,内部结构实现类似于 Java 的 ArrayList,采用预分配冗余空间的方式来减少内存的频繁分配,当字符串长度小于 1M 时,扩容都是加倍现有的空间,如果超过 1M,扩容时一次只会多扩容 1M 的空间
字符串是由多个字节组成,每个字节又是由 8 个 bit 组成
字符串最大长度为 512M
键值对 1 2 3 4 5 6 7 8 > set name codehole ok > get name "codehole" > exists name (integer) 1 > del name (integer) 1
批量键值对
可以批量对多个字符串进行读写,节省网络耗时开销
1 2 3 4 5 6 > mset name1 boy name2 girl name3 unknown ok > mget name1 name2 name3 1) "boy" 2) "girl" 3) "unknown"
过期时间和 set 命令扩展
可以对 key 设置过期时间,到点自动删除,这个功能常用来控制缓存的失效时间
1 2 3 > expire name 5 > setex name 5 codehole > setnx name codehole
计数
如果 value 值是一个整数,还可以对它进行自增操作
自增范围 signed long 的最大最小值
1 2 3 4 5 6 7 8 9 > set age 30ok > incr age (integer) 31 > incrby age 5 (integer) 36 > incrby age -5 (integer) 31
List (列表)
Redis 的列表相当于 Java 语言里的 LinkedList,它是链表而不是数组。意味着 list 的插入和删除操作非常快,时间复杂度为 O(1),但索引定位很慢,时间复杂度为 O(n)
当列表弹出了最后一个元素之后,该数据结构自动被删除,内存被回收
Redis 的列表结构常用来做异步队列使用;将需要延后处理的任务结构体序列化成字符串塞进 Redis 的列表,另一个线程从这个列表中轮训数据进行处理
右边进左边出:队列
1 2 3 4 5 6 > rpush books python java golang (integer) 3 > llen books (integer) 3 > lpop books "Python"
右边进右边出:栈
1 2 3 4 > rpush books python java golang (integer) 3 > rpop books "golang"
慢操作
lindex 相当于 Java 链表中的 get(int index)
方法,他需要对链表进行遍历,性能随着参数 index
增大而变差
ltrim 保留区间,它需要跟两个参数 start_index
和end_index
定义了一个区间,在这个区间的值保留,区间之外的统统砍掉。可以通过 itrim 来实现一个定长的链表
index 可以为负数,index=-1
表示倒数第一个元素
1 2 3 4 5 6 7 8 9 > rpush books python java golang > lindex books 1 "java" > lrange books 0 -1 1) "Python" 2) "java" 3) "golang" > ltrim books 1 -1 > ltrim books 1 0
快速列表
Redis 的 List 底层是由快速链表quicklist
的结构实现的
在列表元素较小的时候会使用一块连续的内存存储,这个结构是压缩列表 ziplist
它将所有的元素紧挨着一起存储。
当数据量比较大的时候会改成quicklist
,因为普通的链表需要附加指针空间太大,会比较浪费空间,而且会加重内存的碎片化。所以 Redis 将链表和ziplist
结合起来组成了quicklist
,将多个 ziplist
使用双指针串起来使用
hash(字典)
Redis 的字典相当于 Java 语言中的 HashMap,它是无序字典。内部实现结构与 Java 中的 HashMap 一样,都是使用 数组 + 链表二维结构。第一维 hash 的数组位置碰撞时,会讲碰撞的元素使用链表串接起来
不同的是 Redis 的字典的值只能是字符串,另外它们的 rehash 的方式不一样,Java 的 HashMap 在字典很大时,rehash 是个耗时的操作,需要一次性全部 rehash,而 Redis 采用了渐进式 rehash 策略
渐进式 rehash 会在 rehash 的同时,保留新旧两个 hash 结构,查询时会同时查询两个 hash 结构,然后在后续的定时任务中以及 hash 操作指令中,循序渐进地将旧 hash 的内容一点点迁移到新的 hash 结构中,当迁移完成后,就会使用新的 hash 结构取而代之
当 hash 移除了最后一个元素之后,改数据结构自动被删除,内存被回收
hash 结构的存储消耗要高于单个字符串
hash 结构中的单个子 key 也可以进行计数
1 2 3 4 5 6 7 8 > hset books java "think in java" (integer) 1 > hgetaall books > hlen books > hget books java > hset book java "effective java" > hmset books java "think in java" python "learning python" id 1 > hincrby books id 1
set (集合)
Redis 的集合相当于 Java 的 HashSet,它内部的键值对是无序的唯一的,它的内部实现相当于一个特殊的字典,字典中所有的 value 都是一个值 NULL
当集合中最后一个元素移除之后,数据结构自动删除,内存被回收
set 结构可以用来存储活动中将的用户 ID,因为有去重功能,可以保证同一用户不会中将两次
1 2 3 4 5 6 7 8 9 10 11 12 > sadd books python (integer) 1 > sadd books python (integer) 0 > sadd books java golang (integer) 2 > sismember books java (integer) 1 > scard books (integer) 3 > spop books "java"
hset (有序集合) hset 结构类似于 Java 的 SortedSet 和 HashMap 的结合体,一方面它是一个 set,保证了内部 value 的唯一性,另一方面它可以给每个 value 赋予一个 score,代表这个 value 的排序权重
hset 内部实现用的是一种叫做「跳跃列表」的数据结构
当有序集合最后一个 value 被移除后,数据结构自动删除,内存被回收
zset 可以用来存粉丝列表,value 值是粉丝的用户 ID,score 是关注时间。我们可以对粉丝列表按关注时间进行排序
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 > zadd books 9.0 "think in java" (integer) 1 > zadd books 8.9 "java concurrency" (integer) 1 > zadd books 8.6 "java cookbook" (integer) 1 > zrange books 0 -1 1) "java cookbook" 2) "java concurrency" 3) "think in java" > zrevrange books 0 -1 1) "think in java" 2) "java concurrency" 3) "java cookbook" > zcard books (integer) 3 > zscore books "java cookbook" "8.9000000000000004" ## 内部 score 使用 double 类型进行存储,所以存在小数点精度问题 > zrank books "java cookbook" > zrangebyscore books 0 8.91 > zrangebyscore books -inf 8.91 withscores > zrem books "java concurrency"
跳跃列表 zset 内部的排序功能是通过「跳跃列表」数据结构来实现的,它的结构非常特殊,也比较复杂
一个创业公司,刚开始只有几个人,团队成员之间人人平等,都是联合创始人。随着公司的成长,人数渐渐变多,团队沟通成本随之增加。这时候就会引入组长制,对团队进行划分。每个团队会有一个组长。开会的时候分团队进行,多个组长之间还会有自己的会议安排。公司规模进一步扩展,需要再增加一个层级 —— 部门,每个部门会从组长列表中推选出一个代表来作为部长。部长们之间还会有自己的高层会议安排。
跳跃列表类似于上面的层级制,最下面一层所有的元素都会串起来,然后每隔几个元素挑选出一个代表来,再将这几个代表使用另外一级指针串起来。然后在这些代表里再挑选出二级代表,再串起来。最终就形成了金字塔结构
跳跃列表之所以跳跃
,是因为内部的元素可能身兼数职
,比如上图中间的元素,同时处于 L0、L1 和 L2层,可以快速再不同层次之间进行跳跃
定位插入点时,现在顶层进行定位,然后下潜到下一层定位,一直下潜到最底层找到合适的位置,将新元素插进去
跳跃列表采取一个随机策略来决定新元素可以兼职到第几层
首先 L0 层兼职机率是 100%,L1 层只有 50% 的机率,L2 层只有 25% 的机率,L3 层只有 12.5% 机率,一直随机到最顶层 L31层
容器型数据结构的通用规则
list/set/hash/zset 这四种数据结构是容器型数据结构,它们共享下面两条通用规则:
create if not exists
如果容器不存在,那就创建一个,再进行操作。
drop if no elements
如果容器里元素没有了,那么立即删除元素,释放内存
过期时间
Redis 所有的数据结构都可以设置过期时间,时间到了,Redis 会自动删除相应的对象
过期是以对象为单位,比如一个 hash 结构的过期是整个 hash 对象的过期,而不是其中的某个子key
如果一个对象已经设置了过期时间,然后再次修改了它,那么它的过期时间会消失