视频教学互动网站建设,wordpress搜索框智能搜索,深圳外贸公司排名,网站开发公司哪家最专业redis可以存储键与5种不同数据结构类型之间的映射#xff1a; String类型的底层实现只有一种数据结构#xff0c;也就是动态字符串。而List、Hash、Set、ZSet都由两种底层数据结构实现。通常我们把这四种类型称为集合类型#xff0c;它们的特点是一个键对应了一个集合的数据… redis可以存储键与5种不同数据结构类型之间的映射 String类型的底层实现只有一种数据结构也就是动态字符串。而List、Hash、Set、ZSet都由两种底层数据结构实现。通常我们把这四种类型称为集合类型它们的特点是一个键对应了一个集合的数据。下面分别介绍下
一、STRING字符串
1、介绍redis没有直接使用C语言传统的字符串表示而是自己实现的叫做简单动态字符串SDS的抽象类型。C语言的字符串不记录自身的长度信息而SDS则保存了长度信息内部结构实现上类似于 Java 的ArrayList这样将获取字符串长度的时间由O(N)降低到了O(1)同时可以避免缓冲区溢出和减少修改字符串长度时所需的内存重分配次数
对C语言中的字符串的封装和优化c语言字符串不是二进制安全的字符串中间不能有空格空格标志结束频繁修改一个字符串时会涉及到内存的重分配比较消耗性能。Redis中的简单动态字符串会有内存预分配和惰性空间释放。如果字符串实际使用长度len1M实际分配空间len长度来存储字符串1字节存末尾空字符len长度的预分配空闲内。如果字符串实际使用长度len1M实际分配空间len长度来存储字符串1字节存末尾空字符1M长度的预分配空闲内存
2、底层数据结构简单动态字符串free、len、buf[](可以保存文本二进制不会缓冲溢出获取字符串长度时间[O1]
3、大小当字符串长度小于 1M 时扩容都是加倍现有的空间如果超过 1M扩容时一次只会多扩 1M 的空间。需要注意的是字符串最大长度为 512M
4、基本命令set,get,strlen,exists,decr,incr,setex 等等;
set num 1incr num【计数器】expire key 60ttl key 【设置过期时间查看指定key的过期时间】
5、应用场景计数
二、LIST列表
1、底层数据结构链表链接上的每个节点都包含了一个字符串。
Redis中list是由两种数据结构构成的数据少时用ziplist数据多时用linkedlistziplist连锁更新耗时当列表弹出了最后一个元素之后该数据结构自动被删除内存被回收。
扩展也可将list模拟队列和栈的使用。 列表元素较少的情况下会使用一块连续的内存存储这个结构是 ziplist也即是压缩列表。它将所有的元素紧挨着一起存储分配的是一块连续的内存。当数据量比较多的时候才会改成 quicklist。因为普通的链表需要的附加指针空间太大会比较浪费空间而且会加重内存的碎片化。
比如这个列表里存的只是 int 类型的数据结构上还需要两个额外的指针 prev 和 next 。所以 Redis 将链表和 ziplist 结合起来组成了 quicklist。也就是将多个ziplist 使用双向指针串起来使用。这样既满足了快速的插入删除性能又不会出现太大的空间冗余。
linkedlist维护前后指针占内存空间还造成内存碎片化
ziplist没有前后指针entry保存了上一个结点长度所以也可以双向遍历但是当一个结点长度变化了后面结点都要变连锁更新耗时
ziplist结构
zlbytes整个ziplist占字节数zltail尾结点相对于首地址偏移量zllen结点数entry保存了前一个结点长度编码内容zlend代表结束
2、基本命令rpush、lpop、lpush、rpop,、lrange、llen 等。
3、应用场景
1发布与订阅或者说消息队列 Redis 的列表结构常用来做异步队列使用。将需要延后处理的任务结构体序列化成字符串塞进 Redis 的列表另一个线程从这个列表中轮询数据进行处理
2慢查询。
三、SET集合
1、底层数据结构哈希表整数数组。 Redis 的集合相当于 Java 语言里面的 HashSet它内部的键值对是无序的唯一的。它的内部实现相当于一个特殊的字典字典中所有的 value 都是一个值 NULL。由于是set有天然去重功能。
2、常用命令sadd、spop、smembers、sismember、scard、sinterstore、sunion 等。
3、使用场景数据不重复可以判断一个成员是否存在交集并集共同关注、粉丝两个集合求交集
四、HASH字典
1、底层数据结构Redis 的字典相当于 Java 语言里面的 HashMap它是无序字典。内部实现结构上同Java 的 HashMap 也是一致的同样的数组 链表二维结构。第一维 hash 的数组位置碰撞时就会将碰撞的元素使用链表串接起来。 不同的是Redis 的字典的值只能是字符串另外它们 rehash 的方式不一样因为Java 的 HashMap 在字典很大时rehash 是个耗时的操作需要一次性全部 rehash。Redis 为了高性能不能堵塞服务所以采用了渐进式 rehash 策略。 1触发rehash的时机
字典类型容量变化过程叫做rehash,需要满足一定的条件才能触发扩容机制。服务器当前没有进行BGWRITEAOF或者BGSAVE命令且当前键值对个数超过一维数组的大小才会触发扩容。
如果当前键值对个数超过一维数组大小的五倍无论是否在进行BGWRITEAOF或者BGSAVE命令都会强制扩容。 Hash类型扩容后数组的长度为原来的二倍
缩容机制如果当前键值对个数少于一维数组大小的十分之一则触发缩容过程。缩容不会考虑当前服务器是否在进行BGWRITEAOF或者BGSAVE命令。
2Rehash过程
利用了两个哈希表进行的 , 有点类似数据库的迁移 , 读的时候先读旧库 , 读不到读新库 , 写的时候只写新库 ; 其他旧数据一点点的往新库上搬。
当触发扩容的时候Redis会首先为ht[1] 分配一块内存空间。如果当前字典是一个比较大的字典那么整个扩容过程的时间复杂度为O(n)直接完整进行扩容机制可能会导致Redis一段时间内停止服务。为了避免停止服务的情况Redis的设计团队采用了渐进式rehash的策略每次只对原哈希表中的一小部分进行搬迁这样渐进式的进行直到全部键值对都迁移到新的哈希表中。
首先对于key的查询我们需要到原来的哈希表中进行查找如果找到对应的value直接返回就可以了。如果没有找到那么只有两种可能一个是这个键值对已经搬迁到新的哈希表了另外一种可能是根本就不存在这个键值对无论是哪种可能我们都需要再去新哈希表中对他进行查找如果找到了就返回如果找不到说明这个键值对不存在。
五、ZSET有序集合
1、底层数据结构
ZSet数据结构类似于Set结构只是ZSet结构中每个元素都会有一个分值然后所有元素按照分值的大小进行排列相当于是一个进行了排序的链表。
如果ZSet是一个链表而且内部元素是有序的在进行元素插入和删除以及查询的时候就必须要遍历链表才行时间复杂度就达到了O(n),这个在以单线程处理的Redis中是不能接受的。所以ZSet采用了一种跳跃表的实现。这个实现有点类似于Kafka存储消息是使用的稀疏索引。这种跳跃表的实现其实和二分查找的思路有点接近只是一方面因为二分查找只能适用于数组而无法适用于链表所以为了让链表有二分查找类似的效率就以空间换时间来达到目的。
操作时间复杂度O(logn)空间复杂度O(n)为何不用红黑树这些跳表实现简单平衡树插入删除可能引发平衡调整更加复杂跳表只需要动动结点指针做范围查找的时候平衡树比skiplist操作要复杂。插入结点使用随机层数算法建立层数 每层晋升概率0.25
2、常用命令zadd,zcard,zscore,zrange,zrevrange,zrem
3、应用场景 跳跃表因为是一个根据分数权重进行排序的列表可以再很多场景中进行应用比如排行榜搜索排序等等。
