Redis数据结构——跳跃表

跳跃表

先来回顾常规的跳跃表。
!!!下面的图片和内容都来自于这个链接Redis数据结构——跳跃表 - 随心所于 - 博客园

对于一个有序的链表,我们如何才能快速定位一个元素呢?只能遍历,时间复杂度是O(N),效率非常低。

既然链表是有序的,我们就可以建立索引,在上一层维护一个索引,也是链表的形式

当我们要查找元素8时,先通过索引定位到8在7和9之间,那么我们直接在7和9之间遍历可以找到。
当元素数量更多时,我们还可以继续向上抽取索引,查询效率明显提升。

这种通过为链表维护多级索引的结构,就是跳跃表
在链表上建立索引,虽然需要占用额外的空间来维护索引,但是对于元素数量非常多时,这些索引占用的空间就不那么重要了,是空间换时间的思想。

Redis中的跳跃表

跳跃表skiplist是一种有序的数据结构,通过在每个节点中维持多个指向其他节点的指针,从而达到快速访问节点的目的。
在大部分情况下,跳跃表的效率可以媲美平衡树(AVL树),并且跳跃表的实现比平衡树更简单。
跳跃表是有序集合底层的实现方式之一,如果一个有序集合中包含的元素数量比较多,或者有序集合中的元素是比较长的字符串时,Redis就会使用跳跃表来作为有序集合的实现方式

实现

简单点说,在Redis中,每个节点都包含若干层,每一层就是一级索引。

在Redis中,跳跃表是由zskiplistNode和zskiplist两个结构定义:

  • zskiplistNode表示一个节点。
  • zskiplist记录整个跳跃表的信息,例如头节点、尾节点、层级

    最左侧的蓝色结构就是zskiplist,该结构包含以下属性:
  • header:指向跳跃表的头结点
  • tail:指向跳跃表的尾节点
  • level:记录目前跳跃表内,最大的层数,即顶级索引所在的层数
  • length:跳跃表的长度,即跳跃表目前包含节点的数量(表头节点不计入)

zskiplistNode结构,包含以下属性:

  • 层level:L1表示第一层,L2表示第二层,以此类推。每一层都有两个属性:前进指针和跨度
    • 前进指针用于访问位于表尾方向的其他节点
    • 跨度记录了前进指针所指向的节点与当前节点的距离。
  • 后退指针bw:指向位于当前节点的前一个节点,后退指针在从尾向头遍历时使用
  • 分值score:节点的分值,在跳跃表中,节点按各自所保存的分值从小到大排序
  • 成员对象obj:各个节点中真实的数据对象

参考文章

  • Redis数据结构——跳跃表 - 随心所于 - 博客园

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

【实操】2023年npm组件库的创建发布流程

2022年的实践为基础,2023年我再建一个组件库【ZUI】。步骤回顾: 2022年的npm组件包的发布删除教程_npm i ant-design/pro-components 怎么删除_啥咕啦呛的博客-CSDN博客 1.在gitee上创建一个项目,相信你是会的 2.创建初始化项目,看吧&#…

86. 分隔链表

86. 分隔链表 题目-中等难度示例1. 新建两链表,根据x值分类存放,最后合并 题目-中等难度 给你一个链表的头节点 head 和一个特定值 x ,请你对链表进行分隔,使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。 你应当 保…

帮助中心干货:7步即可在线搞定产品帮助中心!

在产品的生命周期中,帮助中心是一个非常重要的部分,它能够为用户提供必要的信息和解决方案,帮助他们更好地使用产品。如果你正在寻找一种简单高效的方法来在线搭建产品帮助中心,那么这篇干货文章将为你提供7个步骤,让你…

WebDAV之π-Disk·派盘+Commander One

Commander one是一款为Mac用户设计的双窗格文件管理器,Commander One专业版在原先的版本功能拥有较大的提升。Commander One PRO可以帮助大家将文件从一个地方复制到另一个地方,支持多标签浏览、搜索、自定义热键设置、显示隐藏文件等功能。 π-Disk派盘 – 知识管理专家 派…

[迁移学习]领域泛化

一、概念 相较于领域适应,领域泛化(Domain generalization)最显著的区别在于训练过程中不能访问测试集。 领域泛化的损失函数一般可以描述为以下形式: 该式分为三项:第一项表示各训练集权重的线性组合,其中π为使该项最小的系数&a…

Linux下在qtcreator中创建qt程序

目录 1、新建项目 2、单工程项目创建 3、多工程项目创建 4、添加子工程(基于多工程目录结构) 5、 .pro文件 1、新建项目 切换到“编辑”界面,点击菜单栏中的“文件”-“新建文件或项目” 2、单工程项目创建 只有一个工程的项目&#…

uniapp使用阿里矢量库

然后解压复制全部到你的项目文件 最后只要这几个 然后引入 最后在你需要的页面使用

电脑系统重装日记

重装原因 电脑C盘几乎爆炸故重装系统一清二白 此片原因 记录重装过程,强调一些要注意的点,以防日后重装。 重装过程 1.清空电脑文件后重启,电脑冒蓝光,一直蓝屏反复重启,故只能重装系统以解难题。 2.准备一个U盘&…

手机里视频太大怎么压缩?压缩教程分享

现在视频文件的体积越来越大了,动不动就是几个GB起步,如果后期再剪辑处理一下,更是会占据更多的设备空间了,还会导致我们传输受到限制,这时候就需要我们对视频进行压缩处理,下面给大家分享几个简单的方法&a…

生成式 AI 在泛娱乐行业的应用场景实践 – 助力风格化视频内容创作

感谢大家阅读《生成式 AI 行业解决方案指南》系列博客,全系列分为 4 篇,将为大家系统地介绍生成式 AI 解决方案指南及其在电商、游戏、泛娱乐行业中的典型场景及应用实践。目录如下: 《生成式 AI 行业解决方案指南与部署指南》《生成式 AI 在…

spark的使用

spark的使用 spark是一款分布式的计算框架,用于调度成百上千的服务器集群。 安装pyspark # os.environ[PYSPARK_PYTHON]解析器路径 pyspark_python配置解析器路径 import os os.environ[PYSPARK_PYTHON]"D:/dev/python/python3.11.4/python.exe"pip inst…

SQLyog中导入CSV文件入库到MySQL中

1.在数据库中新建一个表,设置列名(与待导入文件一致),字段可以多出几个都可以 2.右键表名,导入- - >导入使用本地加载的CSV数据 选择使用加载本地CVS数据 3.指定好转义字符,将终止设置为,号(英文状态下…

SciencePub学术| 智能计量类重点SCIE征稿中

SciencePub学术 刊源推荐: 智能计量类重点SCIE征稿中!信息如下,录满为止: 一、期刊概况: 智能计量类重点SCIE 【期刊简介】IF:2.0-2.5,JCR3区,中科院4区; 【版面类型】正刊&#…

多维时序 | MATLAB实现ZOA-CNN-BiGRU-Attention多变量时间序列预测

多维时序 | MATLAB实现ZOA-CNN-BiGRU-Attention多变量时间序列预测 目录 多维时序 | MATLAB实现ZOA-CNN-BiGRU-Attention多变量时间序列预测预测效果基本介绍模型描述程序设计参考资料 预测效果 基本介绍 1.Matlab基于ZOA-CNN-BiGRU-Attention斑马优化卷积双向门控循环单元网络…

【CSS】禁用元素鼠标事件(例如实现元素禁用效果)

文章目录 基本用法 基本用法 pointer-events 属性指定在什么情况下 (如果有) 某个特定的图形元素可以成为鼠标事件。实际运用中可以通过对auto 和none动态控制,来动态实现元素的禁用效果。 属性描述auto与pointer-events属性未指定时的表现效果相同,对…

vue3 setup+Taro3 调用原生小程序自定义年月日时分多列选择器,NutUI改造

vue3 setupTaro3 调用原生小程序自定义年月日时分多列选择器&#xff0c;NutUI改造 NutUI 有日期时间选择器&#xff0c;但是滑动效果太差&#xff0c;卡顿明显。换成 原生小程序 很顺畅 上代码&#xff1a; <template><view><pickermode"multiSelector&…

lodash常用方法笔记

_.fromPairs(pairs) 与_.toPairs正好相反&#xff1b;这个方法返回一个由键值对pairs构成的对象。 _.fromPairs([[fred, 30], [barney, 40]]); // > { fred: 30, barney: 40 }Object.fromEntries()有同样的功能&#xff0c;只是在高版本浏览器才支持&#xff1a; _toPai…

zabbix监控tomcat

一、zabbix监控Tomcat1.1 zbx-agent配置1.1.1 关闭防火墙&#xff0c;将安装 Tomcat 所需软件包传到/opt目录下1.1.2 安装JDK1.1.3 设置JDK环境变量1.1.4 安装启动Tomcat1.1.5 配置 JMX 1.2 zbx-server配置1.2.1 安装zabbix&#xff08;省略&#xff0c;可看上一篇博客&#xf…

汇编知识点之80x86指令系统

指令系统主要考虑以下几个方面&#xff1a; ①对PSW影响  影响/不影响/不定义 ②B/W  字节还是字操作 ③寻址方式 ④功能 ⑤格式 一、数据传送指令 1.通用数据传送指令 (1) MOV DST,SRC    &#xff1c;–>  (DST)<–(SRC) 注&#xff1a;1.二者不能同时为段…

ardupilot参数的mavlink实现

专业名词释义&#xff0c;参数缩写 gimbal 云台&#xff0c;万向接头 failsafe 故障保护 Collective&#xff1a; 总距 Swashplate &#xff1a; 倾斜盘 SW&#xff1a; Swashplate 倾斜盘 RSC&#xff1a; Rotor Speed Control RC&#xff1a; Radio Channel 无线通道 DDFP&am…