网站推广方法素材,教学网站建设,永久免费制作网站,wordpress 企业插件文章目录 动态字符串SDS字符串编码类型 intsetDictZipListZipList的连锁更新问题 QuickListSkipListRedisObjectStringListSet结构ZSETHash Redis 共有 5 种基本数据结构#xff1a;String#xff08;字符串#xff09;、List#xff08;列表#xff09;、Set#xff08;… 文章目录 动态字符串SDS字符串编码类型 intsetDictZipListZipList的连锁更新问题 QuickListSkipListRedisObjectStringListSet结构ZSETHash Redis 共有 5 种基本数据结构String字符串、List列表、Set集合、Hash散列、Zset有序集合。
这 5 种数据结构是直接提供给用户使用的是数据的保存形式其底层实现主要依赖这 8 种数据结构简单动态字符串SDS、LinkedList双向链表、Hash Table哈希表、SkipList跳跃表、Intset整数集合、ZipList压缩列表、QuickList快速列表。
Redis 基本数据结构的底层数据结构实现如下 Redis 3.2 之前List 底层实现是 LinkedList 或者 ZipList。 Redis 3.2 之后引入了 LinkedList 和 ZipList 的结合 QuickListList 的底层实现变为 QuickList。
动态字符串SDS
我们都知道Redis中保存的Key是字符串value往往是字符串或者字符串的集合。可见字符串是Redis中最常用的一种数据结构。
不过Redis没有直接使用C语言中的字符串因为C语言字符串存在很多问题
获取字符串长度的需要通过运算非二进制安全不可修改 什么是非二进制安全 二进制安全是一种主要用于字符串操作函数相关的计算机编程术语。一个二进制安全功能函数其本质上将操作输入作为原始的、无任何特殊格式意义的数据流。对于每个字符都公平对待不特殊处理某一个字符。 大多数的函数当其使用任何特别的或标记字符如转义码那些期望 null 结尾的字符串如C语言中的字符串不是二进制安全的。一个可能的例外是该函数的明确的目的是在某二进制字符串搜索某特定字符。 我们举个例子 C语言的字符串中的字符必须符合某种编码如ASCII并且除了字符串末尾的空字符其他位置不能包含空字符否则会出现数据被截断的情况比如 如果使用C字符串所用的函数来识别只能读取到“hello”后面的“world”会被忽略这个限制使得C字符串只能保存文本数据而不能保存图片、视频、压缩文件等二进制数据。 SDS的API都会以二进制的方式来处理SDS存放在buf数组里的数据Redis使用这个数组保存的是一系列二进制数据而不是保存字符。SDS使用len属性的值判断字符串是否结束而不是空字符即SDS是二进制安全的。 Redis构建了一种新的字符串结构称为简单动态字符串Simple Dynamic String简称SDS。
例如我们执行命令 那么Redis将在底层创建两个SDS其中一个是包含“name”的SDS另一个是包含“虎哥”的SDS。
Redis是C语言实现的其中SDS是一个结构体源码如下 这里的sds根据长度类型分为五类比如我们看到sdshdr8中len属性的类型为uint8_t代表无符号8比特位len最大为255也就是说这种类型的sds长度最大为255字节。 struct __attribute__ ((__packed__)) sdshdr8 {uint8_t len; // 已经使用的字节数uint8_t alloc; // 实际可以存储的字节最大长度不包括SDS头部和结尾的空字符unsigned char flags; // flags中的低3个bit决定使用哪种结构存储字符串高5bit未使用char buf[]; // 柔性数组用来保存实际的字符串
};sdshdrxx会根据字符串的实际长度选取合适的结构最大化节省内存空间。获取字符串长度时间复杂度O(1)。 例如一个包含字符串“name”的sds结构如下 SDS之所以叫做动态字符串是因为它具备动态扩容的能力例如一个内容为“hi”的SDS 假如我们要给SDS追加一段字符串“,Amy”这里首先会申请新内存空间 如果新字符串小于1M则新空间为扩展后字符串长度的两倍1Byte 如果新字符串大于1M则新空间为扩展后字符串长度1M1Byte。称为内存预分配。 申请内存的动作非常消耗资源而通过内存的预分配可以适当地减少申请内存的次数。 字符串编码类型
字符串类型的内部编码有三种 int存储 8 个字节的长整型long2^63-1如果 value 是 long 类型的整数则使用此编码。 embstr代表 embstr 格式的 SDS存储小于 44 个字节的字符串3.2 版本之前是 39 个字节只分配一次内存空间因为 Redis Object 和 SDS 是连续的。 embstr 分配的是连续的一块内存包含 robj 和 sdsrobj 占用了16个字节3.2 版本之前 sds 占用 8 个字节3.2 及之后版本 占用 3 个字节。因此 在 3.2 版本之前如果字符串存储小于等于 39 个字节编码为 embstr超过 39 个字节编码为 raw在 3.2 及之后如果字符串存储小于等于 44 个字节编码为 embstr超过 44 个字节编码为 raw。 优点只需要一次内存分配数据比较小的时候使用的是这种编码数据更紧凑效率更高。缺点没有提供修改的函数所以是只读的如果要对此编码数据进行修改会变成 raw 再执行修改然后结束。 raw存储大于 44 个字节的字符串3.2 版本之前是 39 个字节需要分配两次内存空间分别为 Redis Object 和 SDS 分配空间。raw 分配的不是连续的内存需要调用两次内存分配函数来分别创建 robj 和 sds。
intset
IntSet是Redis中set集合的一种实现方式基于整数数组来实现并且具备长度可变、有序等特征。 结构如下 其中的encoding包含三种模式表示存储的整数大小不同 分析
contents数组是整数集合的底层实现整数集合中的每一个元素就是contents数组中的一个元素每个元素在数组中按照从小到大的顺序排列并且没有重复元素。
虽然contents数组被声明为 int8_t 类型的数组但实际上contents数组并不保存任何int8_t 类型的值contents数组实际存储的类型取决于encoding的值。encoding的取值可以是INTSET_ENC_INT16、INTSET_ENC_INT32 或 INTSET_ENC_INT64每种编码的取值范围如下
INTSET_ENC_INT16 取值范围[−2^15 2^15−1] 即[-32768, 32767 ]INTSET_ENC_INT32 取值范围[−2^31 2^31−1] 即[-2147483648, 2147483647]INTSET_ENC_INT64 取值范围[−2^63 2^63−1] 即[-9223372036854775808, 9223372036854775807]
为了方便查找Redis会将intset中所有的整数按照升序依次保存在contents数组中结构如图 通过右边的寻址公式可以得到每一个整数的位置这也反映了为什么要将数组中的数字编码类型进行统一。因为是连续的内存地址方便寻找数组中每个元素的地址。 现在数组中每个数字都在int16_t的范围内因此采用的编码方式是INTSET_ENC_INT16每部分占用的字节大小为
encoding4字节length4字节contents2字节 * 3 6字节 我们向该其中添加一个数字50000这个数字超出了int16_t的范围intset会自动升级编码方式到合适的大小。 以当前案例来说流程如下
升级编码为INTSET_ENC_INT32, 每个整数占4字节并按照新的编码方式及元素个数扩容数组倒序依次将数组中的元素拷贝到扩容后的正确位置将待添加的元素放入数组末尾最后将inset的encoding属性改为INTSET_ENC_INT32将length属性改为4 源码如下 小总结
Intset可以看做是特殊的整数数组具备一些特点
Redis会确保Intset中的元素唯一、有序具备类型升级机制可以节省内存空间底层采用二分查找方式来查询
Dict
我们知道Redis是一个键值型Key-Value Pair的数据库我们可以根据键实现快速的增删改查。而键与值的映射关系正是通过Dict来实现的。 Dict由三部分组成分别是哈希表DictHashTable、哈希节点DictEntry、字典Dict 当我们向Dict添加键值对时Redis首先根据key计算出hash值h然后利用 h sizemask来计算元素应该存储到数组中的哪个索引位置。我们存储k1v1假设k1的哈希值h 1则13 1因此k1v1要存储到数组角标1位置。 Dict由三部分组成分别是哈希表DictHashTable、哈希节点DictEntry、字典Dict Dict的扩容
Dict中的HashTable就是数组结合单向链表的实现当集合中元素较多时必然导致哈希冲突增多链表过长则查询效率会大大降低。
Dict在每次新增键值对时都会检查负载因子LoadFactor used/size 满足以下两种情况时会触发哈希表扩容
哈希表的 LoadFactor 1并且服务器没有执行 BGSAVE 或者 BGREWRITEAOF 等后台进程哈希表的 LoadFactor 5 Dict的rehash
不管是扩容还是收缩必定会创建新的哈希表导致哈希表的size和sizemask变化而key的查询与sizemask有关。因此必须对哈希表中的每一个key重新计算索引插入新的哈希表这个过程称为rehash。过程是这样的 计算新hash表的realeSize值取决于当前要做的是扩容还是收缩 如果是扩容则新size为第一个大于等于dict.ht[0].used 1的2^n如果是收缩则新size为第一个大于等于dict.ht[0].used的2^n 不得小于4 按照新的realeSize申请内存空间创建dictht并赋值给dict.ht[1] 设置dict.rehashidx 0标示开始rehash 将dict.ht[0]中的每一个dictEntry都rehash到dict.ht[1] 将dict.ht[1]赋值给dict.ht[0]给dict.ht[1]初始化为空哈希表释放原来的dict.ht[0]的内存 将rehashidx赋值为-1代表rehash结束 在rehash过程中新增操作则直接写入ht[1]查询、修改和删除则会在dict.ht[0]和dict.ht[1]依次查找并执行。这样可以确保ht[0]的数据只减不增随着rehash最终为空
整个过程可以描述成 小总结
Dict的结构
类似java的HashTable底层是数组加链表来解决哈希冲突Dict包含两个哈希表ht[0]平常用ht[1]用来rehash
Dict的伸缩
当LoadFactor大于5或者LoadFactor大于1并且没有子进程任务时Dict扩容当LoadFactor小于0.1时Dict收缩扩容大小为第一个大于等于used 1的2^n收缩大小为第一个大于等于used 的2^nDict采用渐进式rehash每次访问Dict时执行一次rehashrehash时ht[0]只减不增新增操作只在ht[1]执行其它操作在两个哈希表
ZipList
ZipList 是一种特殊的“双端链表” 由一系列特殊编码的连续内存块组成。可以在任意一端进行压入/弹出操作, 并且该操作的时间复杂度为 O(1)。 属性类型长度用途zlbytesuint32_t4 字节记录整个压缩列表占用的内存字节数zltailuint32_t4 字节记录压缩列表表尾节点距离压缩列表的起始地址有多少字节通过这个偏移量可以确定表尾节点的地址。zllenuint16_t2 字节记录了压缩列表包含的节点数量。 最大值为UINT16_MAX 65534如果超过这个值此处会记录为65535但节点的真实数量需要遍历整个压缩列表才能计算得出。entry列表节点不定压缩列表包含的各个节点节点的长度由节点保存的内容决定。zlenduint8_t1 字节特殊值 0xFF 十进制 255 用于标记压缩列表的末端。 例如 说明ziplist 的总长度为96字节0x60的十进制最后一个entry距离ziplist起始位置偏移了75字节0x4B的十进制ziplist中此时有30x03的十进制个entry。 ZipListEntry
ZipList 中的Entry并不像普通链表那样记录前后节点的指针因为记录两个指针要占用16个字节浪费内存。而是采用了下面的结构 previous_entry_length前一节点的长度占1个或5个字节。 如果前一节点的长度小于254字节则采用1个字节来保存这个长度值如果前一节点的长度大于254字节则采用5个字节来保存这个长度值第一个字节为0xfe后四个字节才是真实长度数据 encoding编码属性记录content的数据类型字符串还是整数以及长度占用1个、2个或5个字节 contents负责保存节点的数据可以是字符串或整数 ZipList中所有存储长度的数值均采用小端字节序即低位字节在前高位字节在后。例如数值0x1234采用小端字节序后实际存储值为0x3412 Encoding编码
ZipListEntry中的encoding编码分为字符串和整数两种
字符串如果encoding是以“00”、“01”或者“10”开头则证明content是字符串
编码编码长度字符串大小|00pppppp|1 bytes 63 bytes|01pppppp|qqqqqqqq|2 bytes 16383 bytes|10000000|qqqqqqqq|rrrrrrrr|ssssssss|tttttttt|5 bytes 4294967295 bytes
例如我们要保存字符串“ab”和 “bc” 整数如果encoding是以“11”开始则证明content是整数且encoding固定只占用1个字节
编码编码长度整数类型110000001int16_t2 bytes110100001int32_t4 bytes111000001int64_t8 bytes11110000124位有符整数(3 bytes)1111111018位有符整数(1 bytes)1111xxxx1直接在xxxx位置保存数值范围从0001~1101减1后结果为实际值 ZipList的连锁更新问题
ZipList的每个Entry都包含previous_entry_length来记录上一个节点的大小长度是1个或5个字节
如果前一节点的长度小于254字节则采用1个字节来保存这个长度值如果前一节点的长度大于等于254字节则采用5个字节来保存这个长度值第一个字节为0xfe后四个字节才是真实长度数据
现在假设我们有N个连续的、长度为250~253字节之间的entry因此entry的previous_entry_length属性用1个字节即可表示如图所示 ZipList这种特殊情况下产生的连续多次空间扩展操作称之为连锁更新Cascade Update。新增、删除都可能导致连锁更新的发生。 举一个例子 如上图有 entryX-1 512字节entryX 128字节entryX1 253字节entryX2 253 字节。 由于 entryX 元素长度为 128 字节那么 entryX 1 元素的 prevlen 的元素的长度就只要 1 个字节就可以了。 这个时候在 entryX 和 entryX1 之间加了一个 entryNew 元素这个元素长度是 1024 字节那么这个时候 entryX1 中的 prevlen 就需要变成 5 个字节了。注意后面的元素可能也要进行更新。 当删除 entryX 的时候entryX1 的 prevlen 就变成了 5 字节那么 entryX1 的长度就变成了 257 字节又导致后面进行更新这种叫做连锁更新。 由于每次扩展都将重新分配内存导致效率很低当更新到一次不变时那么就不向后检查了。比如说后面有一个 entryX3 为 100 字节那么就不会进行检查了。 小总结
ZipList特性
压缩列表的可以看做一种连续内存空间的双向链表列表的节点之间不是通过指针连接而是记录上一节点和本节点长度来寻址内存占用较低如果列表数据过多导致链表过长可能影响查询性能增或删较大数据时有可能发生连续更新问题
QuickList
问题1ZipList虽然节省内存但申请内存必须是连续空间如果内存占用较多申请内存效率很低。怎么办
答为了缓解这个问题我们必须限制ZipList的长度和entry大小。
问题2但是我们要存储大量数据超出了ZipList最佳的上限该怎么办
答我们可以创建多个ZipList来分片存储数据。
问题3数据拆分后比较分散不方便管理和查找这多个ZipList如何建立联系
答Redis在3.2版本引入了新的数据结构QuickList它是一个双端链表只不过链表中的每个节点都是一个ZipList。 为了避免QuickList中的每个ZipList中entry过多Redis提供了一个配置项list-max-ziplist-size来限制。 如果值为正则代表ZipList的允许的entry个数的最大值 如果值为负则代表ZipList的最大内存大小分5种情况 -1每个ZipList的内存占用不能超过4kb-2每个ZipList的内存占用不能超过8kb-3每个ZipList的内存占用不能超过16kb-4每个ZipList的内存占用不能超过32kb-5每个ZipList的内存占用不能超过64kb
其默认值为 -2
以下是QuickList的和QuickListNode的结构源码 我们接下来用一段流程图来描述当前的这个结构 总结
QuickList的特点
是一个节点为ZipList的双端链表节点采用ZipList解决了传统链表的内存占用问题控制了ZipList大小解决连续内存空间申请效率问题中间节点可以压缩进一步节省了内存
SkipList
SkipList跳表首先是链表但与传统链表相比有几点差异
元素按照升序排列存储节点可能包含多个指针指针跨度不同。 如何理解跳表在了解跳表之前我们先从普通链表开始一点点揭开跳表的神秘面纱~
首先普通单链表来说即使链表是有序的我们要查找某个元素也需要从头到尾遍历整个链表。这样效率很低时间复杂度是O(n)。 那么有没有方法提升查询效率呢我们可以尝试为链表建立“索引”来提升查询效率。如下图我们在原始链表的基础上每两个元素提取一个索引down指向原始链表的节点 此时假如我们要查询值为19的节点我们从索引层开始遍历当遍历到16时下个节点的值为23所以19一定在这两个节点之间。我们通过16节点的down指针来到原始链表将继续遍历直到找到值为19的节点。在没有建“索引”之前我们需要遍历8次才能找到19而在建立“索引”后需要6次就能找到也就是索引帮我们减少了查询的次数。
那如果我们再建一级索引呢哈哈哈没想到吧也是6次这是因为我们的数据量太少即便加了两级索引优化效果也不是很明显。在数据量大时优化效果还是很明显的有兴趣可以自己动手画一画。 这种查找跟二分查找的时间复杂度一样O(log2n)。换句话说我们是基于单链表实现了二分查找。但是这种查询效率的提升是有代价的也就是我们需要维护多层级索引才能实现。这也是一种空间换时间的思路。 跳表的插入和删除
我们想在跳表中插入和删除一个节点第一步是要找到插入和删除的位置然后再执行插入或者删除因为跳表的查询时间复杂度是O(log2n)插入和删除的时间复杂度也是O(log2n)。插入 删除操作就需要注意一下如果删除的节点也存在于索引节点中那么索引中的节点也要删除。单链表中的删除需要拿到前驱节点的指针如果是双向链表就不用考虑了。
跳表索引的动态更新
当我们一直往跳表中添加元素如果不更新索引就可能出现某2个索引之间的索引数过多极端情况下会退化为单向链表。
作为一种动态数据结构我们需要某种手段作为索引节点和原始链表大小的平衡也就是说当链表中的节点数增多时也响应的增加一些索引节点避免复杂度的退化。红黑树和AVL树是通过左旋和右旋来维持左右子树的平衡。
而跳表是一种 probabilistic 数据结构,它通过随机决定每个元素的层数,来保证整个跳表的平衡。具体做法是:
当插入一个新元素时,Redis会随机决定它的层数,层数可以是1层,2层,3层,直到最大层数。层数的随机分布遵循几何分布,层数越高,其出现的概率越低。 举例来说,如果我们设置最大层数为5,那么:
层数为1的概率50%层数为2的概率25%层数为3的概率12.5%层数为4的概率6.25%层数为5的概率3.125%
从这个分布可以看出,层数越高的元素出现的概率会显著下降。这就使得高层元素较为“稀疏”,而低层较为“密集”。
这样,高层元素就像是跳表的快速通道,用于快速遍历和查找。而低层则包含更丰富的元素,可以精确查找每一个元素。
这种随机分布的层数,显著减少了跳表的倾斜几率,使其总体来说是均衡的。因为高层元素较稀疏,所以遍历和查找能够快速跳过大量低层元素,获得较高性能。
而相比AVL树和红黑树等平衡树,跳表的随机性使其逻辑更简单,无须进行频繁旋转来维持平衡,这也使其性能更高。这也是Redis选择跳表的一个重要原因。
总之,跳表通过为每个新元素随机分配层数,来保证其总体平衡。层数遵循几何分布,高层较稀疏,低层较密集。这使得跳表既有快速查找的能力,也可以精确访问每个元素。 跳表源码结构 小总结
SkipList的特点
跳跃表是一个双向链表每个节点都包含score和ele值节点按照score值排序score值一样则按照ele字典排序每个节点都可以包含多层指针层数是1到32之间的随机数不同层指针到下一个节点的跨度不同层级越高跨度越大增删改查效率与红黑树基本一致实现却更简单
RedisObject
redisObject是一个C语言构造,所有的Redis对象的数据类型以及值都存储在这个结构中。我们平时操作的字符串、列表、散列等对象,其内部实现全部用redisObject来构造的。
举个例子,一个Redis字符串对象在内存中大致结构如下:
redisObject- type: REDIS_STRING - encoding: REDIS_ENCODING_EMBSTR - ptr: 指向embstr字符串结构
embstr- size: 字符串长度- buf: char数组,保存字符串值 redisObject是一个非常轻量级的结构,里面只包含必要的字段,这使得Redis可以创建和销毁对象的代价非常低,这也是Redis可以达到亚秒级响应的原因之一。
同时,将不同对象通过type字段区分,encoding字段指定值的具体存储结构,这使得Redis的对象系统非常灵活和易扩展。Redis可以很容易地添加新的数据类型。
redisObject源码 Redis的编码方式
Redis中会根据存储的数据类型不同选择不同的编码方式共包含11种不同类型
编号编码方式说明0OBJ_ENCODING_RAWraw编码动态字符串1OBJ_ENCODING_INTlong类型的整数的字符串2OBJ_ENCODING_HThash表字典dict3OBJ_ENCODING_ZIPMAP已废弃4OBJ_ENCODING_LINKEDLIST双端链表5OBJ_ENCODING_ZIPLIST压缩列表6OBJ_ENCODING_INTSET整数集合7OBJ_ENCODING_SKIPLIST跳表8OBJ_ENCODING_EMBSTRembstr的动态字符串9OBJ_ENCODING_QUICKLIST快速列表10OBJ_ENCODING_STREAMStream流
五种数据结构
Redis中会根据存储的数据类型不同选择不同的编码方式。每种数据类型的使用的编码方式如下
数据类型编码方式OBJ_STRINGint、embstr、rawOBJ_LISTLinkedList和ZipList(3.2以前)、QuickList3.2以后OBJ_SETintset、HTOBJ_ZSETZipList、HT、SkipListOBJ_HASHZipList、HT String
String是Redis中最常见的数据存储类型
底层实现⽅式动态字符串SDS或者 Long 其基本编码方式是RAW基于简单动态字符串SDS实现存储上限为512MB。 如果存储的SDS长度小于44字节则会采用EMBSTR编码此时object head与SDS是一段连续空间。申请内存时只需要调用一次内存分配函数效率更高。 如果存储的字符串是整数值并且大小在LONG_MAX范围内则会采用INT编码直接将数据保存在RedisObject的ptr指针位置刚好8字节不再需要SDS了。 确切地说String在Redis中是⽤⼀个robj来表示的。 用来表示String的robj可能编码成3种内部表⽰OBJ_ENCODING_RAWOBJ_ENCODING_EMBSTROBJ_ENCODING_INT。
其中前两种编码使⽤的是SDS来存储最后⼀种OBJ_ENCODING_INT编码直接把string存成了Long型。
在对string进行incr, decr等操作的时候如果它内部是OBJ_ENCODING_INT编码那么可以直接行加减操作如果它内部是OBJ_ENCODING_RAW或OBJ_ENCODING_EMBSTR编码那么Redis会先试图把SDS存储的字符串转成Long型如果能转成功再进行加减操作。
对⼀个内部表示成Long型的string执行append, setbit, getrange这些命令针对的仍然是string的值即十进制表示的字符串而不是针对内部表⽰的long型进⾏操作。
比如字符串”32”如果按照字符数组来解释它包含两个字符它们的ASCII码分别是0x33和0x32。当我们执行命令setbit key 7 0的时候相当于把字符0x33变成了0x32这样字符串的值就变成了”22”。⽽如果将字符串”32”按照内部的64位long型来解释那么它是0x0000000000000020在这个基础上执⾏setbit位操作结果就完全不对了。因此在这些命令的实现中会把long型先转成字符串再进行相应的操作。
List
Redis的List类型可以从首、尾操作列表中的元素 哪一个数据结构能满足上述特征
LinkedList 普通链表可以从双端访问内存占用较高内存碎片较多ZipList 压缩列表可以从双端访问内存占用低存储上限低QuickListLinkedList ZipList可以从双端访问内存占用较低包含多个ZipList存储上限高
Redis的List结构类似一个双端链表可以从首、尾操作列表中的元素
在3.2版本之前Redis采用ZipList和LinkedList来实现List当元素数量小于512并且元素大小小于64字节时采用ZipList编码超过则采用LinkedList编码。
在3.2版本之后Redis统一采用QuickList来实现List Set结构
Set是Redis中的单列集合满足下列特点
不保证有序性保证元素唯一求交集、并集、差集 可以看出Set对查询元素的效率要求非常高思考一下什么样的数据结构可以满足
HashTable也就是Redis中的Dict不过Dict是双列集合可以存键、值对
Set是Redis中的集合不一定确保元素有序可以满足元素唯一、查询效率要求极高。
为了查询效率和唯一性set采用HT编码Dict。Dict中的key用来存储元素value统一为null。
当存储的所有数据都是整数并且元素数量不超过set-max-intset-entries时Set会采用IntSet编码以节省内存 结构如下
ZSET
ZSet也就是SortedSet其中每一个元素都需要指定一个score值和member值
可以根据score值排序后member必须唯一可以根据member查询分数 因此zset底层数据结构必须满足键值存储、键必须唯一、可排序这几个需求。之前学习的哪种编码结构可以满足
SkipList可以排序并且可以同时存储score和ele值memberHTDict可以键值存储并且可以根据key找value 当元素数量不多时HT和SkipList的优势不明显而且更耗内存。因此zset还会采用ZipList结构来节省内存不过需要同时满足两个条件
元素数量小于zset_max_ziplist_entries默认值128每个元素都小于zset_max_ziplist_value字节默认值64
ziplist本身没有排序功能而且没有键值对的概念因此需要有zset通过编码实现
ZipList是连续内存因此score和element是紧挨在一起的两个entry element在前score在后score越小越接近队首score越大越接近队尾按照score值升序排列 Hash
Hash结构与Redis中的Zset非常类似
都是键值存储都需求根据键获取值键必须唯一
区别如下
zset的键是member值是scorehash的键和值都是任意值zset要根据score排序hash则无需排序
1底层实现方式压缩列表ziplist 或者 字典dict 当Hash中数据项比较少的情况下Hash底层才⽤压缩列表ziplist进⾏存储数据随着数据的增加底层的ziplist就可能会转成dict具体配置如下 hash-max-ziplist-entries 512 hash-max-ziplist-value 64
当满足上面两个条件其中之⼀的时候Redis就使⽤dict字典来实现hash。 Redis的hash之所以这样设计是因为当ziplist变得很⼤的时候它有如下几个缺点
每次插⼊或修改引发的realloc操作会有更⼤的概率造成内存拷贝从而降低性能。⼀旦发生内存拷贝内存拷贝的成本也相应增加因为要拷贝更⼤的⼀块数据。当ziplist数据项过多的时候在它上⾯查找指定的数据项就会性能变得很低因为ziplist上的查找需要进行遍历。
总之ziplist本来就设计为各个数据项挨在⼀起组成连续的内存空间这种结构并不擅长做修改操作。⼀旦数据发⽣改动就会引发内存realloc可能导致内存拷贝。
hash结构如下 zset集合如下 因此Hash底层采用的编码与Zset也基本一致只需要把排序有关的SkipList去掉即可
Hash结构默认采用ZipList编码用以节省内存。 ZipList中相邻的两个entry 分别保存field和value
当数据量较大时Hash结构会转为HT编码也就是Dict触发条件有两个
ZipList中的元素数量超过了hash-max-ziplist-entries默认512ZipList中的任意entry大小超过了hash-max-ziplist-value默认64字节
