html5 网站案例,太原哪个网站制作最好用,传统小型企业做网站的好处,营业推广是一种什么样的促销方式基本结构图 key和value指向的是redisObject对象 type#xff1a;标识该对象用的是什么类型#xff08;String、List
Redis数据结构
SDS SDS有4个属性#xff1a;
len#xff1a;记录了字符串长度#xff0c;因此获取字符串长度的时候时间复杂度O#xff08;1#xff…基本结构图 key和value指向的是redisObject对象 type标识该对象用的是什么类型String、List
Redis数据结构
SDS SDS有4个属性
len记录了字符串长度因此获取字符串长度的时候时间复杂度O1alloc分配给字符数组的空间长度。这样在修改字符串的时候只需要alloc-len来判断剩余空间大小可以用来判断空间是否满足修改条件如果不满足就会将SDS扩容。因此不会出现C语言的缓冲区溢出问题flags用来表示不同类型的SDS表示len和alloc的类型不同进而保存的SDS分配给字节数组的大小不同。buf[]字节数组用来保存实际数据。不仅可以保存文本数据还可以保存二进制数据。
Redis底层由C语言实现那么SDS与C语言字符串对比
O1获得字符串长度因为SDS有len属性二进制安全SDS不仅可以保存文本数据还能保存二进制数据。SDS的使用len属性来判断是否遍历完成不会管\0的字符不会发生缓冲区溢出通过alloc-len来判断剩余空间大小可以用来判断空间是否满足修改条件如果不满足就会将SDS扩容。因此不会出现C语言的缓冲区溢出问题
扩容机制
如果所需的SDS长度小于1MB,则翻倍 1如果所需的SDS长度超过1MB,最后的扩容大小应该是newlen 1MB 1
压缩列表 ZipList分为这几个部分
zlbytes整个压缩列表占用内存字节数zltail压缩表尾部节点距离起始地址多少个字节也就是列表尾的便宜量zllenentry节点的个数entry部分存储数据的部分zlend压缩列表的结束点固定在0xFF entry的构成
prevlen前一个节点的长度目的是实现从后往前遍历encoding记录当前节点实际的类型和长度类型主要是字符串和整数data记录当前节点的实际存储数据类型和长度由encoding决定
prevlen属性的大小
如果前一个节点的长度小于254字节那么prevlen属性需要1字节如果前一个节点的长度大于等于254字节那么prevlen属性需要5字节
encoding属性的大小
如果当前数据是整数需要1字节如果当前的数据是字符串会根据需要使用1、2、5字节的空间
连续更新问题
压缩列表新增某一个元素或者修改某一个元素如果空间不够压缩列表占用的内存空间需要重新分配。当更新的元素较大会导致后续的prevlen也都要重新分配从而引起连锁更新的问题
quicklist 在 Redis 3.0 之前List 对象的底层数据结构是双向链表或者压缩列表。然后在 Redis 3.2 的时候List 对象的底层改由 quicklist 数据结构实现。 quicklist就是双向链表压缩列表的组合quicklist链表中的每一个节点是一个压缩列表。
解决连锁更新
通过控制链表节点中的压缩列表的大小或者元素个数来规避连锁更新的问题。因为压缩列表元素越小连锁更新带来的影响就越小从而性能提升
哈希表
dictht有这几个属性
dictEntry **table数组的每一个元素是指向哈希表节点的指针size哈希表大小sizemask掩码用于计算索引值used哈希表已有的entry个数
哈希冲突 当两个key不同但是索引值相同就会发生冲突
解决办法是采用拉链法
被分配到同一个哈希桶上的多个节点用一个单项链表连接起来但是也有缺点当链表长度过长的时候查询效率很低。
解决办法是rehash分为三步
给哈希表2分配空间一般比哈希表1大一倍将哈希表1数据迁移到哈希表2迁移完成后哈希表1的空间释放并把哈希表2设置为哈希表1然后在新哈希表2创建出一个空白的哈希表为下次rehash做准备 但是也有问题迁移的过程很耗时间因此采用了渐进式rehash
给哈希表2分配空间一般比哈希表1大一倍在rehash期间每次哈希表元素新增、删除、查找的时候Redis会执行对应的操作外还会将哈希表1中索引位置上的所有dictEntry迁移到哈希表2迁移完成后哈希表1的空间释放并把哈希表2设置为哈希表1然后在新哈希表2创建出一个空白的哈希表为下次rehash做准备
rehash触发条件
负载因子 哈希表已保存的节点数量 / 哈希表大小当负载因子大于等于1并且redis没有进行RDB快照和AOF重写的时候进行rehash当负载因子大于等于5说明哈希冲突非常严重不管也没用RDB快照和AOF重写都会强制执行rehash
整数集合
intset有这几个属性
encoding编码方式比如 INTSET_ENC_INT16那么contents就是一个int16_t类型的数组length集合包含的元素数量contents虽然被声明为 int8_t 类型但是实际上是由保存的数据大小由encoding决定
升级规则
当我们将一个新元素加入集合中如果新元素的类型(int32_t)比现有元素的类型(int16_t)都要长需要扩宽contents数组的大小。在原本的数组上将每个元素按间隔类型分割比如如果encoding属性值为INTSET_ENC_INT16那么间隔就是16位。比如现在有3个类型为int16_t的元素每个都是16位长度然后往整数集合里面加入一个新元素65535这个新元素类型用int32_t保存然后对contents扩容会在原本的空间的大小之上多出80位4 * 32 - 3 * 16 80这样就能保证可以存下4个int32_t的元素然后从后往前依次填充最终再把65535这个元素放到最后。
整数集合升级的好处
如果让一个数组保存int16_t、int32_t、int64_t的元素最好的方式就是用int64_t类型但是会造成空间的浪费。整数升级保证了我们只需要int64_t类型的元素再进行扩容因此可以节约资源内存另外整数集合不支持降级
跳表
跳表是在链表的基础上改进过来的是一个多层有序链表。 跳表zskiplist有以下属性
跳表的头尾节点headtail跳表的长度length跳表的最大层数level
跳表节点zskiplistNode有以下几个属性
eleSDS结构存储数据score节点的分数浮点型backward指向上一个节点的回退指针支持从表尾向表头遍历也就是ZREVRANGE命令level是个zskiplistLevel数组zskiplistLevel包含了两个字段一个是forward指向下一层能调到哪个节点span记录了距离下个节点的步数。数据结构就表示每个节点是个多层结构
跳表节点层数设置
跳表的相邻两层的节点数量最理想的比例是 2:1查找复杂度可以降低到 O(logN)。 Redis在创建节点的时候会生成范围为[0, 1]的随机数如果这个随机数小于0.25相当于概率25%那么层数就增加一层。然后继续生成下一个随机数直到随机数的结构大于0.25就结束这样的做法相当于每增加一层的概率不超过 25%层数越高概率越低层高最大限制是 64。
为什么用跳表而不用平衡树
从内存占用上跳表比平衡树更灵活平衡树每个节点包含2个指针跳表每个节点包含的指针数目为1/1-p在redis中p0.25平均每个节点包含1.33个指针内存占用更少在做范围查询的时候跳表比平衡树操作更简单在平衡树中我们找到特定范围的最小值后还需要以中序遍历的顺序寻找其他不超过大值的节点所以中序遍历不容易实现。而跳表就很简单只需要找到最小值后对第一层的节点进行若干步的遍历即可在算法实现难度上跳表更简单。平衡树的插入和删除操作可能引发子树的调整子树逻辑复杂。而跳表的插入和删除只需要修改相邻的节点操作简单又迅速。
listpack
quicklist并没有完全解决连锁更新问题因为quicklist还是使用了压缩列表来保存元素于是有了listpack listpack结构
listpack头包含两个属性分别记录了listpack总字节数和元素数量。然后listpack也有一个结尾标识。listpack entry是listpack的节点 listpack entry
encoding定于元素的编码类型会对不同长度的整数和字符串进行编码data实际存放的数据lenencdongdata的总长度
将prevlen改成len之后能不能从后往前遍历
答案是可以。lpDecodeBacklen函数已经实现了
Redis数据对象有哪些
概述 常见的对象有以下五种
String二进制安全的特性是可以包含任何数据比如一个序列化的对象一个键最大能存储512M。适用于简短的字符场景。底层数据结构采用的是SDS或者INT编码Hash键值对数据结构相当于编程语言的Map。适用于存储、读取、修改用户属性。底层数据结构是哈希表或者压缩列表Set包含字符串的无序集合增删查找快。使用于最新消息排行榜消息队列。底层数据结构是哈希表或者整数集合Sort Set: 将Set集合加一个权重参数score元素按照score排序。特性是在插入元素的时候自然排序。适用于排行榜、带权重的消息队列。底层数据结构是跳表或者压缩列表
String
字符串对象的内部编码encoding有 3 种 int、raw和 embstr。
int如果一个字符串对象保存的是整数值并且这个整数值可以用long类型表示那么这个字符串对象会被保存在redisObject对象的prt中同时将encoding设置成intembstr如果一个字符串对象保存的是字符串并且这个字符串对象小于等于32字节。那么字符串对象将用SDS表示同时encoding设置成embstrraw如果一个字符串对象保存的是字符串并且这个字符串对象大于32字节。那么字符串对象将用SDS表示同时encoding设置成raw
embstr和raw都会用SDS来保存值但不同之处在于embstr会通过一次内存分配函数来分配一块连续的内存空间来保存redisObject和SDS。而raw编码会调用两次内存分配函数分别分配redisObject和SDS。
embstr相比raw好处
embstr编码创建字符串对象只用调用一次内存分配函数而raw编码需要两次释放embstr编码的字符串对象同样也只需要调用一次内存释放函数因为embstr编码的字符串对象的所有数据都保存在一块连续的内存空间可以更好的利用cpu缓存提升性能
但embstr也有缺点
如果字符串的长度需要重新分配空间时整个redisObject和sds都需要重新分配空间所以embstr编码的字符串对象实际上是只读的。redis没有为embstr编码的字符串对象编写任何修改的程序。当我们对embstr编码的字符串对象执行修改的命令实际上是先将编码从embstr转换成raw再做修改。
List
底层是双向链表和压缩列表
如果列表中的元素小于512个列表每个元素的值都小于64字节redis会用压缩列表存储否则用双向链表
在redis3.2之后使用quicklist作为底层数据结构
Hash
如果哈希类型元素个数小于512个并且所有值小于64字节Redis会用压缩列表底层数据结构 否则用哈希表 在redis7.0压缩列表结构被抛弃使用listpack
Set
如果集合中的元素都是整数且元素个数小于512使用整数集合否则用哈希表
Zset
如果有序集合元素小于128个并且每个元素大小小于64字节使用压缩列表否则用跳表
Redis7.0已经将压缩列表废弃使用listpack
