同一份数据,Redis为什么要存两次 (2)

集合对象保存的元素数量小于等于 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 //查看编码

得到如下效果:

同一份数据,Redis为什么要存两次

可以看到,当设置的元素里面只有整数时,集合使用的就是 intset 编码,当设置的元素中含有非整数时,使用的就是 hashtable 编码。

五种基本类型之有序集合对象

Redis 中的有序集合和集合的区别是有序集合中的每个元素都会关联一个 double 类型的分数,然后按照分数从小到大的顺序进行排列。换句话说,有序集合的顺序是由我们自己设值的时候通过分数来确定的。

有序集合对象的底层数据结构有两种:skiplist 和 ziplist。内部同样是通过编码来进行区分:

编码属性 描述 object encoding命令返回值
OBJ_ENCODING_SKIPLIST   使用跳跃表实现的有序集合对象   skiplist  
OBJ_ENCODING_ZIPLIST   使用压缩列表实现的有序集合对象   ziplist  
skiplist 编码

skiplist 即跳跃表,有时候也简称为跳表。使用 skiplist 编码的有序集合对象使用了 zset 结构来作为底层实现,而zset 中同时包含了一个字典和一个跳跃表。

跳跃表

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

大部分情况下,跳跃表的效率可以等同于平衡树,但是跳跃表的实现却远远比平衡树的实现简单,所以 Redis 选择了使用跳跃表来实现有序集合。

下图是一个普通的有序链表,我们如果想要找到 35 这个元素,只能从头开始遍历到尾(链表中元素不支持随机访问,所以不能用二分查找,而数组中可以通过下标随机访问,所以二分查找一般适用于有序数组),时间复杂度是 O(n)。

同一份数据,Redis为什么要存两次

那么假如我们可以直接跳到链表的中间,那就可以节省很多资源了,这就是跳表的原理,如下图所示就是一个跳表的数据结构示例:

同一份数据,Redis为什么要存两次

上图中 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 了,大大提升了效率。

skiplist 的存储结构

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/wssdxp.html