《Redis设计与实现》读书笔记(九) ——Redis集合和有序集合实现原理

《Redis设计与实现》读书笔记(九) ——Redis集合和有序集合实现原理

(原创内容,转载请注明来源,谢谢)

一、集合

集合的编码方式有intset和hashtable两种。

1、intset

intset是整数集合,集合使用此方式时,集合内的所有对象都保存在整数集合中。如下图所示:

2、hashtable

hashtable是字典,集合使用此方式时,集合内的所有对象都保存在字典的键中,值设置成null。每个对象保存在一个键中。

如下图所示:

3、编码实现条件

由于整数集合的效率比字典高,但是整数集合有一定的要求,如下:

1)集合内所有的元素必须是整数。

2)集合内元素个数不超过512个,512个这个数字是通过redis配置文件中的set-max-intset-entries属性进行配置的,默认是512个。

不满足以上两个任意条件的集合,则采用hashtable进行编码。

原先采用intset的集合,操作期间加入非整数或者元素个数超过512个,则redis会将其转换为hashtable编码方式。

4、集合命令实现

二、有序集合

有序集合的编码有ziplist和skiplist两种。

1、ziplist

ziplist是压缩列表,有序集合的每个集合元素使用两个连续的节点保存,前者保存节点具体内容,后者保存节点的score。

在压缩列表内,按照分数从小到大进行排序,分值较小的靠近表头,分值大的靠近表尾。

总体结构如下图所示:

压缩列表内部如下图所示:

2、skiplist

skiplist是跳跃表,redis中该结构专门为有序集合设计的,其他数据类型没有使用到该数据结构。

有序集合使用skiplist时,同时使用到字典。结构如下:

typedef structzset{
zskiplist *zsl;
dict *dict;
}zset;

总结构图如下:

1)跳跃表zsl

有序集合中,zsl按照分值从小到大保存集合所有元素,每个跳跃表节点都保存一个集合的元素:跳跃表节点的object属性保存了有序集合的成员,而score属性保存了有序集合的score。

通过zsl,可以对有序集合进行一些范围操作,包括zrank、zrange等命令就是基于跳跃表的api实现。

2)字典dict

除此之外,dict为有序集合创建了一个从成员到分值的映射,字典里面每个键值对都保存一个集合元素,键保存有序集合的成员,值保存有序集合的score。

通过dict,可以用O(1)的时间复杂度,通过成员找到分值。zscore和其他很多有序集合命令,都是通过集合的api实现。

内部编码结构如下图:

上图中值和分数写了两遍,是为了便于展示。实际上值和分数在skiplist和hashtable都是共享的,通过指针指向,而不是两个值。

3、有序集合skiplist+hashtable编码综述

有序集合每个成员是字符串对象,而分值是浮点数。

虽然有序集合同时使用了跳跃表和字典,但是这两个结构会通过指针的方式,共享有序集合的成员和分值,因此并不会浪费太多的内存空间。

虽然skiplist和hashtable都可以表示有序集合,但是结合在一起使用效率更高。hashtable的特性使得通过成员查找分值的速度极快,O(1);skiplist的特性使得有序集合的成员可以按照顺序排列,在执行范围型操作(如zrange、zrank等)时速度更快。

4、编码使用条件

当元素较少、长度较短时,使用ziplist效率显然更高,而且结构更简单。但是当元素太多、长度太长,使用ziplist的效率就不够高。使用ziplist,需要同时满足以下条件:

1)有序集合元素个数小于128个,通过配置文件的zset-max-ziplist-entries属性配置,默认是128个。

2)有序集合中的所有元素成员长度都小于64字节,通过配置文件的zset-max-ziplist-value属性配置,默认是64字节。

上述任一条件不满足,就会采用skiplist+hashtable的方式对有序集合进行编码。

5、有序集合命令的实现

——written by linhxx 2017.09.01

原文发布于微信公众号 - 决胜机器学习(phpthinker)

原文发表时间:2017-09-01

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏逆向技术

逆向知识第十四讲,(C语言完结)结构体在汇编中的表现形式

              逆向知识第十四讲,(C语言完结)结构体在汇编中的表现形式 一丶了解什么是结构体,以及计算结构体成员的对其值以及总大小(类也是这样算)...

17910
来自专栏北京马哥教育

Linux Shell 流程控制语句实例

linux shell 有一套自己的流程控制语句,其中包括条件语句(if),循环语句(for,while),选择语句(case)。下面我将通过例子介绍下,各个...

3497
来自专栏mathor

Dancing Links算法

 Dancing Links算法主要用于解决精确覆盖问题,精确覆盖问题就的定义:给定一个由0-1组成的矩阵,是否能找到一个行的集合,使得每个集合中每一列恰好只包...

412
来自专栏CDA数据分析师

工具 | Python集合使用详解

我会在这篇文章介绍Python几种类型的集合。 在开始前,先定义集合是什么。一个集合就像篮子,你可以放进和取出东西,可以是同一类的东西,也可以是不同类的。基本上...

1855
来自专栏日常分享

Java 将两个有序数组合成为一个有序数组

   (2)将 两个数组 对应索引下的元素进行比较,小的一方 放入最终数组中的当前索引下的位置,并使小的一方数组的索引+1;

741
来自专栏Deep learning进阶路

C++随记(六)---函数处理数组的一些问题

C++随机(六)---函数处理数组的一些问题 本篇讨论数组做函数形参的情况。 通常,我们按照以往设置形参的习惯,可能会对数组形参做如下的书写: int exa...

1660
来自专栏CodingBlock

正则表达式(一)

  正则表达式是一种强大而灵活的文本处理工具。使用正则表达式,我们能够以编程的方式,构造复杂的文本模式,并对输入的字符串进行搜索。找到匹配这些模式的部分就可以对...

17910
来自专栏进击的君君的前端之路

JavaScript基础笔记

1644
来自专栏怀英的自我修炼

怀英漫谈9 - JS 数组

所谓的数组,就是一些数据的集合,JS中没有集合的概念,所以集合也是数组的一种。如果你Java用的多,那么这个概念就有点儿难以理解,毕竟从Java的文意来说,集合...

1063
来自专栏函数式编程语言及工具

泛函编程(4)-深入Scala函数类

既然是泛函编程,多了解一下函数自然是免不了的了: 方法(Method)不等于函数(Function) 方法不是函数但可以转化成函数;可以手工转换或者由编译器(c...

17310

扫描关注云+社区