数据结构篇:深度剖析跳跃表及与B+树优劣分析

     本文旨在探讨跳跃表的特性及其在实际应用场景中的作用,同时对其与B+树进行比较,以帮助更好地理解和运用这两种数据结构。

跳跃表

什么是跳跃表(skip list)

        跳跃表是一种基于跳跃链表的有序数据结构,它是一种多层链表,每一层都是一个有序的链表。表的每一层都有一个指向下一层的指针,可以快速跳转到更深层次的链表,支持快速的插入、搜索和删除操作。

        其原理是会把数据按照一定的规则分成多个层次,每一层都是有序的,并且每一层的元素数量都比下一层少一半,在搜索从最高层开始,比较要查找的元素和当前层的元素,如果要查找的元素比当前层的元素小,则可以跳转到下一层,如果要查找的元素比当前层的元素大,则继续比较下一个元素,直到找到要查找的元素为止。

        其优势在于搜索时间复杂度可以达到 O(logN),比传统的二分搜索树要快得多,且它的内存占用也比较少,节省大量的内存空间。但它同样也存在着不足,它需要额外的存储空间来存储每一层的指针,而且它的插入和删除操作比较复杂,需要更新多个指针。比起单链表,跳表需要存储多级索引,要消耗更多的存储空间,空间换时间的思路。

        其索引流程首先对链表建立一级“索引”,查找起来会更快,每隔几个结点提取一个结点到上一级,把抽出来的那一级叫做索引层,每加来一层索引之后,查找一个结点需要遍历的结点个数减少,时间复杂度也下降。比如要查找 60,从第一层索引查找到第3个节点发现65比60大,则回到30所在节点下降到一层,继续往前查找即可找到。

应用场景

        Redis的Sorted Set就是使用跳表来实现。

Redis的每种数据结构操作,实际上都是基于多种底层数据结构实现

跳表与B+树的对比

        每一种数据结构都有一个适用场景,结合前面B+树算法章节,我们来想一个问题:MySQL索引为什么使用 B+ 树而不使用跳表?或者说Mysql的InnoDB引擎 3层的B+树可以存储多少条数据 ?

B+树

    1 ) B+ 树是多叉树结构,每个节点存储16k的数据页,每个非叶子节点只存主键值(主键索引)和指针,数据存在于叶子节点。
    2 ) B+树 的一个节点大小=innodb引擎的一页=4个操作系统页(一页4kb)=16kb。
    3 ) B+ 树存放记录数:根节点指针数 x 中间节点数 x 单个叶子节点记录行数。
    4 ) B+树的每个节点可以存16KB数据,假设一行数据大小是1K,那一个叶子节点就可以存16行数据。
    5 ) 非叶子节点存放的是主键值与指针,假设主键类型为bigint,占用8字节, InnoDB 源码中指针占用6字节,共就14Byte。
    6 ) 单个叶子节点(页)大概可以存放为16KB/14Byte=1170个指针。
    7 ) 2层B+树 可以存放1170*16=18720行数据,3层B+树可以存放1170*1170*16=21902400行数据,差不多2000w条数据。
      7.1 ) 如果树高是2, 可以存储1170页的数据,1170*16 = 18720 行数据。
      7.2 ) 如果树高是3,可以存储 1170*1170 = 1368900 = 137万页数据,1170*1170*16 = 2200万行数据。
      7.4 ) 如果树高是4,可以存储 1170*1170*1170 = 16亿页数据,1170*1170*1170*16 = 256亿行数据。
    8 ) B+树三层就可以存储 2kw 左右的数据,查询一次数据,数据页都在磁盘中,最多需要经过三次磁盘 I/O。

跳表

    1 ) 跳表是链表结构,一个节点存储一个数据,如果最底层要存放 2kw 的数据,达到二分查找的效果。
    2 ) 跳表的大概高度在 24 层左右(2kw 大概是 2 的 24 次方)。
    3 ) 如果数据分布不好的情况下, 24 层数据会分散在不同的数据页里,查一次数据会经过 24 次磁盘 I/O。
    4) 存放同样量级的数据,B+ 树的高度比跳表要小,MySQL查询多,磁盘 I/O 次数更少,因此 B+ 树查询更快。
    5) Redis 使用跳表而不使用 B+ 树。
      5.1 ) 进行读写数据时都是内存操作,数据量相对少,不操作磁盘,因此也不存在磁盘 I/O,所以层高就不再是跳表的缺点。
      5.1 ) 写操作B+树要进行拆分索引数据页,跳表是独立插入,没有旋转和维持平衡的开销,跳表的写入性能会比 B+ 树更好。

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

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

相关文章

openGauss_5.1.0 企业版快速安装及数据库连接:单节点容器化安装

目录 📚第一章 官网信息📚第二章 安装📗下载源码📗下载安装包📗修改版本📗解压安装包📗运行buildDockerImage.sh脚本📗docker操作📕查看docker镜像📕启动dock…

上位机图像处理和嵌入式模块部署(改进的qmacvisual动态插件卸载)

【 声明:版权所有,欢迎转载,请勿用于商业用途。 联系信箱:feixiaoxing 163.com】 前面我们讨论过,qmacvisual虽然提供了很多的功能,包括的种类很多,但是总有一些功能是客户希望定制的。这些都是…

更改docker镜像下载地址

一.简介 使用指令 sudo docker info 查看本机的docker镜像下载地址为 由于本机的var文件空间不足,因此,想更改他的存储地址,如下 二.开始操作 1.停止Docker服务: 执行命令 sudo systemctl stop docker 以及 sudo systemctl s…

USB端口

winx,打开设备管理器 名称解释 HS-USB 分类全称传输速率版本超速SSsuper-speed最大速率5Gbps、10Gbps、20GbpsUSB3.0~USB3.2高速HShigh-speed25Mbps-400 Mbps (最大480 Mbps)USB2.0全速FSfull-speed500Kbps-10Mbps(最大12Mbps&…

8个Python小游戏,小白练手,我都能玩一天【内附源码】

大家好,在使用Python的过程中,我最喜欢的就是Python的各种第三方库,能够完成很多操作。 下面就给大家介绍8个通过Python构建的项目,以此来学习Python编程。 大家也可根据项目的目的及提示,自己构建解决方法&#xff…

c++ stub函数打桩

应用场景: 当我们在开发一个涉及到第三方sdk库的软件时,比如做一个上位机控制客户端,该客户端当中调用了一份sdk库当中的接口。而这份sdk库,作为上层客户端软件与下层设备进行通信的媒介,可能需要在有真实设备的环境下…

社交网络与Web3:数字社交的演进

在数字化时代的浪潮下,社交网络已成为人们日常生活的重要组成部分。从早期的在线论坛到如今的社交媒体平台,社交网络已经成为人们交流、分享和获取信息的主要渠道。然而,随着区块链技术的发展,传统的社交网络正经历着一场革命性的…

Sy7 shell编程-1

实验环境: 宿主机为win11,网络:10.255.50.5 6389 WSL2 ubuntu 目标机的OS:Ubuntu 内核、版本如下: linuxpeggy0223:/$ uname -r 5.15.146.1-microsoft-standard-WSL2 linuxpeggy0223:/$ cat /proc/version Linux vers…

Java | Leetcode Java题解之第22题括号生成

题目&#xff1a; 题解&#xff1a; class Solution {static List<String> res new ArrayList<String>(); //记录答案 public List<String> generateParenthesis(int n) {res.clear();dfs(n, 0, 0, "");return res;}public void dfs(int n ,int…

动态规划应用

介绍 是用来解决一类最优问题的算法思想&#xff0c;将一个复杂的问题分解成若干个子问题&#xff0c;通过综合子问题的最优解得到。 递归写法实例 优化斐波那契数列 int F(int n){if(n0||n1) return 1;else{return F(n-1)F(n-2);}有太多重复计算&#xff0c;可用一个数组记…

oracle数据库怎么查看当前登录的用户?

方法如下&#xff1a; 输入select * from dba_users; 即可。 常用语句&#xff1a; 一&#xff0c;查看数据库里面所有用户&#xff1a; select * from dba_users; 前提是你是有dba权限的帐号&#xff0c;如sys,system。 二&#xff0c;查看你能管理的所有用户&#xff1…

.[[backup@waifu.club]].svh勒索病毒数据怎么处理|数据解密恢复

尊敬的读者&#xff1a; 近年来&#xff0c;随着信息技术的迅猛发展&#xff0c;网络安全问题日益凸显&#xff0c;其中勒索病毒成为了一大威胁。.[[backupwaifu.club]].svh、.[[MyFilewaifu.club]].svh勒索病毒就是其中之一&#xff0c;它以其独特的传播方式和恶劣的加密手段…

Spring AMQP消息中间件

SpringAMQP简单说就是一个中间件&#xff0c;提供了模板方便我们操作各种消息模型 上面已经学了RabbitMQ消息队列是有五种消息模型&#xff0c;并且我们演示了其中的基本消息队列(Hello World)。用的是官方API&#xff0c;来实现的基本消息队列(Hello World)。会发现官方提供的…

华为OD-C卷-攀登者1[100分]

攀登者喜欢寻找各种地图,并且尝试攀登到最高的山峰。 地图表示为一维数组,数组的索引代表水平位置,数组的元素代表相对海拔高度。其中数组元素0代表地面。 例如: [0,1,2,4,3,1,0,0,1,2,3,1,2,1,0],代表如下图所示的地图 地图中有两个山脉位置分别为 1,2,3,4,5 和 8,9,1…

一、OpenCvSharp环境搭建

一、Visual Studio 创建新项目 二、选择Windows窗体应用&#xff08;.NET Framework&#xff09; 直接搜索模板&#xff1a;Windows窗体应用(.NET Framework) 记得是C#哈&#xff0c;别整成VB(Visual Basic)了 PS&#xff1a;若搜索搜不到&#xff0c;直接点击安装多个工具和…

K8S哲学 - 常见的资源类型

资源类型 namespace kubectl apply 和 kubectl create kubectl apply是声明式的 和 kubectl create是命令式的对吗 deployment 和 job的区别

Fiddle配置代理,保手机模拟器访问外部网络

前言&#xff1a; 嘿&#xff01;大家好&#xff01;我来带你们玩转Fiddler和Mumu模拟器的组合技了&#xff01;此组合技能帮助你实现在模拟器上畅游外部网络。相信我&#xff0c;它会让你的开发和测试过程更加轻松愉快&#xff01;废话不多说&#xff0c;赶紧展开我们的冒险吧…

bugku-web-file_get_contents

<?php extract($_GET); if (!empty($ac)){$f trim(file_get_contents($fn));if ($ac $f){echo "<p>This is flag:" ." $flag</p>";}else{echo "<p>sorry!</p>";} } ?> 这里涉及到几个不常用的函数 这里直接构…

22.04 忘记root密码

在即将加载Ubuntu启动界面时&#xff0c;在 GRUB 引导菜单出现之前马上按住 Shift 键&#xff0c;将进入引导菜单 在引导菜单中选择 “Advanced options for Ubuntu”&#xff0c;如果是中文则显示为“Ubuntu高级选项” 接下来你会看到好几个内核版本号&#xff0c;按上下键选…

区块链安全-----接口测试-Postman

Postman是一款支持http协议的接口调试与测试工具&#xff0c;其主要特点就是功能强大&#xff0c;使用简单且易 用性好 。无论是开发人员进行接口调试&#xff0c;还是测试人员做接口测试&#xff0c;Postman都是我们的首选工具 之一 。 更早的接入测试&#xff0c;更早的发现问…