Redis中常见的五种数据类型(一)

Redis中常见的五种数据类型(一)

Redis的基本数据类型-1

相关视频参考(来自动力节点):https://www.bilibili.com/video/BV1Uz4y1X72A

相关资料下载:http://www.bjpowernode.com/?cnblogs

1、redis基础

1)redis 中的数据类型有哪些?

Redis 有 5 种基础数据结构,分别为:string (字符串)、list (列表)、set (集合)、hash (哈希) 和 zset (有序集合)。

Redis 的列表相当于 Java 语言里面的 LinkedList,注意它是链表而不是数组。这意味着 list 的插入和删除操作非常快,时间复杂度为 O(1),但是索引定位很慢,时间复杂度为 O(n),这点让人非常意外。 当列表弹出了最后一个元素之后,该数据结构自动被删除,内存被回收。

Redis 的哈希相当于 Java 语言里面的 HashMap,它是无序字典。内部实现结构上同 Java 的 HashMap 也是一致的,同样的数组 + 链表二维结构。第一维 hash 的数组位置碰撞时,就会将碰撞的元素使用链表串接起来。

Redis 的集合相当于 Java 语言里面的 HashSet,它内部的键值对是无序的唯一的。它的内部实现相当于一个特殊的字典,字典中所有的 value 都是一个值NULL。 当集合中最后一个元素移除之后,数据结构自动删除,内存被回收。

zset 类似于 Java 的 SortedSet 和 HashMap 的结合体,一方面它是一个 set,保证了内部 value 的唯一性,另一方面它可以给每个 value 赋予一个 score,代表这个 value 的排序权重。

2)为什么说redis能够快速执行

  • 绝大部分请求是纯粹的内存操作(非常快速)
  • 采用单线程,避免了不必要的上下文切换和竞争条件
  • 非阻塞IO - IO多路复用

2、Redis中的五种数据结构

1)string (字符串)

redis是使用C语言开发,但C中并没有字符串类型,只能使用指针或符数组的形式表示一个字符串,所以redis设计了一种简单动态字符串(SDS[Simple Dynamic String])作为底实现:

定义SDS对象,此对象中包含三个属性:

  1. len buf中已经占有的长度(表示此字符串的实际长度)
  2. free buf中未使用的缓冲区长度
  3. buf[] 实际保存字符串数据的地方

所以取字符串的长度的时间复杂度为O(1),另,buf[]中依然采用了C语言的以结尾可以直接使用C语言的部分标准C字符串库函数。

空间分配原则:当len小于IMB(1024*1024)时增加字符串分配空间大小为原来的2倍,当len大于等于1M时每次分配 额外多分配1M的空间。

由此可以得出以下特性:

  • redis为字符分配空间的次数是小于等于字符串的长度N,而原C语言中的分配原则必为N。降低了分配次数提高了追加速度,代价就是多占用一些内存空间,且这些空间不会自动释放。
  • 二进制安全的
  • 高效的计算字符串长度(时间复杂度为O(1))
  • 高效的追加字符串操作。

2)list (列表)

redis对键表的结构支持使得它在键值存储的世界中独树一帜,一个列表结构可以有序地存储多个字符串,拥有例如:lpush lpop rpush rpop等等操作命令。在3.2版本之前,列表是使用ziplist和linkedlist实现的,在这些老版本中,当列表对象同时满足以下两个条件时,列表对象使用ziplist编码:

  • 列表对象保存的所有字符串元素的长度都小于64字节
  • 列表对象保存的元素数量小于512个
  • 当有任一条件 不满足时将会进行一次转码,使用linkedlist。

而在3.2版本之后,重新引入了一个quicklist的数据结构,列表的底层都是由quicklist实现的,它结合了ziplist和linkedlist的优点。按照原文的解释这种数据结构是【A doubly linked list of ziplists】意思就是一个由ziplist组成的双向链表。那么这两种数据结构怎么样结合的呢?

3)ziplist的结构

由表头和N个entry节点和压缩列表尾部标识符zlend组成的一个连续的内存块。然后通过一系列的编码规则,提高内存的利用率,主要用于存储整数和比较短的字符串。可以看出在插入和删除元素的时候,都需要对内存进行一次扩展或缩减,还要进行部分数据的移动操作,这样会造成更新效率低下的情况。

4)linkedlist的结构

意思为一个双向链表,和普通的链表定义相同,每个entry包含向前向后的指针,当插入或删除元素的时候,只需要对此元素前后指针操作即可。所以插入和删除效率很高。但查询的效率却是O(n)[n为元素的个数]。

了解了上面的这两种数据结构,我们再来看看上面说的“ziplist组成的双向链表”是什么意思?

实际上,它整体宏观上就是一个链表结构,只不过每个节点都是以压缩列表ziplist的结构保存着数据,而每个ziplist又可以包含多个entry。也可以说一个quicklist节点保存的是一片数据,而不是一个数据。

总结:

1、整体上quicklist就是一个双向链表结构,和普通的链表操作一样,插入删除效率很高,但查询的效率却是O(n)。不过,这样的链表访问两端的元素的时间复杂度却是O(1)。所以,对list的操作多数都是poll和push。

2、每个quicklist节点就是一个ziplist,具备压缩列表的特性。