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 ## 设置 5s 后自动删除
> setex name 5 codehole ## 添加数据 并设置5s后自动删除，等价于 set+expire
> setnx name codehole # 如果 name 不存在就执行 set 创建

计数

如果 value 值是一个整数，还可以对它进行自增操作

自增范围 signed long 的最大最小值

1
2
3
4
5
6
7
8
9

> set age 30
ok
> incr age ## 自增 1
(integer) 31
> incrby age 5 ## 增加 5
(integer) 36
> incrby age -5 ## 减少 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 ## 时间复杂度为 O(n) 慎用
"java"
> lrange books 0 -1 ## 获取所有的元素，时间复杂度为 O(n) 慎用
1) "Python"
2) "java"
3) "golang"
> ltrim books 1 -1  ## 时间复杂度为 O(n) 慎用 返回一个定长列表
> 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 ## 获取 books 字典中的所有数据
> hlen books ## 获取 books 的长度
> hget books java ## 查询指定 field
> hset book java "effective java" ## 相同 field 会覆盖，所以是更新操作
> 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 ## 查询某个 value 是否存在
(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 ## 按 score 顺序排序，参数区间为排列范围
1) "java cookbook"
2) "java concurrency"
3) "think in java"
> zrevrange books 0 -1 ## 按 score 倒序排列，参数区间为排列范围
1) "think in java"
2) "java concurrency"
3) "java cookbook"
> zcard books ## 获取 元素数量
(integer) 3
> zscore books "java cookbook" ## 获取指定 value 的 score
"8.9000000000000004"  ## 内部 score 使用 double 类型进行存储，所以存在小数点精度问题
> zrank books "java cookbook" ## 获取指定 value 的排名
> zrangebyscore books 0 8.91 ## 根据分值区间遍历 zset
> zrangebyscore books -inf 8.91 withscores # 根据分值区间 (-∞, 8.91] 遍历 zset，同时返回分值。inf 代表 infinite，无穷大的意思。
> zrem books "java concurrency"  # 删除 value

跳跃列表

zset 内部的排序功能是通过「跳跃列表」数据结构来实现的，它的结构非常特殊，也比较复杂

一个创业公司，刚开始只有几个人，团队成员之间人人平等，都是联合创始人。随着公司的成长，人数渐渐变多，团队沟通成本随之增加。这时候就会引入组长制，对团队进行划分。每个团队会有一个组长。开会的时候分团队进行，多个组长之间还会有自己的会议安排。公司规模进一步扩展，需要再增加一个层级 —— 部门，每个部门会从组长列表中推选出一个代表来作为部长。部长们之间还会有自己的高层会议安排。

跳跃列表类似于上面的层级制，最下面一层所有的元素都会串起来，然后每隔几个元素挑选出一个代表来，再将这几个代表使用另外一级指针串起来。然后在这些代表里再挑选出二级代表，再串起来。最终就形成了金字塔结构

跳跃列表之所以跳跃，是因为内部的元素可能身兼数职，比如上图中间的元素，同时处于 L0、L1 和 L2层，可以快速再不同层次之间进行跳跃

定位插入点时，现在顶层进行定位，然后下潜到下一层定位，一直下潜到最底层找到合适的位置，将新元素插进去

跳跃列表采取一个随机策略来决定新元素可以兼职到第几层

首先 L0 层兼职机率是 100%，L1 层只有 50% 的机率，L2 层只有 25% 的机率，L3 层只有 12.5% 机率，一直随机到最顶层 L31层

容器型数据结构的通用规则

list/set/hash/zset 这四种数据结构是容器型数据结构，它们共享下面两条通用规则：

1. create if not exists

   如果容器不存在，那就创建一个，再进行操作。

2. drop if no elements

   如果容器里元素没有了，那么立即删除元素，释放内存

过期时间

Redis 所有的数据结构都可以设置过期时间，时间到了，Redis 会自动删除相应的对象

过期是以对象为单位，比如一个 hash 结构的过期是整个 hash 对象的过期，而不是其中的某个子key

如果一个对象已经设置了过期时间，然后再次修改了它，那么它的过期时间会消失