当前位置: 首页 > news >正文

跳表是一种什么样的数据结构

跳表是有序集合的底层数据结构,它其实是链表的一种进化体。正常链表是一个接着一个用指针连起来的,但这样查找效率低只有O(n),为了解决这个问题,提出了跳表,实际上就是增加了高级索引。朴素的跳表指针是单向的并且元素值不能重复,redis对其进行了修改,回退指针的作用是支持反向遍历。
在这里插入图片描述
具体查找过程,假设查45,那从5的二级索引一下跳到35,发现还没找到,再跳到55。发现超了,那用一级索引试试,结果找到了,那ok了。需要注意,使用高级索引时候底层源码实现时候还有一个对于步长的记录,也就是5->35用二级索引记录了步长3

插入的话,不会影响当前表中节点的层高,因为节点被创建时和层高就已经确定了(当然可能会修改插入位置前后结点的关联指针,这是链表必然的)。
那一个节点层高如何确定?
这是在插入时候确定的,默认每个节点一开始默认的是1层(一级索引都没有),每次以25%概率增加1层(5.0.5版本最高为64层)。不用一个层高数量的比例是因为不想刻意维护这种比例关系,导致额外开销。

跳表的平均性能能达到O(logn),并且由于表头有定义查询有序集合元素总数时仅需O(1)

那么为啥redis不用b+树呢?
因为b+树是更多用于磁盘io的,其可以降低磁盘io次数。redis是内存中的,所以b+树这扁平特性没那么重要了,并且跳表实现起来简单,也不用考虑在中间位置插入后保持平衡的操作。
同样的问题,为啥不用红黑树?
其实就是因为跳表实现简单,占用内存少(层高概率25%是可以调的,层高越大占用内存越多,折中选择),并且查询性能和局部性不比红黑树差

相关文章:

跳表是一种什么样的数据结构

跳表是有序集合的底层数据结构,它其实是链表的一种进化体。正常链表是一个接着一个用指针连起来的,但这样查找效率低只有O(n),为了解决这个问题,提出了跳表,实际上就是增加了高级索引。朴素的跳表指针是单向的并且元素…...

【刷题记录】最大公因数,最小公倍数(辗转相除法、欧几里得算法)

本系列博客为个人刷题思路分享,有需要借鉴即可。 1.题目链接: 无 2.详解思路: 题目描述:输入两个正整数,输出其最大公因数和最小公倍数 一般方法:最大公因数:穷加法;最小公倍数&…...

ETL快速拉取物流信息

我国作为世界第一的物流大国,但是在目前的物流信息系统还存在着几大的痛点。主要包括以下几个方面: 数据孤岛:有些物流企业各个部门之间的数据标准不一致,难以实现数据共享和协同,容易导致信息孤岛。 操作繁琐&#x…...

17.1 SpringMVC框架_SpringMVC入门与数据绑定(❤❤)

17.1 SpringMVC框架_SpringMVC入门与数据绑定 1. SpringMVC入门1.1 MVC介绍1.2 环境配置1. 依赖引入2. web配置文件:DispatchServlet配置3. applicationContext.xml配置4. 开发Controller控制器(❤❤)1.3 MVC处理流程图2. Spring MVC数据绑定2.1 URL Mapping2.2 URL Mapping三个…...

Leetcode 11.盛水最多的容器

题目 给定一个长度为 n 的整数数组 height 。有 n 条垂线,第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。 找出其中的两条线,使得它们与 x 轴共同构成的容器可以容纳最多的水。 返回容器可以储存的最大水量。 说明:你不能倾斜容器。…...

《Go 简易速速上手小册》第7章:包管理与模块(2024 最新版)

文章目录 7.1 使用 Go Modules 管理依赖 - 掌舵向未来7.1.1 基础知识讲解7.1.2 重点案例:Web 服务功能描述实现步骤扩展功能7.1.3 拓展案例 1:使用数据库功能描述实现步骤扩展功能7.1.4 拓展案例 2:集成 Redis 缓存功能描述实现步骤...

【论文精读】IBOT

摘要 掩码语言建模(MLM)是一种流行的语言模型预训练范式,在nlp领域取得了巨大的成功。然而,它对视觉Transformer (ViT)的潜力尚未得到充分开发。为在视觉领域延续MLM的成功,故而探索掩码图像建模(MIM),以训练更好的视觉transforme…...

Yolo V5在实时视频流中的建筑物与彩钢房检测:性能评估与改进方法

Yolo V5在实时视频流中的建筑物与彩钢房检测:性能评估与改进方法 文章目录 Yolo V5在实时视频流中的建筑物与彩钢房检测:性能评估与改进方法概述Yolo V5模型概述建筑物与彩钢房检测的挑战实时视频流处理流程模型性能评估改进方法实验与分析结论与展望 概…...

图——最小生成树实现(Kruskal算法,prime算法)

目录 预备知识: 最小生成树概念: Kruskal算法: 代码实现如下: 测试: Prime算法 : 代码实现如下: 测试: 结语: 预备知识: 连通图:在无向图…...

Unity3D xLua开发环境搭建详解

前言 xLua是一种基于Lua语言的开发框架,可以帮助开发者在Unity3D中使用Lua脚本来开发游戏。 对惹,这里有一个游戏开发交流小组,希望大家可以点击进来一起交流一下开发经验呀! 在本文中,我们将详细介绍如何搭建Unity…...

Python笔记-super().init(root)的作用

假设我们有一个名为Animal的父类,它有一个属性color,在其构造函数__init__中被初始化: class Animal:def __init__(self, color):self.color color现在,我们想创建一个Animal的子类,名为Dog。Dog类有自己的属性name&…...

【git 使用】使用 git rebase -i 修改任意的提交信息/合并多个提交

修改最近一次的提交信息的方法有很多,可以参考这篇文章,但是对于之前的提交信息进行修改只能使用 rebase。 修改提交信息 假设我们想修改下面这个提交信息,想把【登录】改成【退出登录】步骤如下 运行 git rebase -i head~3 打开了一个文本…...

【Vue3】toRefs和toRef在reactive中的一些应用

💗💗💗欢迎来到我的博客,你将找到有关如何使用技术解决问题的文章,也会找到某个技术的学习路线。无论你是何种职业,我都希望我的博客对你有所帮助。最后不要忘记订阅我的博客以获取最新文章,也欢…...

力扣精选算法100道——Z字形变换(模拟专题)

目录 🎈了解题意 🎈算法原理 🚩先处理第一行和最后一行 🚩再处理中间行 🎈实现代码 🎈了解题意 大家看到这个题目的时候肯定是很迷茫的,包括我自己也是搞不清楚题目什么意思,我…...

Elastic Stack--01--简介、安装

提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档 文章目录 1. Elastic Stack 简介为什么要学习ESDB-Engines搜索引擎类数据库排名常年霸榜![在这里插入图片描述](https://img-blog.csdnimg.cn/direct/051342a83f574c8c910cda…...

.NET项目web自动化测试实战——Selenium 2.0

🔥 交流讨论:欢迎加入我们一起学习! 🔥 资源分享:耗时200小时精选的「软件测试」资料包 🔥 教程推荐:火遍全网的《软件测试》教程 📢欢迎点赞 👍 收藏 ⭐留言 &#x1…...

【Day53】代码随想录之动态规划_买卖股票ⅠⅡ

文章目录 动态规划理论基础动规五部曲:出现结果不正确: 1. 买卖股票的最佳时机2. 买卖股票的最佳时机Ⅱ 动态规划理论基础 动规五部曲: 确定dp数组 下标及dp[i] 的含义。递推公式:比如斐波那契数列 dp[i] dp[i-1] dp[i-2]。初…...

Swift Combine 使用调试器调试管道 从入门到精通二十六

Combine 系列 Swift Combine 从入门到精通一Swift Combine 发布者订阅者操作者 从入门到精通二Swift Combine 管道 从入门到精通三Swift Combine 发布者publisher的生命周期 从入门到精通四Swift Combine 操作符operations和Subjects发布者的生命周期 从入门到精通五Swift Com…...

go内置库函数实现client与server数据的发送接收

功能:客户端持续写入数据,直到输入exit退出,服务端读取数据并打印 注意:server和client目录在同一层级 服务端 server/main package mainimport ("fmt""net" )func main() {listen, err : net.Listen(&quo…...

[java基础揉碎]this

引出this: 什么是this: java虚拟机会给每个对象分配 this,代表当前对象。 这里的this就是new出来的这个对象 this的本质: this是个引用在堆中指向它自己: this的细节: 访问成员方法: 访问构造器:...

《Playwright:微软的自动化测试工具详解》

Playwright 简介:声明内容来自网络,将内容拼接整理出来的文档 Playwright 是微软开发的自动化测试工具,支持 Chrome、Firefox、Safari 等主流浏览器,提供多语言 API(Python、JavaScript、Java、.NET)。它的特点包括&a…...

spring:实例工厂方法获取bean

spring处理使用静态工厂方法获取bean实例,也可以通过实例工厂方法获取bean实例。 实例工厂方法步骤如下: 定义实例工厂类(Java代码),定义实例工厂(xml),定义调用实例工厂&#xff…...

SpringBoot+uniapp 的 Champion 俱乐部微信小程序设计与实现,论文初版实现

摘要 本论文旨在设计并实现基于 SpringBoot 和 uniapp 的 Champion 俱乐部微信小程序,以满足俱乐部线上活动推广、会员管理、社交互动等需求。通过 SpringBoot 搭建后端服务,提供稳定高效的数据处理与业务逻辑支持;利用 uniapp 实现跨平台前…...

拉力测试cuda pytorch 把 4070显卡拉满

import torch import timedef stress_test_gpu(matrix_size16384, duration300):"""对GPU进行压力测试,通过持续的矩阵乘法来最大化GPU利用率参数:matrix_size: 矩阵维度大小,增大可提高计算复杂度duration: 测试持续时间(秒&…...

听写流程自动化实践,轻量级教育辅助

随着智能教育工具的发展,越来越多的传统学习方式正在被数字化、自动化所优化。听写作为语文、英语等学科中重要的基础训练形式,也迎来了更高效的解决方案。 这是一款轻量但功能强大的听写辅助工具。它是基于本地词库与可选在线语音引擎构建,…...

10-Oracle 23 ai Vector Search 概述和参数

一、Oracle AI Vector Search 概述 企业和个人都在尝试各种AI,使用客户端或是内部自己搭建集成大模型的终端,加速与大型语言模型(LLM)的结合,同时使用检索增强生成(Retrieval Augmented Generation &#…...

算法:模拟

1.替换所有的问号 1576. 替换所有的问号 - 力扣(LeetCode) ​遍历字符串​:通过外层循环逐一检查每个字符。​遇到 ? 时处理​: 内层循环遍历小写字母(a 到 z)。对每个字母检查是否满足: ​与…...

推荐 github 项目:GeminiImageApp(图片生成方向,可以做一定的素材)

推荐 github 项目:GeminiImageApp(图片生成方向,可以做一定的素材) 这个项目能干嘛? 使用 gemini 2.0 的 api 和 google 其他的 api 来做衍生处理 简化和优化了文生图和图生图的行为(我的最主要) 并且有一些目标检测和切割(我用不到) 视频和 imagefx 因为没 a…...

面向无人机海岸带生态系统监测的语义分割基准数据集

描述:海岸带生态系统的监测是维护生态平衡和可持续发展的重要任务。语义分割技术在遥感影像中的应用为海岸带生态系统的精准监测提供了有效手段。然而,目前该领域仍面临一个挑战,即缺乏公开的专门面向海岸带生态系统的语义分割基准数据集。受…...

MySQL 知识小结(一)

一、my.cnf配置详解 我们知道安装MySQL有两种方式来安装咱们的MySQL数据库,分别是二进制安装编译数据库或者使用三方yum来进行安装,第三方yum的安装相对于二进制压缩包的安装更快捷,但是文件存放起来数据比较冗余,用二进制能够更好管理咱们M…...