Redis的学习_基础数据结构（二）(可能是最完善的整理)

字数统计: 4.9k字   |   阅读时长: 19分
Redis 阅读量

Redis 基础数据结构

Redis 有 5 种基础数据结构，分别为：

  • string (字符串)
  • list (列表)
  • hash (哈希)
  • set (集合)
  • zset (有序集合)

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

String (字符串)

字符串 string 是 Redis 最简单的数据结构。

字符串结构使用非常广泛，一个常见的用途就是缓存用户信息。我们将用户信息结构体使用 JSON 序列化成字符串，然后将序列化后的字符串塞进 Redis 来缓存。同样，取用户信息会经过一次反序列化的过程。

存储容量会自动扩容

Redis 的字符串是动态字符串，是可以修改的字符串，内部结构实现上类似于 Java 的 ArrayList，采用预分配冗余空间的方式来减少内存的频繁分配，如图中所示，内部为当前字符串实际分配的空间 capacity 一般要高于实际字符串长度 len。当字符串长度小于 1M 时，扩容都是加倍现有的空间，如果超过 1M，扩容时一次只会多扩 1M 的空间。需要注意的是字符串最大长度为 512M。

操作

  • 键值对

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    > set name kuanger
    OK
    > get name
    "kuanger"
    > getset name kuanger2 # 取值后再赋值
    "kuanger"
    > get name
    "kuanger2"
    > exists name
    (integer) 1
    > getrange name 0 2 # 获取字符串的[start end]的字符
    "kua"
    > del name
    (integer) 1
    > get name
    (nil)

  • 批量键值对

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    > set name1 kuanger1
    OK
    > set name2 kuanger2
    OK
    > mget name1 name2 name3 # 返回一个列表
    1) "kuanger1"
    2) "kuanger2"
    3) (nil)
    > mset name1 boy name2 girl name3 unknown
    > mget name1 name2 name3
    1) "boy"
    2) "girl"
    3) "unknown"

  • 过期和 set 命令扩展
    可以对 key 设置过期时间，到点自动删除，这个功能常用来控制缓存的失效时间。不过这个「自动删除」的机制是比较复杂的，后面会记录.

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    > set name kuanger
    > get name
    "kuanger"
    > expire name 5  # 设置5s 后过期
    (integer) 1  # 1表示设置成功，0表示变量ireader不存在
    ...  # wait for 5s
    > ttl ireader # 查看寿命
    (integer) 4  # 还有4秒的寿命，返回-2表示变量不存在，-1表示没有设置过期时间
    > get name
    (nil)

    > setex name 5 kuanger  # 5s 后过期，等价于 set+expire
    > get name
    "kuanger"
    ... # wait for 5s
    > get name
    (nil)

    > setnx name kuanger  # 如果 name 不存在就执行 set 创建
    (integer) 1
    > get name
    "kuanger"
    > setnx name hello
    (integer) 0  # 因为 name 已经存在，所以 set 创建不成功
    > get name
    "kuanger"  # 没有改变

  • 计数

如果 value 值是一个整数，还可以对它进行自增操作。自增是有范围的，它的范围是 signed long 的最大最小值，超过了这个值，Redis 会报错。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
> set age 30
OK
> incr age # 默认加一
(integer) 31
> decr ireader  # 等价于decrby ireader 1
(integer) 30
> incrby age 6
(integer) 36
> incrby age -5
(integer) 31
> set codehole 9223372036854775807  # Long.Max
OK
> incr codehole
(error) ERR increment or decrement would overflow

List(列表)


Redis 的列表相当于 Java 语言里面的 LinkedList，注意它是链表而不是数组。这意味着 list 的插入和删除操作非常快，时间复杂度为 O(1)，但是索引定位很慢，时间复杂度为 O(n)，这点让人非常意外。

当列表弹出了最后一个元素之后，该数据结构自动被删除，内存被回收。

Redis 的列表结构常用来做 异步队列 使用。将需要延后处理的任务结构体序列化成字符串塞进 Redis 的列表，另一个线程从这个列表中轮询数据进行处理。

  • 负下标 : 链表元素的位置使用自然数0,1,2,….n-1表示，还可以使用负数-1,-2,…-n来表示，-1表示「倒数第一」，-2表示「倒数第二」，那么-n就表示第一个元素，对应的下标为0。

操作

  • 队列／堆栈 : 链表可以从表头和表尾追加和移除元素，结合使用rpush/rpop/lpush/lpop四条指令，可以将链表作为队列或堆栈使用，左向右向进行都可以

  • 右边进左边出：队列

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    > rpush books python java golang
    (integer) 3
    > llen books # 使用llen指令获取链表长度
    (integer) 3
    > lpop books
    "python"
    > lpop books
    "java"
    > lpop books
    "golang"
    > lpop books
    (nil)

  • 右边进右边出：栈

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    > rpush books python java golang
    (integer) 3
    > rpop books
    "golang"
    > rpop books
    "java"
    > rpop books
    "python"
    > rpop books
    (nil)

  • 修改元素 

    1
    2
    3
    4
    5
    6
    7
    8
    > rpush ireader go java python
    (integer) 3
    > lset ireader 1 javascript # 使用lset指令在指定位置修改元素。
    OK
    > lrange ireader 0 -1
    1) "go"
    2) "javascript"
    3) "python"

  • 插入元素linsert : 使用linsert指令在列表的中间位置插入元素, 通过方向参数before/after来显示指示前置和后置插入。

    • 不过让人意想不到的是linsert指令并不是通过指定位置来插入，而是通过指定具体的值。这是因为在分布式环境下，列表的元素总是频繁变动的，意味着上一时刻计算的元素下标在下一时刻可能就不是你所期望的下标了。
      1
      2
      3
      4
      5
      6
      7
      8
      9
      > rpush ireader go java python
      (integer) 3
      > linsert ireader before java ruby
      (integer) 4
      > lrange ireader 0 -1
      1) "go"
      2) "ruby"
      3) "java"
      4) "python"

    暂时还没有在实际应用中发现插入指定的应用场景

  • 删除元素 : 列表的删除操作也不是通过指定下标来确定元素的，你需要指定删除的最大个数以及元素的值

    1
    2
    3
    4
    5
    6
    7
    > rpush ireader go java python
    (integer) 3
    > lrem ireader 1 java
    (integer) 1
    > lrange ireader 0 -1
    1) "go"
    2) "python"

  • 慢操作

    • lindex : 访问指定位置的元素, 相当于 Java 链表的 get(int index) 方法，它需要对链表进行遍历，性能随着参数index增大而变差。

    • lrange : 使用lrange指令来获取链表子元素列表，提供start和end下标参数

    • ltrim : 和字面上的含义不太一样，个人觉得它叫 lretain(保留) 更合适一些，因为 ltrim 跟的两个参数start_index和end_index定义了一个区间，在这个区间内的值，ltrim 要保留，区间之外统统砍掉。我们可以通过ltrim来实现一个定长的链表，这一点非常有用。

    • index : 可以为负数，index=-1表示倒数第一个元素，同样index=-2表示倒数第二个元素。

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      > rpush books python java golang
      (integer) 3
      > lindex books 1  # O(n) 慎用
      "java"
      > lrange books 0 -1  # 获取所有元素，O(n) 慎用
      1) "python"
      2) "java"
      3) "golang"
      > ltrim books 1 -1 # O(n) 慎用 保留[1,-1]区间的值,第一个到最后一个
      OK
      > lrange books 0 -1
      1) "java"
      2) "golang"
      > ltrim books 1 0 # 这其实是清空了整个列表，因为区间范围长度为负
      OK
      > llen books
      (integer) 0

内部结构

  • 快速列表 quicklist

  • 如果再深入一点，你会发现 Redis 底层存储的还不是一个简单的 linkedlist，而是称之为快速链表 quicklist 的一个结构。

  • 首先在列表元素较少的情况下会使用一块连续的内存存储，这个结构是 ziplist，也即是压缩列表。

  • 它将所有的元素紧挨着一起存储，分配的是一块连续的内存。 当数据量比较多的时候才会改成 quicklist。因为普通的链表需要的附加指针空间太大，会比较浪费空间，而且会加重内存的碎片化。

  • 比如这个列表里存的只是 int 类型的数据，结构上还需要两个额外的指针 prev 和 next 。所以 Redis 将链表和 ziplist 结合起来组成了 quicklist。也就是将多个 ziplist 使用双向指针串起来使用。这样既满足了快速的插入删除性能，又不会出现太大的空间冗余。>

hash (字典)

  • Redis 的字典相当于 Java 语言里面的 HashMap，它是无序字典。内部实现结构上同 Java 的 HashMap 也是一致的，同样的数组 + 链表二维结构。第一维 hash 的数组位置碰撞时，就会将碰撞的元素使用链表串接起来。

    • 结构上它使用二维结构，第一维是数组，第二维是链表，hash的内容key和value存放在链表中，数组里存放的是链表的头指针。
    • 通过key查找元素时，先计算key的hashcode，然后用hashcode对数组的长度进行取模定位到链表的表头，再对链表进行遍历获取到相应的value值，链表的作用就是用来将产生了「hash碰撞」的元素串起来。
    • 哈希的第一维数组的长度也是2^n。

  • 不同的是，Redis 的字典的值只能是字符串，另外它们 rehash 的方式不一样，因为 Java 的 HashMap 在字典很大时，rehash 是个耗时的操作，需要一次性全部 rehash。Redis 为了高性能，不能堵塞服务，所以采用了渐进式 rehash 策略。

  • 缩容 Redis的hash结构不但有扩容还有缩容，从这一点出发，它要比Java的HashMap要厉害一些，Java的HashMap只有扩容。缩容的原理和扩容是一致的，只不过新的数组大小要比旧数组小一倍

渐进式 rehash 会在 rehash 的同时，保留新旧两个 hash 结构，查询时会同时查询两个 hash 结构，然后在后续的定时任务中以及 hash 操作指令中，循序渐进地将旧 hash 的内容一点点迁移到新的 hash 结构中。当搬迁完成了，就会使用新的hash结构取而代之。

当 hash 移除了最后一个元素之后，该数据结构自动被删除，内存被回收。

hash 结构也可以用来存储用户信息，不同于字符串一次性需要全部序列化整个对象，hash 可以对用户结构中的每个字段单独存储。这样当我们需要获取用户信息时可以进行部分获取。而以整个字符串的形式去保存用户信息的话就只能一次性全部读取，这样就会比较浪费网络流量。

hash 也有缺点，hash 结构的存储消耗要高于单个字符串，到底该使用 hash 还是字符串，需要根据实际情况再三权衡。

操作

  • 插入元素

    1
    2
    3
    4
    5
    6
    7
    8
    9
    # hset key field value 
    > hset books java "think in java"  # 命令行的字符串如果包含空格，要用引号括起来
    (integer) 1
    > hset books golang "concurrency in go"
    (integer) 1
    > hset books python "python cookbook"
    (integer) 1
    > hmset books java "effective java" python "learning python" golang "modern golang programming"  # 批量 set
    OK

  • 获取元素

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    > hgetall books  # entries()，key 和 value 间隔出现
    1) "java"
    2) "think in java"
    3) "golang"
    4) "concurrency in go"
    5) "python"
    6) "python cookbook"
    > hlen books
    (integer) 3
    > hget books java
    "think in java"
    > hset books golang "learning go programming"  # 因为是更新操作，所以返回 0
    (integer) 0
    > hget books golang
    "learning go programming"

  • 删除元素

    1
    2
    3
    4
    5
    6
    > hdel books java
    (integer) 1
    > hdel books golang python
    (integer) 2
    > del books #直接删除key 包括对应的field-value
    (integer) 1

同字符串对象一样，hash 结构中的单个子 key 也可以进行计数，它对应的指令是 hincrby，和 incr 使用基本一样。

1
2
3
4
5
# 如果没有key-value 会直接创建默认加1
> hincrby user-hello age 1
(integer) 1
> hincrby user-hello age 1
(integer) 2

  • 判断元素是否存在 :
    • 通常我们使用hget获得key对应的value是否为空就直到对应的元素是否存在了，不过如果value的字符串长度特别大，通过这种方式来判断元素存在与否就略显浪费，这时可以使用hexists指令。
      1
      2
      3
      4
      > hmset ireader go fast java fast python slow
      OK
      > hexists ireader go
      (integer) 1

Set (集合)

Redis 的集合相当于 Java 语言里面的 HashSet，它内部的键值对是无序的唯一的。它的内部实现相当于一个特殊的字典，字典中所有的 value 都是一个值NULL。

当集合中最后一个元素移除之后，数据结构自动删除，内存被回收。

set 结构可以用来存储活动中奖的用户 ID，因为有去重功能，可以保证同一个用户不会中奖两次。

操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
> sadd books python
(integer) 1
> sadd books python  #  重复
(integer) 0
> sadd books java golang
(integer) 2
> smembers books  # 注意顺序，和插入的并不一致，因为 set 是无序的
1) "java"
2) "python"
3) "golang"
> sismember books java  # 查询某个 value 是否存在，相当于 contains(o) 1表示存在，0表示不存在
(integer) 1
> sismember books rust
(integer) 0
> scard books  # 获取长度相当于 count()
(integer) 3
> spop books  # 弹出一个
"java"

zset (有序集合)

zset 可能是 Redis 提供的最为特色的数据结构，它也是在面试中面试官最爱问的数据结构。它类似于 Java 的 SortedSet 和 HashMap 的结合体，一方面它是一个 set，保证了内部 value 的唯一性，另一方面它可以给每个 value 赋予一个 score，代表这个 value 的排序权重。它的内部实现用的是一种叫做「跳跃列表」的数据结构。

zset 中最后一个 value 被移除后，数据结构自动删除，内存被回收。

  • zset 可以用来存粉丝列表，value 值是粉丝的用户 ID，score 是关注时间。我们可以对粉丝列表按关注时间进行排序。

  • zset 还可以用来存储学生的成绩，value 值是学生的 ID，score 是他的考试成绩。我们可以对成绩按分数进行排序就可以得到他的名次。

操作

  • 命令：zadd key score value score value score value
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    > 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
    > zadd books 9.1 "think in java" # 如果该元素已存在则会用新的分数替换原来的分数。
    (integer) 0       # 返回0则是更新

    > zrange books 0 -1  # 按 score 排序列出，参数区间为排名范围 (从低到高) 不带score
    1) "java cookbook"
    2) "java concurrency"
    3) "think in java"
    > zrange books 0 -1 withscores # 按 score 排序列出，参数区间为排名范围 (从低到高) 带score
    1) "java cookbook"
    2) "8.6"
    3) "java concurrency"
    4) "8.9"
    5) "think in java"
    6) "9.0"

    > zrevrange books 0 -1  # 按 score 逆序列出，参数区间为排名范围 (从高到低) 不带score
    1) "think in java"
    2) "java concurrency"
    3) "java cookbook"
    > zrevrange books 0 -1 withscores # 按 score 逆序列出，参数区间为排名范围 (从高到低) 带score
    1) "think in java"
    2) "9.0"
    3) "java concurrency"
    4) "8.9"
    5) "java cookbook"
    6) "9.0"

    > zcard books  # 相当于 count()
    (integer) 3
    > zscore books "java concurrency"  # 获取指定 value 的 score
    "8.9000000000000004"  # 内部 score 使用 double 类型进行存储，所以存在小数点精度问题
    > zrank books "java concurrency"  # 排名
    (integer) 1
    > zrangebyscore books 0 8.91  # 根据分值区间遍历 zset
    1) "java cookbook"
    2) "java concurrency"
    > zrangebyscore books -inf 8.91 withscores # 根据分值区间 (-∞, 8.91] 遍历 zset，同时返回分值。inf 代表 infinite，无穷大的意思。
    1) "java cookbook"
    2) "8.5999999999999996"
    3) "java concurrency"
    4) "8.9000000000000004"
    > zrem books "java concurrency"  # 删除 value
    (integer) 1
    > zrange books 0 -1
    1) "java cookbook"
    2) "think in java"

跳跃列表

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

因为 zset 要支持随机的插入和删除，所以它不好使用数组来表示。我们先看一个普通的链表结构。

我们需要这个链表按照 score 值进行排序。这意味着当有新元素需要插入时，要定位到特定位置的插入点，这样才可以继续保证链表是有序的。通常我们会通过二分查找来找到插入点，但是二分查找的对象必须是数组，只有数组才可以支持快速位置定位，链表做不到，那该怎么办？

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

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

想想你老家在世界地图中的位置：亚洲–>中国->XX省->XX市->XX县->XX镇->XX村->xxxx号，也是这样一个类似的结构。

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

  • 定位插入点时，先在顶层进行定位，然后下潜到下一级定位，一直下潜到最底层找到合适的位置，将新元素插进去。你也许会问，那新插入的元素如何才有机会「身兼数职」呢？

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

  • 首先 L0 层肯定是 100% 了，L1 层只有 50% 的概率，L2 层只有 25% 的概率，L3 层只有 12.5% 的概率，一直随机到最顶层 L31 层。绝大多数元素都过不了几层，只有极少数元素可以深入到顶层。列表中的元素越多，能够深入的层次就越深，能进入到顶层的概率就会越大。

  • 通俗的理解就是 :

    • 需要从 header 的最高层开始遍历找到第一个
      节点 (最后一个比「我」小的元素)，然后从这个节点开始降一层再遍历找到第二个节点 (最
      后一个比「我」小的元素)，然后一直降到最底层进行遍历就找到了期望的节点 ( 最底层的最
      后一个比我「小」的元素       )。

    • 我们将中间经过的一系列节点称之为 「搜索路径」 ，它是从最高层一直到最底层的每一
      层最后一个比「我」小的元素节点列表。

    • 有了这个搜索路径，我们就可以插入这个新节点了。不过这个插入过程也不是特别简
      单。因为新插入的节点到底有多少层，得有个算法来分配一下，跳跃列表使用的是随机算
      法

参考

Copyright © 2018 - 2020 Kuanger All Rights Reserved.

访客数 : | 访问量 :