Redis数据结构三之压缩列表

这篇具有很好参考价值的文章主要介绍了Redis数据结构三之压缩列表。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

本文首发于公众号:Hunter后端
原文链接:Redis数据结构三之压缩列表

本篇笔记介绍压缩列表。

在 Redis 3.2 版本之前,压缩列表是列表对象、哈希对象、有序集合对象的的底层实现之一。

因为压缩列表本身结构上的一些缺陷,压缩列表这个结构被替换了,但是压缩列表结构本身有一些可取之处,并且替换它的新结构 listpack 与之很相似,所以我们这里还是介绍一下压缩列表的结构和存储

1、压缩列表的结构

压缩列表是 Redis 为了节约内存而开发的,由一个连续内存块组成的顺序型数据结构。

它的组成结构如下:

| zlbytes | zltail | zllen | entry1 | entry2 | ... | entryN | zlend |

压缩列表的英文名是 ziplist,所以它的属性都是 zl 开头。

1. 列表属性介绍

zlbytes

zlbytes 长度为 4 字节,记录整个压缩列表占用的内存字节数

zltail

zltail 长度为 4 字节,记录压缩列表最后一个节点,也就是我们结构示例中的 entryN 到 zlbytes 的地址之间的偏移量。

zllen

zllen 长度为 2 字节,记录的是压缩列表包含的节点数量,也就是结构中的 N。

zlend

zlend 长度为 1 字节,它的值为 0xFF(十进制 255),用于标记压缩列表的末端。

2. 压缩列表节点属性介绍

对于每一个 entry 节点,也就是压缩列表中的元素节点,它的结构示意如下:

| previous_entry_length | encoding | content |

previous_entry_length

previous_entry_length 属性记录的是压缩列表中前一个节点的长度

previous_entry_length 属性本身的长度可以是 1 字节或者 5 字节

如果前一节点的长度小于 254 字节,那么 previous_entry_length 属性的长度为 1 字节,前一个节点的长度保存在这个字节里

如果前一节点的长度大于等于 254 字节,那么 previous_entry_length 属性的长度为 5 字节,第一个字节被设置成 0xFE(也就是 254),之后的四个字节用于前一节点的长度。

通过 previous_entry_length 属性,我们可以通过当前节点的地址和 previous_entry_length 属性,计算出前一个节点的起始地址,压缩列表的从表尾到表头的遍历操作就是使用这个原理一个节点一个节点往前回溯实现的。

encoding

encoding 属性记录了节点的 content 属性所保存数据的类型以及长度。

encoding 的值如果是一字节长,且值的最高位以 11 开头,那么表示是整数编码,表示 content 属性保存着整数值。

encoding 的值为 一字节、两字节、五字节长,且值的最高位为 00、01、10 则表示是字节数组编码

content

content 属性保存的是节点的值,可以是一个字节数组或者整数,值的类型和长度由节点的 encoding 属性决定。

2、 连锁更新

在压缩列表的节点属性中,previous_entry_length 属性的长度是根据前一节点的长度来进行赋值的,如果前一节点的长度小于 254 字节,那么下一节点的 previous_entry_length 属性长度为 1 字节,如果前一节点的长度大于等于 254 字节,那么下一节点的 previous_entry_length 属性为 5 字节。

那么在这种情况下,就存在一种较为极端的情况,那就是压缩列表中每个节点的长度都在 250 - 253 字节之间,这时候,如果在表头插入一个长度大于等于 254 字节的节点,那么相对应的第二个节点的 previous_entry_length 的长度就要从 1 字节变为 4 字节,那么该节点的整体长度就大于等于 254 字节。

依此类推,压缩列表的每一个节点的长度都会产生连锁反应,长度都会逐个变成大于等于 254 字节长度,程序就需要不断地对压缩列表执行空间重分配的操作。

Redis 将这种在特殊情况下产生的连续多次空间扩展操作称为连锁更新。

除了新增节点这种情况,还有一种删除节点也可能造成连锁更新的情况,比如有这么几个节点,big 节点的长度大于等于 254 字节,small 节点长度小于254 字节,e1 到 eN 的节点长度都在 250-253 字节之间。

| zlbytes | zltail | zllen | big | small | entry1 | entry2 | ... | entryN | zlend |

这时候,删除 small 节点,entry1 节点的前节点的长度就会从 250-253 变成大于等于 254,因此 entry1 节点的 previous_entry_length 长度就会变成 5 字节,entry1 整体长度就会大于等于 254 字节,依次之后每个节点都会这样产生连锁更新。

尽管连锁更新的复杂度较高,但它真正造成性能问题的几率是很低的:

首先,压缩列表里要恰好有多个连续的、长度介于 250-253 字节之间的节点,连锁反应才有可能被引发

其次,即使出现连锁更新,但只要被更新的节点数量不多,就不会对性能造成任何影响,比如对只拥有三五个节点的压缩列表进行连锁更新。

3、压缩列表缺点

压缩列表虽然能节约内存,但仍然存在一些缺点:

  • 需要通过遍历操作来查找节点,元素过多时会造成查询效率低下
  • 对压缩列表节点进行新增或者修改时,可能会造成连锁更新的问题

如果想获取更多后端相关文章,可扫码关注阅读:
Redis数据结构三之压缩列表文章来源地址https://www.toymoban.com/news/detail-448172.html

到了这里,关于Redis数据结构三之压缩列表的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • Redis数据结构——快速列表quicklist、快表

    Redis中的数据结构,链表和压缩列表这两种数据结构是列表对象的底层实现方式。 当时考虑到链表的附加空间太大,节点的内存都是单独分配的,还会导致内存碎片化问题严重。 因此从Redis3.2开始,对列表的底层数据结构进行了改造,即使用 quickList代替链表list和压缩列表z

    2024年02月12日
    浏览(39)
  • 【数据结构】C--顺序表1.0版本(本文非常适合小白观看,已尽力详解,以及图解也是尽量列举)

    目录 0.前言 什么是数据结构? 1.逻辑结构: 1.1线性结构: 1.2非线性结构:         (1)集合         (2)树形结构         (3)图形结构或者网状结构 2.存储结构 一.线性表 二.顺序表 顺序表与数组的关系:(非常容易混淆) 1.静态顺序表:使用定长数组存储元素 2.动态顺序表

    2024年02月06日
    浏览(57)
  • 【数据结构】矩阵的压缩存储

    5.1 普通矩阵的存储 用二维数组存储 分为行优先和列优先: 行优先:优先存放一行的数据。 列优先:优先存放一列的数据。 注意下标是从0还是1开始的! 5.2 对称矩阵的存储 对称矩阵定义 若n阶方阵中任意一个元素 a i , j a_{i,j} a i , j ​ 都有 a i , j = a j , i a_{i,j}=a_{j,i} a i , j

    2024年03月18日
    浏览(57)
  • 【数据结构】特殊矩阵的压缩存储

    🌈 自在飞花轻似梦,无边丝雨细如愁 🌈   🌟 正式开始学习数据结构啦~此专栏作为学习过程中的记录 🌟 数组是由n个相同类型的数据元素所构成的有限序列 数组和线性表的关系: 数组是线性表的推广:一维数组可以看做是一个线性表,而对于二维数组而言,可以看成是有

    2024年02月11日
    浏览(48)
  • 数据结构--特殊矩阵的压缩存储

    各数组元素大小相同,且物理上连续存放。 数组元素a[i]的存放地址= LOC + i * sizeof(ElemType) ( 0 ≤ i 10 ) (0le i 10) ( 0 ≤ i 10 ) 注:除非题目特别说明,否则数组 下标默认从 0 开始 color{red}下标默认从0开始 下标默认从 0 开始 注意审题 ! 易错 ! color{purple}注意审题!易错! 注意审题

    2024年02月16日
    浏览(61)
  • 数据结构(五)----特殊矩阵的压缩存储

    目录 1.一维数组的存储结构 2.二维数组的存储结构 3.普通矩阵的存储 4.特殊矩阵的压缩存储 (1)对称矩阵 (2)三角矩阵 (3)三对角矩阵 (4)稀疏矩阵的压缩存储 1.一维数组的存储结构 一维数组的定义如下: ElemType a[10]; 各数组元素大小相同,且物理上连续存放。 数组元

    2024年04月28日
    浏览(39)
  • Python数据结构与算法-数据结构(列表、栈、队列、链表)

    数据结构是指相互之间存在这一种或者多种关系的数据元素的集合和该集合中元素之间的关系组成。 简单来说,数据结构就是设计数据以何种方式组织并存储在计算机中。 比如:列表、集合与字典等都是一种数据结构。 N.Wirth:“程序=数据结构+算法” 数据结构按照其 逻辑结

    2024年02月08日
    浏览(58)
  • 数据结构基础--散列表

    散列表,又叫 哈希表 (Hash Table),是能够通过给定的的值直接访问到具体对应的值的一个数据结构。也就是说,把映射到一个表中的位置来直接访问记录,以加快访问速度。 通常,把这个称为 Key,把对应的记录称为 Value,所以也可以说是通过 Key 访问

    2024年02月04日
    浏览(45)
  • 【考研】数据结构——特殊矩阵的压缩存储(含真题)

    本文内容源于对《数据结构(C语言版)》(第2版)、王道讲解学习所得心得、笔记整理和总结。 本文主要以举例子的方式讲解考研选择题型中的特殊矩阵的压缩存储知识点,配以图文(含408真题)。 可搭配以下链接进行学习: 【2023考研】数据结构常考应用典型例题(含真

    2024年02月03日
    浏览(53)
  • 哈希表-散列表数据结构

    哈希表也叫散列表,哈希表是根据关键码值(key value)来直接访问的一种数据结构,也就是将关键码值(key value)通过一种映射关系映射到表中的一个位置来加快查找的速度,这种映射关系称之为哈希函数或者散列函数,存放记录的数组称之为哈希表。 哈希表采用的是一种转换思

    2024年01月21日
    浏览(56)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包