Redis核心数据结构之压缩列表(二)

压缩列表

压缩列表节点的构成

encoding

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

  • 1.一字节、两字节或者五字节长,值得最高位为00、01或者10的是字节数组编码:这种编码表示节点的content属性保存着字节数组,数组的长度由编码除去最高两位之后的其他位记录
  • 2.一字节长,值得最高位以11开头的是整数编码:这种编码表示节点的content属性保存着整数值,整数值的类型和长度由编码出去最高两位之后的其他位记录
    在这里插入图片描述
    在这里插入图片描述

content

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

例子

在这里插入图片描述
举个例子,图中展示了一个保存字节数组的节点示例

  • 1.编码的最高两位00表示节点保存的是一个字节数组
  • 2.编码的后六位001011记录了字节数组的长度11;
  • 3.content属性保存着节点值"hello world"

另一个例子。图中展示了一个保存整数值的节点示例

  • 1.编码11000000表示节点保存的是一个int16_t类型的整数值
  • 2.content属性保存着节点的值10086
    在这里插入图片描述

连锁更新

每个节点的previous_entry_length属性都记录了前一个节点的长度:

  • 1.如果前一节点的长度小于254字节,那么previous_entry_length属性需要用1字节长的空间来保存这个长度值
  • 2.如果前一节点的长度大于等于254字节,那么previous_entry_length属性需要用5字节长的空间来保存这个长度值现在,考虑这样一种情况:在一个压缩列表中,有多个连续的、长度介于250字节到253字节之间的节点e1至eN,如图所示。因为e1至eN的所有节点的长度都小于254字节,所以记录这些节点的长度只需要1字节长的previous_entry_length属性,换句话说,e1至eN的所有节点的previous_entry_length属性都是1字节长。这时,如果将一个长度大于等于254字节的新节点new设置为压缩列表的表头节点,那么new将称为e1的前置节点
    在这里插入图片描述
    在这里插入图片描述
    因为e1的previous_entry_length属性仅长1字节,它没有办法保存新节点new的长度,所以程序将对压缩列表执行空间重分配操作,并将e1节点的previous_entry_length属性从原来的1字节长扩展为5字节长。
    现在,麻烦的事情来了,e1原本的长度介于250字节至253字节之间,在为previous_entry_length属性新增四个字节的空间之后,e1的长度就变成了介于254字节至257字节之间,而这种长度使用1字节长的previous_entry_length属性是没法保存的。因此,为了让e2的previous_entry_length属性可以记录下e1的长度,程序需要再次对压缩列表执行空间重分配操作,并将e2节点的previous_entry_length属性从原来的1字节长扩展为5字节长.正如扩展e1引发对e2的扩展一样,扩展e2也会引发对e3的扩展,而扩展e3又会引发对e4的扩展…为了让每个节点的previous_entry_length属性都符合压缩列表对节点的要求,程序需要不断地对压缩列表执行空间重分配操作,直到eN为止
    在这里插入图片描述
    除了添加新节点可能会引发连锁更新之外,删除节点也可能会引发连锁更新
    在这里插入图片描述
    如图所示的压缩列表,如果e1至eN都是大小介于250字节至253字节的节点。big节点的长度大于等于254字节(需要5字节的previous_entry_length来保存),而small节点的长度小于254字节(只需要1字节的previous_entry_length来保存),那么当我们将small节点从压缩列表中删除之后,为了让e1的previous_entry_length属性可以记录big节点的长度,程序将扩展e1的空间,并由此引发之后的连锁更新。因为连锁更新在最坏情况下需要第压缩列表执行N次空间重分配操纵,而每次空间重分配的最坏复杂度为O(N),所以连锁更新的最坏复杂度为O(N^2).要注意的是,尽管连锁更新的复杂度较高,但它真正造成性能问题的几率是很低的:
  • 1,首先,压缩列表里要恰好有多个连续的,长度介于250字节至253字节之间的节点,连锁更新才有可能触发,在实际情况中,这种情况并不多见
  • 2.其次,即时出现连锁更新,但只要被更新的节点数量不多,就不会对性能造成任何影响:比如说,对三五个节点进行连锁更新是绝对不会影响性能的

因为以上原因,ziplistPush等命令的平均复杂度仅为O(N),在实际中,可以放心地使用这些函数,而不必担心连锁更新会
影响压缩列表的性能

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/451670.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

【Python】random库

专栏文章索引:Python 原文章:Python中random函数用法整理_python random-CSDN博客 目录 1.random.random() 2.random.uniform(a, b) 3.random.randint(a, b) 4.random.randrange([start], stop[, step]) 5. random.choice() 6. random.shuffle(x[,…

【每日八股】Java基础中面试你必须要掌握问题1

🔥 个人主页: 黑洞晓威 😀你不必等到非常厉害,才敢开始,你需要开始,才会变的非常厉害。## 如何解决浮点数运算的精度丢失问题? BigDecimal 可以解决精度问题的原因在于它是一个精确的十进制数学运算类&…

idea中设置字段唯一,后台做出提示(springboot项目)

在项目中,我们通常需要对某些字段做字段唯一的限制,保证在数据库中该字段对应的值不能出现重复的值,接下来看看怎么做吧~ 数据库中可以同时设置几个字段的unique,就比如用户在进行注册的时候,一个用户只能对应一个电话…

爬虫入门到精通_框架篇14(PySpider架构概述及用法详解)

官方文档 Sample Code: from pyspider.libs.base_handler import *class Handler(BaseHandler):crawl_config {}# minutes24 * 60:每隔一天重新爬取every(minutes24 * 60)def on_start(self):self.crawl(http://scrapy.org/, callbackself.index_page)…

week07day01(powerbi)

一. Power BI简介 1. 构成部分 power query: 进行简单的数据清洗power pivot : 进行指标计算power view : 进行报表视图 二. Power Query (进行数据清洗) 1. 如何获取数据: 点击获取数据 ——> 选择导入数据的类型——> 会出现 "加载&…

【刷题日志3.4--3.10】

绕过flag关键字od读取&#xff08;脚本&#xff09;空格过滤 [广东强网杯 2021 团队组]love_Pokemon <?php error_reporting(0); highlight_file(__FILE__); $dir sandbox/ . md5($_SERVER[REMOTE_ADDR]) . /;if(!file_exists($dir)){mkdir($dir); }function DefenderBon…

Pytorch搭建AlexNet 预测实现

1.导包 import torch import matplotlib.pyplot as plt import json from model import AlexNet from PIL import Image from torchvision import transforms 2.数据预处理 data_transform transforms.Compose([transforms.Resize((224, 224)), # 将图片重新裁剪transform…

【Android】 ClassLoader 知识点提炼

1.Java中的 ClassLoader 1.1 、ClassLoader的类型 Java 中的类加载器主要有两种类型&#xff0c;即系统类加载器和自定义类加载器。其中系统类 加载器包括3种&#xff0c;分别是 Bootstrap ClassLoader、Extensions ClassLoader 和 Application ClassLoader。 1.1.1.Bootstra…

uniapp开发DAPP钱包应用(二) Vue + Java

上一节我们讲了如何通过vue uniapp还有web3以及需要准备的相关组件&#xff0c;来搭建了DAPP开发的环境。 这一节&#xff0c;我们来说说如何用代码来实现DAPP相关接口。 1. ethers实现类 导入组件 import { ethers , providers , utils } from "ethers"; impor…

QML 控件添加键盘事件

在QML中&#xff0c;可以使用Keys类型来处理键盘事件。以下是一个简单的示例&#xff0c;演示如何在QML控件中添加键盘事件&#xff1a; import QtQuick 2.12 import QtQuick.Window 2.12Window {visible: truewidth: 640height: 480title: qsTr("Hello World")Recta…

DFS算法详解及例题

DFS:往深搜索&#xff0c;执着&#xff0c;确认从底下返回后的每个人的节点都已经用完&#xff0c;空间占用少&#xff0c;爆搜。 BFS:每一层搜索&#xff0c;稳重&#xff0c;(当一个图的权重都为1时搜到的一定是最短路) 下面我们以dfs的一道经典例题来讲解 代码: #include…

Ubuntu18.04 安装搜狗输入法

一. 概述 自己的Ubuntu 18.04系统配置中文搜狗输入法&#xff0c;安装步骤&#xff0c;亲测可用 二. 安装步骤 2.1 确认系统版本和CPU架构 查看Ubuntu系统版本号&#xff0c;通过命令 lsb_release -a wuubuntume:~$ lsb_release -a No LSB modules are available. Distr…

基于SpringBoot的“智慧食堂”系统(源码+数据库+文档+PPT)

基于SpringBootVue的智慧食堂系统的设计与实现&#xff08;源码数据库文档PPT) 开发语言&#xff1a;Java数据库&#xff1a;MySQL技术&#xff1a;SpringBootVUE工具&#xff1a;IDEA/Ecilpse、Navicat、Maven 系统展示 系统登录界面图 系统首页界面图 用户注册界面图 菜…

项目总结.

文章目录 1.DDD结构基础2. 抽奖领域3. 发奖领域4.活动领域5. 支撑领域应用层编排 1.DDD结构基础 包含&#xff1a; 接口层、应用层、领域层、基础层&#xff1b;通用包、接口层、接口定义。 接口层&#xff1a;实现RPC接口定义&#xff0c;引入应用层服务&#xff0c;封装具体的…

日期问题 刷题笔记

思路 枚举 19600101 到20591231这个区间的数 获得年月日 判断是否合法 如果合法 关于题目给出的日期 有三种可能 年/月/日 日/月/年 月/日/年 判断 是否和题目给出的日期符合 如果符合 输出 闰年{ 1.被4整除不被100整除 2.被400整除} 补位写法“%02d" 如果不…

【C语言步行梯】自定义函数、函数递归详谈

&#x1f3af;每日努力一点点&#xff0c;技术进步看得见 &#x1f3e0;专栏介绍&#xff1a;【C语言步行梯】专栏用于介绍C语言相关内容&#xff0c;每篇文章将通过图片代码片段网络相关题目的方式编写&#xff0c;欢迎订阅~~ 文章目录 什么是函数库函数自定义函数函数执行示例…

STM32 ADC数模转换器

单片机学习&#xff01; 目录 文章目录 前言 一、ADC简介 1.1 ADC名称 1.2 ADC功能 1.3 分辨率与转换时间 1.4 输入电压与转换范围 1.5 输入通道 1.6 增强功能 1.7 自动监测输入电压范围 1.8 STM32F103C8T6 ADC资源 二、逐次逼近型ADC 2.1 ADC内部结构原理图 2.2 输入通道选择 …

AI 驱动的医疗变革:迈向未来医疗新生态

直面呼啸而来的人工智能&#xff0c;医疗行业将首当其冲&#xff0c;发生翻天覆地的变化。美国心脏病学家兼基因学教授埃里克托普在《未来医疗》中预测&#xff0c;未来人类将拥有“健康小助手”——个人医疗数据和处理能力&#xff0c;还能轻松预防疾病。诸多评论家也持类似观…

Jade 处理XRD并计算半峰宽FWHM、峰面积、峰强度等数据

1.打开软件 2.导入测试的XRD数据 3.平滑数据 4.抠一下基底 5.分析具体数据 6.按住鼠标左键&#xff0c;在峰底部拉一条线&#xff0c;尽量和基底持平 7.结果就出来了&#xff0c;想要的都在里面&#xff0c;直接取值就行

数据分析-Pandas如何观测数据的中心趋势度

数据分析-Pandas如何观测数据的中心趋势度 数据分析和处理中&#xff0c;难免会遇到各种数据&#xff0c;那么数据呈现怎样的规律呢&#xff1f;不管金融数据&#xff0c;风控数据&#xff0c;营销数据等等&#xff0c;莫不如此。如何通过图示展示数据的规律&#xff1f; 数据…