关于java:面试官有一种数据类型Redis-要存两次为什么

起源：blog.csdn.net/zwx900102/article/details/113096979

在 Redis 中，有一种数据类型，当在存储的时候会同时采纳两种数据结构来进行别离存储，那么 Redis 为什么要这么做呢？这么做会造成同一份数据占用两倍空间吗？

Redis 中的汇合对象是一个蕴含字符串类型元素的无序汇合，汇合中元素惟一不可反复。

汇合对象的底层数据结构有两种：intset 和 hashtable。外部通过编码来进行辨别：

intset（整数汇合）能够保留类型为 int16_t，int32_t，int64_t 的整数值，并且保障汇合中没有反复元素。

intset 数据结构定义如下（源码 inset.h 内）：

typedef struct intset {
    uint32_t encoding;// 编码方式
    uint32_t length;// 以后汇合中的元素数量
    int8_t contents[];// 汇合中具体的元素} intset;

下图就是一个 intset 的汇合对象存储简图：

在 intset 外部的 encoding 记录了以后整数汇合的数据存储类型，次要有三种：

INTSET_ENC_INT16

此时 contents[] 内的每个元素都是一个 int16_t 类型的整数值，范畴是：-32768 ~ 32767（-2 的 15 次方 ~ 2 的 15 次方 – 1）。

INTSET_ENC_INT32

此时 contents[] 内的每个元素都是一个 int32_t 类型的整数值，范畴是：-2147483648 ~ 2147483647（-2 的 31 次方 ~ 2 的 31 次方 – 1）。

INTSET_ENC_INT64

此时 contents[] 内的每个元素都是一个 int64_t 类型的整数值，范畴是：-9223372036854775808 ~ 9223372036854775807（-2 的 63 次方 ~ 2 的 63 次方 – 1）。

`contents[]`

contents[] 尽管构造的定义上写的是 int8_t 类型，然而理论存储类型是由下面的 encoding 来决定的。

如果一开始整数汇合中的元素都是 16 位的，采纳 int16_t 类型来存储，此时须要再存储一个 32 位的整数，那么就须要对原先的整数汇合进行降级，降级之后能力将 32 位的整数存储到整数汇合内。这就波及到了整数汇合的类型降级，降级过程次要有 4 个步骤：

依据新增加元素的类型来扩大底层数组空间的大小，依照降级后现有元素的位数来调配新的空间。
将现有的元素进行类型转换，并将转换类型后的元素从后到前一一从新放回到数组内。
将新元素放到数组的头部或者尾部（因为触发降级的条件就是以后数组的整数类型无奈存储新元素，所以新元素要么比现有元素都大，要么就比现有元素都小）。
将 encoding 属性批改为最新的编码，并且同步批改 length 属性。

PS：和字符串对象的编码一样，整数汇合的类型一旦产生降级，将会放弃编码，无奈降级。

1. 如果咱们有一个汇合存储的 encoding 是 int16_t，外部存储了 3 个元素：

2. 这时候须要插入一个整数 50000，发现存储不上来，而 50000 是一个 int32_t 类型整数，所以须要申请新空间，申请空间大小为 4 * 32 - 48=80。

3. 当初新的数组内要搁置 4 个元素，原来的数组排在第 3，所以须要将降级后的 3 挪动到 64-95 位。

4. 持续将降级后的 2 挪动到 32-63 位。

5. 持续将降级后的 1 挪动到 0-31 位。

6. 而后会将 50000 放到 96-127 位。

7. 最初会批改 encoding 和 length 属性，批改之后就实现了本次的降级。

hashtable 构造在后面讲述哈希对象的时候进行过详细分析，想具体理解的能够点击这里。

当一个汇合满足以下两个条件时，Redis 会抉择应用 intset 编码：

汇合对象保留的所有元素都是整数值。
汇合对象保留的元素数量小于等于 512 个（这个阈值能够通过配置文件 set-max-intset-entries 来管制）。

一旦汇合中的元素不满足下面两个条件，则会抉择应用 hashtable 编码。

sadd key member1 member2：将一个或多个元素 member 退出到汇合 key 当中，并返回增加胜利的数目，如果元素已存在则被疏忽。
sismember key member：判断元素 member 是否存在汇合 key 中。
srem key member1 member2：移除汇合 key 中的元素，不存在的元素会被疏忽。
smove source dest member：将元素 member 从汇合 source 中挪动到 dest 中，如果 member 不存在，则不执行任何操作。
smembers key：返回汇合 key 中所有元素。

理解了操作汇合对象的常用命令，咱们就能够来验证下后面提到的哈希对象的类型和编码了，在测试之前为了避免其余 key 值的烦扰，咱们先执行 flushall 命令清空 Redis 数据库。

顺次执行如下命令：

sadd num 1 2 3  // 设置 3 个整数的汇合，会应用 intset 编码
type num // 查看类型
object encoding num   // 查看编码

sadd name 1 2 3 test  // 设置 3 个整数和 1 个字符串的汇合，会应用 hashtable 编码
type name // 查看类型
object encoding name // 查看编码

失去如下成果：

能够看到，当设置的元素外面只有整数时，汇合应用的就是 intset 编码，当设置的元素中含有非整数时，应用的就是 hashtable 编码。

Redis 中的有序汇合和汇合的区别是有序汇合中的每个元素都会关联一个 double 类型的分数，而后依照分数从小到大的程序进行排列。换句话说，有序汇合的程序是由咱们本人设值的时候通过分数来确定的。

有序汇合对象的底层数据结构有两种：skiplist 和 ziplist。外部同样是通过编码来进行辨别：

skiplist 即跳跃表，有时候也简称为跳表。应用 skiplist 编码的有序汇合对象应用了 zset 构造来作为底层实现，而 zset 中同时蕴含了一个字典和一个跳跃表。

跳跃表是一种有序的数据结构，其次要特点是通过在每个节点中维持多个指向其余节点的指针，从而达到快速访问节点的目标。

大部分状况下，跳跃表的效率能够等同于均衡树，然而跳跃表的实现却远远比均衡树的实现简略，所以 Redis 抉择了应用跳跃表来实现有序汇合。

下图是一个一般的有序链表，咱们如果想要找到 35 这个元素，只能从头开始遍历到尾（链表中元素不反对随机拜访，所以不能用二分查找，而数组中能够通过下标随机拜访，所以二分查找个别实用于有序数组），工夫复杂度是 O(n)。

那么如果咱们能够间接跳到链表的两头，那就能够节俭很多资源了，这就是跳表的原理，如下图所示就是一个跳表的数据结构示例：

上图中 level1，level2，level3 就是跳表的层级，每一个 level 层级都有一个指向下一个雷同 level 层级元素的指针，比方上图咱们遍历寻找元素 35 的时候就有三种计划：

第 1 种就是执行 level1 层级的指针，须要遍历 7 次（1->8->9->12->15->20->35）能力找到元素 35。
第 2 种就是执行 level2 层级的指针，只须要遍历 5 次（1->9->12->15->35）就能找到元素 35。
第 3 种就是执行 level3 层级的元素，这时候只须要遍历 3 次（1->12->35）就能找到元素 35 了，大大晋升了效率。

跳跃表中的每个节点是一个 zskiplistNode 节点（源码 server.h 内）：

typedef struct zskiplistNode {
    sds ele;// 元素
    double score;// 分值
    struct zskiplistNode *backward;// 后退指针
    struct zskiplistLevel {// 层
        struct zskiplistNode *forward;// 后退指针
        unsigned long span;// 以后节点到下一个节点的跨度（逾越的节点数）} level[];} zskiplistNode;

level（层）

level 即跳跃表中的层，其是一个数组，也就是说一个节点的元素能够领有多个层，即多个指向其余节点的指针，程序能够通过不同层级的指针来抉择最快捷的门路晋升访问速度。

level 是在每次创立新节点的时候依据幂次定律（power law）随机生成的一个介于 1~32 之间的数字。

forward（后退指针）

每个层都会有一个指向链表尾部方向元素的指针，遍历元素的时候须要应用到后退指针。

span（跨度）

跨度记录了两个节点之间的间隔, 须要留神的是，如果指向了 NULL 的话，则跨度为 0。

backward（后退指针）

和后退指针不一样的是后退指针只有一个，所以每次只能后退至前一个节点（上图中没有画出后退指针）。

ele（元素）

跳跃表中元素是一个 sds 对象（晚期版本应用的是 redisObject 对象），元素必须惟一不能反复。

score（分值）

节点的分值是一个 double 类型的浮点数，跳跃表中会将节点依照分值依照从小到大的顺序排列，不同节点的分值能够反复。

下面介绍的只是跳跃表中的一个节点，多个 zskiplistNode 节点组成了一个 zskiplist 对象：

typedef struct zskiplist {
    struct zskiplistNode *header, *tail;// 跳跃表的头节点和尾结点指针
    unsigned long length;// 跳跃表的节点数
    int level;// 所有节点中最大的层数
} zskiplist;

到这里你可能认为有序汇合就是用这个 zskiplist 来实现的，然而实际上 Redis 并没有间接应用 zskiplist 来实现，而是用 zset 对象再次进行了一层包装。

typedef struct zset {
    dict *dict;// 字典对象
    zskiplist *zsl;// 跳跃表对象
} zset;

所以最终，一个有序汇合如果应用了 skiplist 编码，其数据结构如下图所示：

上图中下面一部分中的字典中的 key 就是对应了有序汇合中的元素（member），value 就对应了分值（score）。上图中上面一部分中跳跃表整数 1,8,9,12 也是对应了元素（member），最初一排的 double 型数字就是分值（score）。

也就是说字典和跳跃表中的数据都指向了咱们存储的元素（两种数据结构最终指向的是同一个地址，所以数据并不会呈现冗余存储），Redis 为什么要这么做呢？

有序汇合间接应用跳跃表或者独自应用字典齐全能够单独实现，然而咱们想一下，如果独自应用跳跃表来实现，那么尽管能够应用跨度大的指针去遍历元素来找到咱们须要的数据，然而其复杂度依然达到了 O(logN)，而字典中获取一个元素的复杂度是 O(1)，而如果独自应用字典尽管获取元素很快，然而字典是无序的，所以如果要范畴查找就须要对其进行排序，这又是一个耗时的操作，所以 Redis 综合了两种数据结构来最大水平的晋升性能，这也是 Redis 设计的精妙之处。

压缩列表在列表对象和哈希对象都有应用到，想具体理解的能够点击这里。

https://blog.csdn.net/zwx9001…

当有序汇合对象同时满足以下两个条件时，会应用 ziplist 编码进行存储：

有序汇合对象中保留的元素个数小于 128 个（能够通过配置 zset-max-ziplist-entries 批改）。
有序汇合对象中保留的所有元素的总长度小于 64 字节（能够通过配置 zset-max-ziplist-value 批改）。

zadd key score1 member1 score2 member2：将一个或多个元素（member）及其 score 增加到有序汇合 key 中。
zscore key member：返回有序汇合 key 中 member 成员的 score。
zincrby key num member：将有序汇合 key 中的 member 加上 num，num 能够为正数。
zcount key min max：返回有序汇合 key 中 score 值在 [min,max] 区间的 member 数量。
zrange key start stop：返回有序汇合 key 中 score 从小到大排列后在 [start,stop] 区间的所有 member。
zrevrange key start stop：返回有序汇合 key 中 score 从大到小排列后在 [start,stop] 区间的所有 member。
zrangebyscore key min max：返回有序汇合中按 score 从小到大排列后在 [min,max] 区间的所有元素。留神这里默认是闭区间，然而能够在 max 和 min 的数值后面加上 ( 或者 [ 来管制开闭区间。
zrevrangebyscore key max min：返回有序汇合中按 score 从大到小排列后在 [min,max] 区间的所有元素。留神这里默认是闭区间，然而能够在 max 和 min 的数值后面加上 ( 或者 [ 来管制开闭区间。
zrank key member：返回有序汇合中 member 中元素排名（从小到大），返回的后果从 0 开始计算。
zrevrank key member：返回有序汇合中 member 中元素排名（从大到小），返回的后果从 0 开始计算。
zlexcount key min max：返回有序汇合中 min 和 max 之间的 member 数量。留神这个命令中的 min 和 max 后面必须加 ( 或者 [ 来管制开闭区间，非凡值 – 和 + 别离示意负无穷和正无穷。

理解了操作有序汇合对象的常用命令，咱们就能够来验证下后面提到的哈希对象的类型和编码了，在测试之前为了避免其余 key 值的烦扰，咱们先执行 flushall 命令清空 Redis 数据库。

在执行命令之前，咱们先把配置文件中的参数 zset-max-ziplist-entries 批改为 2，而后重启 Redis 服务。

重启实现之后顺次执行如下命令：

zadd name 1 zs 2 lisi // 设置 2 个元素会应用 ziplist
type name // 查看类型
object encoding name // 查看编码

zadd address 1 beijing 2 shanghai 3 guangzhou 4 shenzhen  // 设置 4 个元素则会应用 skiplist 编码
type address  // 查看类型
object encoding address // 查看编码

失去如下成果：

本文次要剖析了汇合对象和有序汇合对象的底层存储构造 intset 和 skiplist 的实现原理，并且重点剖析了有序汇合如何实现排序以及为何同时应用两种数据结构（字典和跳表）同时进行进行存储数据的起因。

近期热文举荐：

1.1,000+ 道 Java 面试题及答案整顿 (2022 最新版)

2. 劲爆！Java 协程要来了。。。

3.Spring Boot 2.x 教程，太全了！

4. 别再写满屏的爆爆爆炸类了，试试装璜器模式，这才是优雅的形式！！

5.《Java 开发手册（嵩山版）》最新公布，速速下载！

感觉不错，别忘了顺手点赞 + 转发哦！

关于java:面试官有一种数据类型Redis-要存两次为什么

前言

五种根本类型之汇合对象

intset 编码

encoding

`contents[]`

整数汇合的降级

降级示例

hashtable 编码

intset 和 hashtable 编码转换

汇合对象常用命令

五种根本类型之有序汇合对象

skiplist 编码

跳跃表

skiplist 的存储构造

为什么同时抉择应用字典和跳跃表

ziplist 编码

ziplist 和 skiplist 编码转换

有序汇合对象常用命令

总结

Just My Socks（注册教程内含优惠码）

关于java:面试官有一种数据类型Redis-要存两次为什么

前言

五种根本类型之汇合对象

intset 编码

encoding

contents[]

整数汇合的降级

降级示例

hashtable 编码

intset 和 hashtable 编码转换

汇合对象常用命令

五种根本类型之有序汇合对象

skiplist 编码

跳跃表

skiplist 的存储构造

为什么同时抉择应用字典和跳跃表

ziplist 编码

ziplist 和 skiplist 编码转换

有序汇合对象常用命令

总结

Just My Socks（注册教程 内含优惠码）

`contents[]`

Just My Socks（注册教程内含优惠码）