数据类型及应用

https://onecompiler.com/redis可以进行实践

  • String

    • String 是最基本的 key-value 结构，key 是唯一标识，value 是具体的值

    • 数据结构实现主要是int和SDS

      • SDS 不仅可以保存文本数据，还可以保存二进制数据
        • 因为 SDS 使用 len 属性的值判断字符串是否结束
      • SDS 获取字符串长度的时间复杂度是 O(1)
        • SDS 结构里用 len 属性记录了字符串长度，所以复杂度为 O(1)
      • Redis 的 SDS API 是安全的，拼接字符串不会造成缓冲区溢出
        • SDS 在拼接字符串之前会检查 SDS 空间是否满足要求，如果空间不够会自动扩容

    • 常用指令

      # 设置 key-value 类型的值
> SET name lin
OK
# 根据 key 获得对应的 value
> GET name
"lin"
# 判断某个 key 是否存在
> EXISTS name
(integer) 1
# 返回 key 所储存的字符串值的长度
> STRLEN name
(integer) 3
# 删除某个 key 对应的值
> DEL name
(integer) 1

      批量设置 :

      # 批量设置 key-value 类型的值
> MSET key1 value1 key2 value2 
OK
# 批量获取多个 key 对应的 value
> MGET key1 key2 
1) "value1"
2) "value2"

      计数器（字符串的内容为整数的时候可以使用）：

      # 设置 key-value 类型的值
> SET number 0
OK
# 将 key 中储存的数字值增一
> INCR number
(integer) 1
# 将key中存储的数字值加 10
> INCRBY number 10
(integer) 11
# 将 key 中储存的数字值减一
> DECR number
(integer) 10
# 将key中存储的数字值键 10
> DECRBY number 10
(integer) 0

      过期（默认为永不过期）：

      # 设置 key 在 60 秒后过期（该方法是针对已经存在的key设置过期时间）
> EXPIRE name  60 
(integer) 1
# 查看数据还有多久过期
> TTL name 
(integer) 51

#设置 key-value 类型的值，并设置该key的过期时间为 60 秒
> SET key  value EX 60
OK
> SETEX key  60 value
OK

      不存在就插入：

      # 不存在就插入（not exists）
>SETNX key value
(integer) 1

    • 应用场景

      • 缓存对象

        • 直接缓存整个对象的 JSON

          SET user:1 '{"name":"xiaolin", "age":18}'。

        • 采用 key 进行分离为 user:ID:属性，采用 MSET 存储，用 MGET 获取各属性值

          MSET user:1:name xiaolin user:1:age 18 user:2:name xiaomei user:2:age 20

      • 常规计数

        Redis 处理命令是单线程，执行命令的过程是原子的。因此 String 数据类型适合计数场景，比如计算访问次数、点赞、转发、库存数量等等

        • 计算文章的阅读量：
        # 初始化文章的阅读量
> SET aritcle:readcount:1001 0
OK
#阅读量+1
> INCR aritcle:readcount:1001
(integer) 1
#阅读量+1
> INCR aritcle:readcount:1001
(integer) 2
#阅读量+1
> INCR aritcle:readcount:1001
(integer) 3
# 获取对应文章的阅读量
> GET aritcle:readcount:1001
"3"

      • 分布式锁

        SET 命令有个 NX 参数可以实现「key不存在才插入」，可以用来实现分布式锁：

        • 如果 key 不存在，则显示插入成功，可以用来表示加锁成功
        • 如果 key 存在，则会显示插入失败，可以用来表示加锁失败
        SET lock_key unique_value NX PX 10000
        • lock_key 就是 key 键
        • unique_value 是客户端生成的唯一的标识
        • NX 代表只在 lock_key 不存在时，才对 lock_key 进行设置操作
        • PX 10000 表示设置 lock_key 的过期时间为 10s，这是为了避免客户端发生异常而无法释放锁

      • 共享Session信息

        • 使用 Session 来保存用户的会话(登录)状态，这些 Session 信息会被保存在服务器端，无论请求发送到那台服务器，服务器都会去同一个 Redis 获取相关的 Session 信息

  • List

    • List 简单的字符串列表，按照插入顺序排序，可从头部或尾部向 List 列表添加元素

    • List 类型的底层数据结构是由双向链表或压缩列表实现的

      • 元素个数少使用压缩列表，元素个数多使用双向链表

    • 常用命令

      • # 将一个或多个值value插入到key列表的表头(最左边)，最后的值在最前面
LPUSH key value [value ...] 
# 将一个或多个值value插入到key列表的表尾(最右边)
RPUSH key value [value ...]
# 移除并返回key列表的头元素
LPOP key     
# 移除并返回key列表的尾元素
RPOP key 

# 返回列表key中指定区间内的元素，区间以偏移量start和stop指定，从0开始
LRANGE key start stop

# 从key列表表头弹出一个元素，没有就阻塞timeout秒，如果timeout=0则一直阻塞
BLPOP key [key ...] timeout
# 从key列表表尾弹出一个元素，没有就阻塞timeout秒，如果timeout=0则一直阻塞
BRPOP key [key ...] timeout

    • 应用场景

      • 消息队列

        存取消息时：消息保序、处理重复的消息和保证消息可靠性

        1. 如何满足消息保序需求？

          List 本身就是按先进先出的顺序对数据进行存取的，如果使用 List 作为消息队列保存消息的话，就已经能满足消息保序的需求了

          • 生产者使用 LPUSH key value[value...] 将消息插入到队列的头部，如果 key 不存在则会创建一个空的队列再插入消息。
          • 消费者使用 RPOP key 依次读取队列的消息，先进先出 Redis提供了 BRPOP 命令。BRPOP命令也称为阻塞式读取，客户端在没有读到队列数据时，自动阻塞，直到有新的数据写入队列，再开始读取新数据

        2. 如何处理重复的消息？

          • 每个消息都有一个全局的 ID
          • 消费者要记录已经处理过的消息的 ID。当收到一条消息后，消费者程序就可以对比收到的消息 ID 和记录的已处理过的消息 ID，来判断当前收到的消息有没有经过处理

        3. 如何保证消息可靠性？

          • 从 List 中读取一条消息后，List 就不会再留存这条消息了。所以，如果消费者程序在处理消息的过程出现了故障或宕机，就会导致消息没有处理完成，那么，消费者程序再次启动后，就没法再次从 List 中读取消息了
          • 为留存消息，List 类型提供 BRPOPLPUSH ，作用是让消费者程序从一个 List 中读取消息，Redis 会把这个消息再插入到另一个 List（可以叫作备份 List）留存

  • Hash

    • Hash 是一个键值对（key - value）集合，其中 value 的形式如： value=[{field1，value1}，...{fieldN，valueN}]。Hash 特别适合用于存储对象

    • 实现：

      • 元素个数少使用压缩列表，元素个数多使用哈希表

    • 常用命令

      • # 存储一个哈希表key的键值
HSET key field value   
# 获取哈希表key对应的field键值
HGET key field

# 在一个哈希表key中存储多个键值对
HMSET key field value [field value...] 
# 批量获取哈希表key中多个field键值
HMGET key field [field ...]       
# 删除哈希表key中的field键值
HDEL key field [field ...]    

# 返回哈希表key中field的数量
HLEN key       
# 返回哈希表key中所有的键值
HGETALL key 

# 为哈希表key中field键的值加上增量n
HINCRBY key field n

    • 应用场景

      • 缓存对象

        Hash 类型的 （key，field， value） 的结构与对象的（对象id， 属性， 值）的结构相似，也可以用来存储对象

        # 存储一个哈希表uid:1的键值
> HMSET uid:1 name Tom age 15
2
# 存储一个哈希表uid:2的键值
> HMSET uid:2 name Jerry age 13
2
# 获取哈希表用户id为1中所有的键值
> HGETALL uid:1
1) "name"
2) "Tom"
3) "age"
4) "15"

      • 购物车

        用户 id 为 key，商品 id 为 field，商品数量为 value，恰好构成了购物车的3要素

        • 添加商品：HSET cart:{用户id} {商品id} 1
        • 添加数量：HINCRBY cart:{用户id} {商品id} 1
        • 商品总数：HLEN cart:{用户id}
        • 删除商品：HDEL cart:{用户id} {商品id}
        • 获取购物车所有商品：HGETALL cart:{用户id}

  • Set

    • 一个无序并唯一的键值集合，它的存储顺序不会按照插入的先后顺序进行存储

    • 特性：无序、不可重复

    • 内部实现

      • 元素个数少使用整数集合，元素个数多使用哈希表

    • 常用命令

      • # 往集合key中存入元素，元素存在则忽略，若key不存在则新建
SADD key member [member ...]
# 从集合key中删除元素
SREM key member [member ...] 
# 获取集合key中所有元素
SMEMBERS key
# 获取集合key中的元素个数
SCARD key

# 判断member元素是否存在于集合key中
SISMEMBER key member

# 从集合key中随机选出count个元素，元素不从key中删除
SRANDMEMBER key [count]
# 从集合key中随机选出count个元素，元素从key中删除
SPOP key [count]

      • Set运算操作

        # 交集运算
SINTER key [key ...]
# 将交集结果存入新集合destination中
SINTERSTORE destination key [key ...]

# 并集运算
SUNION key [key ...]
# 将并集结果存入新集合destination中
SUNIONSTORE destination key [key ...]

# 差集运算
SDIFF key [key ...]
# 将差集结果存入新集合destination中
SDIFFSTORE destination key [key ...]

    • 应用场景

      • 点赞

        Set 类型可以保证一个用户只能点一个赞。场景：key 是文章id，value 是用户id

        uid:1 、uid:2、uid:3 三个用户分别对 article:1 文章点赞了。

        # uid:1 用户对文章 article:1 点赞
> SADD article:1 uid:1
(integer) 1
# uid:2 用户对文章 article:1 点赞
> SADD article:1 uid:2
(integer) 1
# uid:3 用户对文章 article:1 点赞
> SADD article:1 uid:3
(integer) 1

        uid:1 取消了对 article:1 文章点赞。

        > SREM article:1 uid:1
(integer) 1

        获取 article:1 文章所有点赞用户 :

        > SMEMBERS article:1
1) "uid:3"
2) "uid:2"

        获取 article:1 文章的点赞用户数量：

        > SCARD article:1
(integer) 2

        判断用户 uid:1 是否对文章 article:1 点赞了：

        > SISMEMBER article:1 uid:1
(integer) 0  # 返回0说明没点赞，返回1则说明点赞了

      • 共同关注

        Set 类型支持交集运算，key 可以是用户id，value 则是已关注的公众号的id

        uid:1 用户关注公众号 id 为 5、6、7、8、9

        uid:2 用户关注公众号 id 为 7、8、9、10、11。

        # uid:1 用户关注公众号 id 为 5、6、7、8、9
> SADD uid:1 5 6 7 8 9
(integer) 5
# uid:2  用户关注公众号 id 为 7、8、9、10、11
> SADD uid:2 7 8 9 10 11
(integer) 5
        • uid:1 和 uid:2 共同关注的公众号：
        # 获取共同关注
> SINTER uid:1 uid:2
1) "7"
2) "8"
3) "9"
        • 给 uid:2 推荐 uid:1 关注的公众号：
        > SDIFF uid:1 uid:2
1) "5"
2) "6"
        • 验证某个公众号是否同时被 uid:1 或 uid:2 关注:
        > SISMEMBER uid:1 5
(integer) 1 # 返回0，说明关注了
> SISMEMBER uid:2 5
(integer) 0 # 返回0，说明没关注

      • 抽奖文化

        • 存储某活动中中奖的用户名

          • 如果允许重复中奖，可以使用 SRANDMEMBER 命令。
          # 抽取 1 个一等奖：
> SRANDMEMBER lucky 1
1) "Tom"
# 抽取 2 个二等奖：
> SRANDMEMBER lucky 2
1) "Mark"
2) "Jerry"
# 抽取 3 个三等奖：
> SRANDMEMBER lucky 3
1) "Sary"
2) "Tom"
3) "Jerry"
          • 如果不允许重复中奖，可以使用 SPOP 命令。
          # 抽取一等奖1个
> SPOP lucky 1
1) "Sary"
# 抽取二等奖2个
> SPOP lucky 2
1) "Jerry"
2) "Mark"
# 抽取三等奖3个
> SPOP lucky 3
1) "John"
2) "Sean"
3) "Lindy"

  • Zset

    • Zset 类型（有序集合类型）相比于 Set 类型多了一个排序属性 score（分值） 对于有序集合 ZSet 来说，每个存储元素相当于有两个值组成的，一个是有序集合的元素值，一个是排序值

    • 内部实现

      • 元素个数少使用压缩列表，元素个数多使用跳表

    • 常用命令

      • # 往有序集合key中加入带分值元素
ZADD key score member [[score member]...]   
# 往有序集合key中删除元素
ZREM key member [member...]                 
# 返回有序集合key中元素member的分值
ZSCORE key member
# 返回有序集合key中元素个数
ZCARD key 

# 为有序集合key中元素member的分值加上increment
ZINCRBY key increment member 

# 正序获取有序集合key从start下标到stop下标的元素
ZRANGE key start stop [WITHSCORES]
# 倒序获取有序集合key从start下标到stop下标的元素
ZREVRANGE key start stop [WITHSCORES]

# 返回有序集合中指定分数区间内的成员，分数由低到高排序。
ZRANGEBYSCORE key min max [WITHSCORES] [LIMIT offset count]

# 返回指定成员区间内的成员，按字典正序排列, 分数必须相同。
ZRANGEBYLEX key min max [LIMIT offset count]
# 返回指定成员区间内的成员，按字典倒序排列, 分数必须相同
ZREVRANGEBYLEX key max min [LIMIT offset count]

        Zset 运算操作（相比于 Set 类型，ZSet 类型没有支持差集运算）：

        # 并集计算(相同元素分值相加)，numberkeys一共多少个key，WEIGHTS每个key对应的分值乘积
ZUNIONSTORE destkey numberkeys key [key...] 
# 交集计算(相同元素分值相加)，numberkeys一共多少个key，WEIGHTS每个key对应的分值乘积
ZINTERSTORE destkey numberkeys key [key...]

    • 应用场景

      • 排行榜

        我们以博文点赞排名为例，小小发表了五篇博文，分别获得赞为 200、40、100、50、150。

        # arcticle:1 文章获得了200个赞
> ZADD user:xiaoxiao:ranking 200 arcticle:1
(integer) 1
# arcticle:2 文章获得了40个赞
> ZADD user:xiaoxiao:ranking 40 arcticle:2
(integer) 1
# arcticle:3 文章获得了100个赞
> ZADD user:xiaoxiao:ranking 100 arcticle:3
(integer) 1
# arcticle:4 文章获得了50个赞
> ZADD user:xiaoxiao:ranking 50 arcticle:4
(integer) 1
# arcticle:5 文章获得了150个赞
> ZADD user:xiaoxiao:ranking 150 arcticle:5
(integer) 1

        文章 arcticle:4 新增一个赞，可以使用 ZINCRBY 命令

        > ZINCRBY user:xiaoxiao:ranking 1 arcticle:4
"51"

        查看某篇文章的赞数，可以使用 ZSCORE 命令（返回有序集合key中元素个数）：

        > ZSCORE user:xiaoxiao:ranking arcticle:4
"50"

        获取小林文章赞数最多的 3 篇文章，可以使用 ZREVRANGE 命令（倒序获取有序集合 key 从start下标到stop下标的元素）：

        # WITHSCORES 表示把 score 也显示出来
> ZREVRANGE user:xiaoxiao:ranking 0 2 WITHSCORES
1) "arcticle:1"
2) "200"
3) "arcticle:5"
4) "150"
5) "arcticle:3"
6) "100"

        获取小林 100 赞到 200 赞的文章，可以使用 ZRANGEBYSCORE 命令（返回有序集合中指定分数区间内的成员，分数由低到高排序）：

        > ZRANGEBYSCORE user:xiaoxiao:ranking 100 200 WITHSCORES
1) "arcticle:3"
2) "100"
3) "arcticle:5"
4) "150"
5) "arcticle:1"
6) "200"

      • 电话,姓名排序

        使用有序集合的 ZRANGEBYLEX 或 ZREVRANGEBYLEX 可以帮助我们实现电话号码或姓名的排序

        不要在分数不一致的 SortSet 集合中去使用 ZRANGEBYLEX和 ZREVRANGEBYLEX 指令

        1、电话排序

        将电话号码存储到 SortSet 中，然后根据需要来获取号段：

        > ZADD phone 0 13100111100 0 13110114300 0 13132110901 
(integer) 3
> ZADD phone 0 13200111100 0 13210414300 0 13252110901 
(integer) 3
> ZADD phone 0 13300111100 0 13310414300 0 13352110901 
(integer) 3

        获取所有号码:

        > ZRANGEBYLEX phone - +
1) "13100111100"
2) "13110114300"
3) "13132110901"
4) "13200111100"
5) "13210414300"
6) "13252110901"
7) "13300111100"
8) "13310414300"
9) "13352110901"

        获取 132 号段的号码：

        > ZRANGEBYLEX phone [132 (133
1) "13200111100"
2) "13210414300"
3) "13252110901"

        获取132、133号段的号码：

        > ZRANGEBYLEX phone [132 (134
1) "13200111100"
2) "13210414300"
3) "13252110901"
4) "13300111100"
5) "13310414300"
6) "13352110901"

        2、姓名排序

        > zadd names 0 Toumas 0 Jake 0 Bluetuo 0 Gaodeng 0 Aimini 0 Aidehua 
(integer) 6

        获取所有人的名字:

        > ZRANGEBYLEX names - +
1) "Aidehua"
2) "Aimini"
3) "Bluetuo"
4) "Gaodeng"
5) "Jake"
6) "Toumas"

        获取名字中大写字母A开头的所有人：

        > ZRANGEBYLEX names [A (B
1) "Aidehua"
2) "Aimini"

        获取名字中大写字母 C 到 Z 的所有人：

        > ZRANGEBYLEX names [C [Z
1) "Gaodeng"
2) "Jake"
3) "Toumas"

  • BitMap

    • Bitmap，位图，是一串连续的二进制数组（0和1），可通过偏移量（offset）定位元素

    • 特别适合一些数据量大且使用二值统计的场景

    • 内部实现

      • Bitmap 本身是String 类型作为底层数据结构实现的一种统计二值状态的数据类型

    • 常用命令

      # 设置值，其中value只能是 0 和 1
SETBIT key offset value

# 获取值
GETBIT key offset

# 获取指定范围内值为 1 的个数
# start 和 end 以字节为单位
BITCOUNT key start end
      • bitmap 运算操作：
      # BitMap间的运算
# operations 位移操作符，枚举值
  AND 与运算 &
  OR 或运算 |
  XOR 异或 ^
  NOT 取反 ~
# result 计算的结果，会存储在该key中
# key1 … keyn 参与运算的key，可以有多个，空格分割，not运算只能一个key
# 当 BITOP 处理不同长度的字符串时，较短的那个字符串所缺少的部分会被看作 0。返回值是保存到 destkey 的字符串的长度（以字节byte为单位），和输入 key 中最长的字符串长度相等。
BITOP [operations] [result] [key1] [keyn…]

# 返回指定key中第一次出现指定value(0/1)的位置
BITPOS [key] [value]

    • 应用场景

      • 签到统计

        用记录签到（1）或未签到（0）就是非常典型的二值状态

        统计 ID 100 的用户在 2022 年 6 月份的签到情况，可以按照下面步骤进行操作。

        1. 执行下面的命令，记录该用户 6 月 3 号已签到。
        SETBIT uid:sign:100:202206 2 1
        1. 检查该用户 6 月 3 日是否签到。
        GETBIT uid:sign:100:202206 2
        1. 统计该用户在 6 月份的签到次数。
        BITCOUNT uid:sign:100:202206

数据结构

  • 在 Redis 3.0 版本中 List 对象的底层数据结构由「双向链表」或「压缩表列表」实现，但是在 3.2 版本之后，List 数据类型底层数据结构是由 quicklist 实现的；
  • 核心：双向链表变为quicklist，压缩列表变为listpack

  • SDS

    • C语言字符串缺陷：

      • 获取字符串长度的时间复杂度为 O（N）；
      • 字符串结尾以 “\0” 字符标识，字符串里面不能包含 “\0” 字符，不能保存二进制数据；
      • 字符串操作函数不高效且不安全，比如有缓冲区溢出的风险，有可能会造成程序运行终止

    • SDS结构设计

      • len，记录了字符串长度。时间复杂度只需要 O（1）

      • alloc，分配给字符数组的空间长度。这样在修改字符串的时候，可以通过 alloc - len 计算出剩余的空间大小，可以用来判断空间是否满足修改需求

      • flags，用来表示不同类型的 SDS。一共设计了 5 种类型，分别是 sdshdr5、sdshdr8、sdshdr16、sdshdr32 和 sdshdr64，后面在说明区别之处。

      • buf[]，字节数组，用来保存实际数据。不仅可以保存字符串，也可以保存二进制数据

        SDS 扩容的规则代码如下：

        hisds hi_sdsMakeRoomFor(hisds s, size_t addlen)
{
    ... ...
    // s目前的剩余空间已足够，无需扩展，直接返回
    if (avail >= addlen)
        return s;
    //获取目前s的长度
    len = hi_sdslen(s);
    sh = (char *)s - hi_sdsHdrSize(oldtype);
    //扩展之后 s 至少需要的长度
    newlen = (len + addlen);
    //根据新长度，为s分配新空间所需要的大小
    if (newlen < HI_SDS_MAX_PREALLOC)
        //新长度<HI_SDS_MAX_PREALLOC 则分配所需空间*2的空间
        newlen *= 2;
    else
        //否则，分配长度为目前长度+1MB
        newlen += HI_SDS_MAX_PREALLOC;
       ...
}
        • 如果所需的 sds 长度小于 1 MB，那么最后的扩容是按照翻倍扩容来执行的，即 2 倍的newlen
        • 如果所需的 sds 长度超过 1 MB，那么最后的扩容长度应该是 newlen + 1MB

  • 链表

链表结构

typedef struct list {
    //链表头节点
    listNode *head;
    //链表尾节点
    listNode *tail;
    //节点值复制函数
    void *(*dup)(void *ptr);
    //节点值释放函数
    void (*free)(void *ptr);
    //节点值比较函数
    int (*match)(void *ptr, void *key);
    //链表节点数量
    unsigned long len;
} list;

  • 优缺点

    • 优点：
      • listNode 链表节点的结构里带有 prev 和 next 指针，获取某个节点的前置节点或后置节点的时间复杂度只需O(1)，而且这两个指针都可以指向 NULL，所以链表是无环链表；
      • list 结构因为提供了表头指针 head 和表尾节点 tail，所以获取链表的表头节点和表尾节点的时间复杂度只需O(1)；
      • list 结构因为提供了链表节点数量 len，所以获取链表中的节点数量的时间复杂度只需O(1)；
      • listNode 链表节使用 void* 指针保存节点值，并且可以通过 list 结构的 dup、free、match 函数指针为节点设置该节点类型特定的函数，因此链表节点可以保存各种不同类型的值；
    • 缺点：
      • 链表每个节点之间内存都是不连续，无法很好利用 CPU 缓存。
      • 保存一个链表节点的值都需要一个链表节点结构头的分配，内存开销较大

  • 压缩列表

    • 设计成一种内存紧凑型的数据结构，占用一块连续的内存空间，不仅可以利用 CPU 缓存，而且会针对不同长度的数据，进行相应编码，这种方法可以有效地节省内存开销
    • 缺陷
      • 不能保存过多的元素，否则查询效率就会降低
      • 新增或修改某个元素时，压缩列表占用的内存空间需要重新分配，甚至可能引发连锁更新的问题
    • 结构设计
      • 压缩列表 Redis 为了节约内存而开发的，由连续内存块组成的顺序型数据结构
      • 压缩列表在表头有三个字段：
        • zlbytes，记录整个压缩列表占用对内存字节数；
        • zltail，记录压缩列表「尾部」节点距离起始地址由多少字节，也就是列表尾的偏移量；
        • zllen，记录压缩列表包含的节点数量；
        • zlend，标记压缩列表的结束点，固定值 0xFF（十进制255）
      • 压缩列表中，如果要查找定位第一个元素和最后一个元素，可通过表头三个字段（zllen）的长度直接定位，复杂度是 O(1)。查找其他元素时，就没有这么高效了，只能逐个查找，此时的复杂度就是 O(N) 了，因此压缩列表不适合保存过多的元素
      • 压缩列表节点包含三部分内容：
        • prevlen：记录了「前一个节点」的长度，目的是为了实现从后向前遍历
        • encoding：记录了当前节点实际数据的「类型和长度」，类型主要有两种：字符串和整数
        • data：记录了当前节点的实际数据，类型和长度都由 encoding 决定
      • 压缩列表里的每个节点中的 prevlen 属性都记录了「前一个节点的长度」，而且 prevlen 属性的空间大小跟前一个节点长度值有关
        • 前一个节点的长度小于 254 字节，那么 prevlen 属性需要用 1 字节的空间来保存这个长度值
        • 前一个节点的长度大于等于 254 字节，那么 prevlen 属性需要用 5 字节的空间来保存这个长度值
    • 连锁更新
      • 压缩列表新增某个元素或修改某个元素时，如果空间不不够，压缩列表占用的内存空间就需要重新分配。而当新插入的元素较大时，可能会导致后续元素的 prevlen 占用空间都发生变化，从而引起「连锁更新」问题，导致每个元素的空间都要重新分配，造成访问压缩列表性能的下降
    • 缺陷：
      • 空间扩展操作也就是重新分配内存，因此连锁更新一旦发生，就会导致压缩列表占用的内存空间要多次重新分配，这就会直接影响到压缩列表的访问性能
      • 虽然压缩列表紧凑型的内存布局能节省内存开销，但是如果保存的元素数量增加了，或是元素变大了，会导致内存重新分配，最糟糕的是会有「连锁更新」的问题

  • 哈希表

    • 一种保存键值对（key-value）的数据结构 当一个键值对的键经过 Hash 函数计算后得到哈希值，再将(哈希值 % 哈希表大小)取模计算，得到的结果值就是该 key-value 对应的数组元素位置，也就是第几个哈希桶

    • 哈希冲突：

      当有两个以上数量的 kay 被分配到了哈希表中同一个哈希桶上时，此时称这些 key 发生了冲突

    • 链式哈希：

      每个哈希表节点都有一个 next 指针，用于指向下一个哈希表节点，因此多个哈希表节点可以用 next 指针构成一个单项链表，被分配到同一个哈希桶上的多个节点可以用这个单项链表连接起来

      链式哈希局限性也很明显，随着链表长度的增加，在查询这一位置上的数据的耗时就会增加，毕竟链表的查询的时间复杂度是 O(n)

    • rehash

      • Redis 定义一个 dict 结构体，这个结构体里定义了两个哈希表（ht[2]）。

        typedef struct dict {
    …
    //两个Hash表，交替使用，用于rehash操作
    dictht ht[2]; 
    …
} dict;

      • 随着数据逐步增多，触发了 rehash 操作，这个过程分为三步：

        • 给「哈希表 2」 分配空间，一般会比「哈希表 1」 大一倍（两倍的意思）；
        • 将「哈希表 1 」的数据迁移到「哈希表 2」 中
          • 「哈希表 1 」的数据量非常大，那迁移至「哈希表 2 」时，会涉及大量的数据拷贝，可能会对 Redis 造成阻塞，无法服务其他请求
        • 迁移完成后，「哈希表 1 」的空间会被释放，并把「哈希表 2」 设置为「哈希表 1」，然后在「哈希表 2」 新创建一个空白的哈希表，为下次 rehash 做准备

      • 渐进式rehash

        为避免 rehash 在数据迁移过程中，拷贝数据的耗时，采用渐进式 rehash

        把一次性大量数据迁移工作的开销，分摊到了多次处理请求的过程中，避免了一次性 rehash 的耗时操作

        • 步骤如下：
          • 给「哈希表 2」 分配空间
          • rehash 进行期间，每次哈希表元素进行新增、删除、查找或者更新操作时，Redis 除了会执行对应的操作之外，还会顺序将「哈希表 1 」中索引位置上的所有 key-value 迁移到「哈希表 2」 上
          • 随着处理客户端发起的哈希表操作请求数量越多，最终在某个时间点会把「哈希表 1 」的所有 key-value 迁移到「哈希表 2」，从而完成 rehash 操作

  • 整数集合

    • 整数集合是 Set 对象的底层实现之一，整数集合本质是一块连续内存空间

    • 结构设计：

      typedef struct intset {
    //编码方式
    uint32_t encoding;
    //集合包含的元素数量
    uint32_t length;
    //保存元素的数组
    int8_t contents[];
} intset;

    • 升级过程：

      • 当我们将一个新元素加入到整数集合里面，如果新元素的类型（int32_t）比整数集合现有所有元素的类型（int16_t）都要长时，整数集合需要先进行升级，然后才能将新元素加入到整数集合里，当然升级的过程中，也要维持整数集合的有序性
      • 整数集合升级的过程不会重新分配一个新类型的数组，而是在原本的数组上扩展空间，然后在将每个元素按间隔类型大小分割

    • 不支持降级操作，一旦对数组进行了升级，就会一直保持升级后的状态

  • 跳表

    • ZSET（有序集合）通常由跳表和哈希表两种数据结构组成：

      1. 跳表（Skip List）：
        • 用于维护元素的顺序，支持高效的范围查询（如ZRANGE、ZRANK等操作）。
        • 跳表通过多层索引实现近似O(log N)的查找、插入和删除性能。
      2. 哈希表（Hash Table）：
        • 用于存储元素到分数的映射，支持O(1)时间复杂度的分数查找（如ZSCORE操作）。
        • 哈希表通过键值对快速定位元素。

    • zset 结构体里有两个数据结构：一个是跳表，一个是哈希表。

      • 好处：既能进行高效的范围查询，也能进行高效单点查询。
      typedef struct zset {
    dict *dict;
    zskiplist *zsl;
} zset;

    • 结构设计

      • 链表查找元素的时候，需要逐一查找，所以查询效率非常低，时间复杂度是O(N) 跳表是在链表基础上改进过来的，实现了一种「多层」的有序链表

      • 「跳表节点」数据结构：

        typedef struct zskiplistNode {
    //Zset 对象的元素值
    sds ele;
    //元素权重值
    double score;
    //后向指针
    struct zskiplistNode *backward;

    //节点的level数组，保存每层上的前向指针和跨度
    struct zskiplistLevel {
        struct zskiplistNode *forward;
        unsigned long span;
    } level[];
} zskiplistNode;

        「跳表」结构体：

        typedef struct zskiplist {
    struct zskiplistNode *header, *tail;
    unsigned long length;
    int level;
} zskiplist;
        • 跳表的头尾节点，便于在O(1)时间复杂度内访问跳表的头节点和尾节点；
        • 跳表的长度，便于在O(1)时间复杂度获取跳表节点的数量；
        • 跳表的最大层数，便于在O(1)时间复杂度获取跳表中层高最大的那个节点的层数量

    • 跳表节点查询过程

      • 查找一个跳表节点的过程时，跳表会从头节点的最高层开始，逐一遍历每一层
      • 用跳表节点中的 SDS 类型的元素和元素的权重来进行判断
        • 如果当前节点的权重「小于」要查找的权重时，跳表就会访问该层上的下一个节点
        • 如果当前节点的权重「等于」要查找的权重时，并且当前节点的 SDS 类型数据「小于」要查找的数据时，跳表就会访问该层上的下一个节点
      • 上面两个条件都不满足，跳表就会使用目前遍历到的节点的 level 数组里的下一层指针，然后沿着下一层指针继续查找

    • 跳表节点层数设置

      • 跳表在创建节点时候，会生成范围为[0-1]的一个随机数，如果这个随机数小于 0.25（相当于概率 25%），那么层数就增加 1 层，然后继续生成下一个随机数，直到随机数的结果大于 0.25 结束，最终确定该节点的层数

    • 为什么使用跳表而不是平衡树

      • 从内存占用上来比较，跳表比平衡树更灵活一些。
      • 在做范围查找的时候，跳表比平衡树操作要简单。
      • 从算法实现难度上来比较，跳表比平衡树要简单得多。