Redis 自身是一个 Map,其中所有的数据都是采纳 key:value 的模式存储
这里的数据类型次要是指存储的,也即是 value 的数据类型,key 的数据类型永远都是 String
redis 中 value 应用的数据结构有:
String:字符串类型
List:列表类型
Hash:哈希表类型
Set:无序汇合类型
sorted set:有序汇合类型
上面咱们来一个一个别离来理解一下:
一、String:字符串类型
redis 是应用 C 语言开发,但 C 中并没有 String 类型,只能应用指针或字符数组的模式示意一个字符串,所以 redis 设计了一种简略动静字符串(SDS[Simple Dynamic String]) 作为底层实现。
这个 SDS 的内部结构更像是一个 ArrayList,外部保护着一个字节数组,并且在其外部预调配了肯定的空间,以缩小内存的频繁调配。
Redis 的内存分配机制是这样:
当字符串的长度小于 1MB 时,每次扩容都是加倍现有的空间。
如果字符串长度超过 1MB 时,每次扩容时只会扩大 1MB 的空间。
这样既保证了内存空间够用,还不至于造成内存的节约,字符串最大长度为 512MB。
上图就是字符串的根本构造,其中 content 外面保留的是字符串内容,0x\0 作为完结字符不会被计算 len 中。
SDS 的数据结构:
capacity 和 len 两个属性都是泛型,为什么不间接用 int 类型?因为 Redis 外部有很多优化计划,为更正当的应用内存,不同长度的字符串采纳不同的数据类型示意,且在创立字符串的时候 len 会和 capacity 一样大,不产生冗余的空间,所以 String 值能够是字符串、数字(整数、浮点数) 或者二进制。
redis 中 SDS 和 C 语言字符串比照:
1)C 语言中的字符串,遇到 ’\0’ 则结尾,用长度 N + 1 的数组保护长度为 N 的字符串。
Redis 的 SDS 是:
len 示意字符串的长度;
free 示意闲暇的,未调配的空间;
buffer 数组是真正的字符串,并且以 ’\0’ 结尾。
2)C 字符串并不记录本身的长度信息,获取一个 C 字符串的长度, 必须遍历整个字符串, 对遇到的字符进行计数, 直到遇到代表字符串结尾的空字符为止,复杂度为 O(n)
SDS 在 len 属性中记录了 SDS 的自身长度,复杂度为 O(1)
3)C 字符串不记录本身长度容易造成缓冲区溢出
SDS 的空间调配策略齐全杜绝了产生缓冲区的可能性:当 SDS API 须要对 SDS 进行批改时,API 会先查看 SDS 的空间是否满足批改所需的要求, 如果不满足的话,API 会主动将 SDS 的空间扩大至执行批改所需的大小, 而后才执行理论的批改操作,所以应用 SDS 既不须要批改 SDS 的空间大小, 也不会呈现后面所说的缓冲区溢出问题
4)缩小批改字符串时带来的内存重调配次数
C 字符串的长度和底层数组的长度之间存在这种关联性,所以每次增长或者缩短一个 C 字符串,总要对保留 C 字符串的数组进行一次内存重调配操作
在 SDS 中,buf 数组的长度不肯定就是字符数量加一,数组外面能够蕴含为应用的字节,而这些字节的数量就由 SDS 的 free 属性记录。通过未应用空间,SDS 实现了空间预调配和惰性空间开释两种优化策略
5)二级制平安
C 字符串必须合乎某种编码,并且除了字符串的开端之外,字符串外面不能蕴含空字符
SDS 的 API 都是二进制平安的,所有 SDS API 都会以解决二进制的形式来解决 SDS 寄存在 buf 数组里的数据
6)C 兼容所有字符串函数
SDS 兼容局部 C 字符串函数
String 类型的利用
1、能够存储 base64 的图片数据
2、作为缓存性能,升高 mysql 数据库的申请
3、做一些短时间的谬误限度管制
二、List:列表类型
Redis 中的 list 实质是链表构造
list 的实现在 3.2 版本之前有两种形式:
压缩列表 ziplist
双向链表 linkedlist
在 3.2 版本之后引入了:
疾速列表 quicklist
因为双向链表 linkedlist 占用的内存比压缩列表 ziplist 要多,所以当创立新的列表键时,列表会优先思考应用压缩列表 ziplist,并且在有须要的时候,才从压缩列表 ziplist 实现转换到双向链表 linkedlist 实现。
而后续引入的 quicklist 能够看作是 linkedlist 和 ziplist 的结合体。
这三种列表外部应用哪一种类型是通过编码来辨别的:
linkedlist
linkedlist 是一个双向列表,每个节点都会存储指向上一个节点和指向下一个节点的指针。linkedlist 因为每个节点的空间是不间断的,所以可能会造成过多的空间碎片。
linkedlist 的存储构造,链表中每一个节点都是一个 listNode 对象(源码 adlist.h 内),不过须要留神的是,列表中的 value 其实也是一个字符串对象。
而后会将其再进行封装成为一个 list 对象(源码 adlist.h 内):
Redis 中对 linkedlist 的拜访是以 NULL 值为起点的,因为 head 节点的 prev 节点为 NULL,tail 节点的 next 节点为 NULL。
所以,在 Redis3.2 之前咱们能够失去如下简图:
ziplist
ziplist 是为了节俭内存而开发的一种压缩列表数据结构,哈希数据类型底层也用到了 ziplist。
ziplist 是由一系列非凡编码的间断内存块组成的程序型数据结构,一个 ziplist 能够蕴含任意多个 entry,而每一个 entry 又能够保留一个字节数组或者一个整数值。
ziplist 和 linkedlist 最大的区别是 ziplist 不存储指向上一个节点和下一个节点的指针,存储的是上一个节点的长度和以后节点的长度,就义了局部读写性能来换取高效的内存利用率,是一种工夫换空间的思维。
ziplist 实用于字段个数少和字段值少的场景。
ziplist 的组成构造:
对于列表抉择应用 ziplist 编码进行存储,必须满足上面两个条件:
1)列表对象保留的所有字符串元素的长度都小于 64 字节。
2)列表对象保留的元素数量小于 512 个。
一旦不满足这两个条件中的任意一个,则会应用 linkedlist 编码来进行存储
这两个条件能够通过参数 list-max-ziplist-value 和 list-max-ziplist-entries 进行批改从新设定
quicklist
在 Redis3.2 之后,对立用 quicklist 来存储列表对象,quicklist 存储了一个双向列表,每个列表的节点是一个 ziplist,所以实际上 quicklist 就是 linkedlist 和 ziplist 的联合。
quicklist 外部存储构造,quicklist 中每一个节点都是一个 quicklistNode 对象,其数据结构定义为:
而后各个 quicklistNode 就形成了一个列表,quicklist:
依据下面两个结构图,能够失去 Redis3.2 之后列表的简图:
quicklist 和原始两种列表的比照
quicklist 同样采纳了 linkedlist 的双端列表个性,而后 quicklist 中的每个节点又是一个 ziplist,所以 quicklist 就是综合均衡思考了空间碎片和读写性能两个维度。
应用 quicklist 须要留神以下 2 点:
1、如果 ziplist 中的 entry 个数过少,极其状况就是只有 1 个 entry,此时就相当于进化成了一个一般的 linkedlist。
2、如果 ziplist 中的 entry 过多,那么也会导致一次性须要申请的内存空间过大,而且因为 ziplist 自身的就是以工夫换空间,所以会过多 entry 也会影响到列表对象的读写性能。
ziplist 中的 entry 个数能够通过参数 list-max-ziplist-size 来管制:
list-max-ziplist-size 1
这个参数能够配置负数也能够配置正数。负数示意限度每个节点中的 entry 数量,如果是正数则只能为 -1~-5
-1: 每个 ziplist 最多只能为 4KB
-2: 每个 ziplist 最多只能为 8KB
-3: 每个 ziplist 最多只能为 16KB
-4: 每个 ziplist 最多只能为 32KB
-5: 每个 ziplist 最多只能为 64KB
Redis Lrange 返回列表中指定区间内的元素,区间以偏移量 START 和 END 指定。其中 0 示意列表的第一个元素,1 示意列表的第二个元素,以此类推。也能够应用正数下标,以 -1 示意列表的最初一个元素,-2 示意列表的倒数第二个元素,以此类推。
List 数据类型利用:
timeline:例如微博的时间轴,有人公布微博,用 lpush 退出时间轴,展现新的列表信息。
三、Hash:哈希表类型
Redis hash 是一个 string 类型的 field(字段)和 value(值)的映射表,hash 特地适宜用于存储对象。
Redis 中每个 hash 能够存储 2^32 – 1 键值对(40 多亿)
Redis 的哈希对象的底层存储能够应用 ziplist(压缩列表)和 hashtable。
当 hash 对象能够同时满足以下两个条件时,哈希对象应用 ziplist 编码
1. 哈希对象保留的所有键值对的键和值的字符串长度都小于 64 字节
2. 哈希对象保留的键值对数量小于 512 个
常见操作命令:
所有 hash 的命令都是 h 结尾的 hget、hset、hdel 等
Hash 数据类型利用:
1、缓存:能直观,相比 string 更节俭空间的保护缓存信息,如:用户信息,视频信息等。
四、Set:无序汇合类型
Redis 的 Set 是 String 类型的无序汇合。汇合成员是惟一的,这就意味着汇合中不能呈现反复的数据,将一个反复的元素增加到 set 中将会被疏忽。
汇合对象的编码能够是 intset 或者 hashtable。
Redis 中汇合是通过哈希表实现的,所以增加,删除,查找的复杂度都是 O(1)。
汇合中最大的成员数为 2^32 – 1 (4294967295, 每个汇合可存储 40 多亿个成员)
汇合类型也是用来保留多个字符串的元素,但和列表不同的是,汇合中:
不容许有反复的元素
汇合中的元素是无序的,不能通过索引下标获取元素
反对汇合间的操作,能够取多个汇合取交加、并集、差集
Set 数据类型利用:
1、标签(tag), 给用户增加标签,或者用户给音讯增加标签,这样有同一标签或者相似标签的能够给举荐关注的事或者关注的人
2、点赞,或点踩,珍藏等,能够放到 set 中实现
五、Sorted Set
Redis 的 sorted_set 是有序汇合,在 set 的根底上减少 score 属性用来排序
在 redis 中,数据类型对应的命令个别以数据类型的首字母结尾,然而单词 s 曾经被 string 类型应用了,所以 sorted_set 类型的相干命令只能应用 26 个英文字母中的最初一个字母 z 来结尾,所以 sorted_set 也被称为 zset。
有序汇合和汇合有着必然的分割,保留了汇合不能有反复成员的个性,区别是,有序汇合中的元素是能够排序的,它给每个元素设置一个分数,作为排序的根据。
(有序汇合中的元素不能够反复,然而 score 分数能够反复,就和一个班里的同学学号不能反复,但考试成绩能够雷同)。
Sortedset 底层存储构造:
Sortedset 同时会由两种数据结构反对,ziplist 和 skiplist
只有同时满足如下条件时,应用的是 ziplist,其余时候则是应用 skiplist
1)有序汇合保留的元素数量小于 128 个
2)有序汇合保留的所有元素的长度小于 64 字节
当 ziplist 作为存储构造时候, 每个汇合元素应用两个紧挨在一起的压缩列表节点来保留, 第一个节点保留元素的成员, 第二个元素保留元素的分值.
当应用 skiplist 作为存储构造时, 应用 skiplist 按序保留元素分值, 应用 dict 来保留元素和分值的对应关系
对于 skiplist
skiplist 实质上是一个 list, 它其实是由有序链表倒退而来
咱们先来看一个有序链表,如下图(最左侧的灰色节点示意一个空的头节点):
在这样一个链表中,如果咱们要查找某个数据,那么须要从头开始一一进行比拟,直到找到蕴含数据的那个节点,或者找到第一个比给定数据大的节点为止(没找到)。也就是说,工夫复杂度为 O(n)。同样,当咱们要插入新数据的时候,也要经验同样的查找过程,从而确定插入地位
如果咱们每相邻两个节点减少一个指针,让指针指向下下个节点,如下图:
这样所有新减少的指针连成了一个新的链表,但它蕴含的节点个数只有原来的一半(上图中是 7, 19, 26)。当初当咱们想查找数据的时候,能够先沿着这个新链表进行查找。当碰到比待查数据大的节点时,再回到原来的链表中进行查找。比方,咱们想查找 23,查找的门路是沿着下图中标红的指针所指向的方向进行的:
1)23 首先和 7 比拟,再和 19 比拟,比它们都大,持续向后比拟,当 23 和 26 比拟的时候,比 26 要小,因而回到上面的链表(原链表),与 22 比拟
2)23 比 22 要大,沿上面的指针持续向后和 26 比拟
3)23 比 26 小,阐明待查数据 23 在原链表中不存在,而且它的插入地位应该在 22 和 26 之间
在这个查找过程中,因为新减少的指针,咱们不再须要与链表中每个节点一一进行比拟了。须要比拟的节点数大略只有原来的一半。
利用同样的形式,咱们能够在下层新产生的链表上,持续为每相邻的两个节点减少一个指针,从而产生第三层链表。如下图:
在这个新的三层链表构造上,如果咱们还是查找 23,那么沿着最上层链表首先要比拟的是 19,发现 23 比 19 大,接下来咱们就晓得只须要到 19 的前面去持续查找,从而一下子跳过了 19 后面的所有节点。能够设想,当链表足够长的时候,这种多层链表的查找形式能让咱们跳过很多上层节点,大大放慢查找的速度
skiplist 正是受这种多层链表的想法的启发而设计进去的。实际上,依照下面生成链表的形式,下面每一层链表的节点个数,是上面一层的节点个数的一半,这样查找过程就十分相似于一个二分查找,使得查找的工夫复杂度能够升高到 O(log n)。然而,这种办法在插入数据的时候有很大的问题。新插入一个节点之后,就会打乱高低相邻两层链表上节点个数严格的 2:1 的对应关系。如果要维持这种对应关系,就必须把新插入的节点前面的所有节点(也包含新插入的节点)从新进行调整,这会让工夫复杂度从新进化成 O(n),删除数据也有同样的问题。
skiplist 为了防止这一问题,它不要求高低相邻两层链表之间的节点个数有严格的对应关系,而是为每个节点随机出一个层数(level)。比方,一个节点随机出的层数是 3,那么就把它链入到第 1 层到第 3 层这三层链表中。为了表白分明,下图展现了如何通过一步步地插入操作从而造成一个 skiplist 的过程:
从下面 skiplist 的创立和插入过程能够看出,每一个节点的层数(level)是随机进去的,而且新插入一个节点不会影响其它节点的层数。因而,插入操作只须要批改插入节点前后的指针,而不须要对很多节点都进行调整。这就升高了插入操作的复杂度。实际上,这是 skiplist 的一个很重要的个性,这让它在插入性能上显著优于均衡树的计划。
依据上图中的 skiplist 构造,咱们很容易了解这种数据结构的名字的由来。skiplist,翻译成中文,能够翻译成“跳表”或“跳跃表”,指的就是除了最上面第 1 层链表之外,它会产生若干层稠密的链表,这些链表外面的指针成心跳过了一些节点(而且越高层的链表跳过的节点越多)。这就使得咱们在查找数据的时候可能先在高层的链表中进行查找,而后逐层升高,最终降到第 1 层链表来准确地确定数据地位。在这个过程中,咱们跳过了一些节点,从而也就放慢了查找速度。
刚刚创立的这个 skiplist 总共蕴含 4 层链表,当初假如咱们在它外面仍然查找 23,下图给出了查找门路:
须要留神的是,后面演示的各个节点的插入过程,实际上在插入之前也要先经验一个相似的查找过程,在确定插入地位后,再实现插入操作。
至此,skiplist 的查找和插入操作,咱们曾经很分明了。而删除操作与插入操作相似,咱们也很容易设想进去。这些操作咱们也应该能很容易地用代码实现进去。
当然,理论利用中的 skiplist 每个节点应该蕴含 key 和 value 两局部。后面的形容中咱们没有具体辨别 key 和 value,但实际上列表中是依照 key 进行排序的,查找过程也是依据 key 在比拟。
zset 数据类型利用:
1、排行榜:有序汇合经典应用场景。例如小说视频等网站须要对用户上传的小说视频做排行榜,榜单能够依照用户关注数,更新工夫,字数等打分,做排行
关键词:java 培训