成都网站建设服务,网站qq一键登录,网站建设基础内容,哪些网站可以做化妆品广告引言
Redis是一款基于键值对的数据结构存储系统#xff0c;它的特点是基于内存操作、单线程处理命令、IO多路复用模型处理网络请求、键值对存储与简单丰富的数据结构等等
这篇文章主要围绕Redis中的对象与数据结构来详细说明键值对存储与简单丰富的数据结构这两大特点
Redi…引言
Redis是一款基于键值对的数据结构存储系统它的特点是基于内存操作、单线程处理命令、IO多路复用模型处理网络请求、键值对存储与简单丰富的数据结构等等
这篇文章主要围绕Redis中的对象与数据结构来详细说明键值对存储与简单丰富的数据结构这两大特点
Redis中的数据以Key,Value键值对的形式存储在字典中字典的实现是哈希表
键Key只能使用字符串对象来表示值Value能够使用其他所有对象
对象与数据结构
Redis中存在丰富的对象常用的对象数据类型有字符串对象string、列表对象list、散列对象hash、集合对象set、有序集合对象zset等
还有其他的数据类型如Bitmap、Hyperloglog、Geospatial、布隆过滤器等但这篇文章只涉及常用的对象其他数据类型再以后的文章中再展开说明
redis中的对象RedisObject由类型、编码、引用次数、lru、指向编码使用的数据结构对象构成 类型标识这个对象是什么类型对象 比如字符串、列表、哈希、集合、有序集合等 编码表示构成对应类型对象时使用哪种数据结构 引用次数表示这个对象被引用了多少次 redis内存回收使用引用计数法回收引用次数为0的对象 redis只依赖字符串对象而不存在循环依赖所以不存在循环引用因此可以使用引用计数法 lru记录这个对象最近被调用的时间当空间回收算法使用lru时会优先回收很久未用的对象后续删除回收的文章会介绍
数据结构
sds简单动态字符串
sds使用字节数组维护len记录字符串长度表示结尾的\0不算free表示字节数组中空闲的长度 在添加元素前会判断数组长度是否足够不够则会进行扩容扩容有空间预分配策略会留有一部分空闲空间
如果下次修改字符串未超出数组长度就能够直接修改节省了扩容的开销
hashtable字典
字典使用哈希表实现哈希表的原理本篇文章不会详细概述
哈希冲突使用链地址法解决查找时先通过 hash%数组长度-1 来获取索引得到索引后再遍历链表节点如果是新增则直接使用头插法插入链表头部 为了防止大字典扩容时发生阻塞字典中哈希表的扩容是循序渐进的在发生扩容时会有俩个哈希表 旧哈希表和新哈希表中都可能存储数据再收到hget等请求时先在旧哈希表中查找找到了就顺便把它迁移到新哈希表中在旧哈希表中没找到就去新哈希表中找
在完成迁移时新哈希表将旧哈希表替换
skiplist跳表
跳表维护多层级的有序链表利用高层能够快速达到后续节点实现简单维护方便增删改查时间复杂度平均log n 比如查找值为2.0的节点查找顺序为图中虚线
先找到虚拟头节点从当前维护的最高层L5开始寻找往后找到o3对象值为3.0说明已经找过头了于是要去下一层进行寻找来到L4先后遍历o1对象值为1.0比目标值2.0小说明没有目标值在o1对象后面于是来到o1对象L4层继续在o1对象L4向后遍历发现o3值为3.0大于目标值于是降层来到o1对象L3层L3层后面也是o3于是继续降层来到L2层L2层向后遍历为o2对象值为2.0并比较o2对象相同说明找到了
从维护的最高层开始查询查询为空或者查询值大于目标值则降层当前在最后一层还需要降层说明找不到
当排序值相同时按照对象大小排序这里的对象都是字符串对象
增加节点时的层数是随机生成的越高层几率越小其他修改操作也是通过查询再进行同时还要维护一些如最高层级等其他属性
intset整数集合
intset 维护了一个有序无重复的数组
在实现上使用数组、长度记录元素数量和编码编码能够标识元素类型如16、32、64位的整型 当加入的元素为当前数组内不存在的高位整型时比如数组中都是32位整型此时加入一个64位整型发生升级先申请内存重分配再将旧元素移动到对应位置上然后加入新元素同时修改编码当删除高位整型时不会发生降级
intset的升级有效的节约内存当set对象都为整型且数据量较小时使用intset实现以此来节约内存
ziplist压缩列表
ziplist用连续空间的节点构成节点由记录前驱节点偏移量逆序遍历、编码字节数组或整型的编码、内容内容可以是字节数组或整型组成 因为ziplist的内容不是固定的比如记录前驱节点偏移量是可变长的这会影响节点的长度又因为ziplist是空间连续的这会导致后续的节点空间都要变动被称为连锁更新发生的概率小
为了节省空间用于数量量小场景下列表、哈希、有序集合的实现
quicklist快速列表
快速列表可以当作双向链表只不过节点使用ziplist常用来实现数据量大场景下的列表对象
对象
说明
下文中数据量代表着占用字节情况和数据元素数量
本篇文章不介绍各个对象的命令使用规则需要学习命令的同学可以去官网查看
字符串对象
字符串对象string由sds简单动态字符串来实现
sds有不同的编码int、embstr、row int 用来存储整型字符串计算时可能发生整型与字符串的转换embstr 用来存储短的字符串只分配一次内存分配内存时同时分配redisobject和sdsrow 用来存储长字符串分配内存时需要分配两次redisobject、sds
字符串对象是Redis中最常用的对象也是唯一会被其他对象依赖使用的对象
字符串对象常见的使用场景整存整取的缓存、计数器、分布式锁
列表对象
列表对象list是一个队列可以操作队头队尾由ziplist或quicklist来实现
数据量小时使用ziplist数据量大时使用quicklist( linkedlistziplist )
列表的使用场景是FIFO队列保证元素访问顺序
哈希对象
哈希对象hash是维护KV键值对的无序数据结构由ziplist或hashtable来实现
数据量少使用ziplist、数据量大使用hashtable
哈希的使用场景是缓存的部分存取比如一个大礼包下有A商品B商品等
集合对象
集合对象set的特点是无序、无重由intset或hashtable来实现
数据量少且数据为整型使用intset、数据量大或数据不为整型使用hashtable且值永远为null
集合的使用场景是唯一性元素或交集并集共同关注、可能认识等无序、无重复
有序集合对象
有序集合对象zset是有序、无重的数据结构由ziplist或skiplist hashtable实现
数据量少时使用ziplist、数据量大时使用skiplist hashtable为了满足根据对象查询分指常量级功能共享对象不造成内存开销
有序集合的使用场景是排行榜、关注程度榜单等有序、无重复
总结
本篇文章围绕Redis以键值对存储、丰富多元的数据结构为特点详细介绍了Redis中的对象与数据结构
对象由类型、编码、数据结构指针等构成
为了节省空间每种类型的对象都有多种编码类型的数据结构能够实现
字符串对象常用来做缓存、分布式锁、计数器等被其他对象依赖使用 由sds实现主要有int、embstr、row三种编码来处理不同类型的字符串embstr处理短字符串优化内存分配sds是动态字符串利用空间预分配策略在修改不超过数组长度情况下可以不需要进行扩容节省开销 列表对象常用来维护队列元素有序性 当数据量小时使用压缩列表ziplist实现数据量大时使用快速列表quicklist实现压缩列表使用连续空间节点中存储可以时字符串也可以是整型快速列表则可以当作链表节点为压缩列表 哈希对象常用来维护部分存取的缓存 当数据量小时使用压缩列表zpilist实现数据量大时使用哈希表hashtable实现哈希表为了防止阻塞在扩容时使用新旧两个哈希表存储元素在处理命令的同时完成迁移 集合对象有无序、无重的特点常用来做唯一、交集共同好友、并集可能认识 当数据量小且元素都为整型时使用整型集合intset实现当数据量大使用哈希表实现整型集合有不同的编码形式充分节省了空间使用哈希表时Value为空 有序集合对象有有序、无重的特点常用来做排行榜 当数据量小时使用压缩列表实现当数据量大时使用跳表skiplist哈希表实现哈希表保存K对象V比较值跳表是多层级有序的链表平均时间复杂度在log n简单易维护
最后一键三连求求拉~
本篇文章笔记以及案例被收入 gitee-StudyJava、 github-StudyJava 感兴趣的同学可以stat下持续关注喔~
有什么问题可以在评论区交流如果觉得菜菜写的不错可以点赞、关注、收藏支持一下~
关注菜菜分享更多干货公众号菜菜的后端私房菜 本文由博客一文多发平台 OpenWrite 发布
