MySql中索引为什么用B+树,他有什么特点?时间复杂度是多少?能存多少数据?是不是只能三层?他与B-树有什么不同?还有其它的树你是是否知道?

平衡二叉树

  • 平衡二叉树又被称为AVL树
  • 平衡二叉树是一颗空树或者它的左右两个子树的高度差的绝对值不超过1,并且左右子树也是平衡树
  • 非叶子节点值大于左子节点值而小于右子节点值
  • 非叶子节点最多拥有两个子节点
  • 平衡二叉树的不足之处及时间复杂度

  • 如果每次插入的数据都比上一次插入的数据大,那么用平衡二叉树就会以线性方式进行存储,所以他的时间复杂度为O(n)。在mysql中一张表存储百万条数据是很正常的一件事,这样会导致树的深度更深,导致大量的IO操作。还有就是mysql进行过磁盘读取时,是以页为单位进行读取,每个节点表示一页。而平衡二叉树每个节点存储一个关键词,导致存储空间被浪费。
  • 红黑树

  • 每个节点要么是红色要么是黑色
  • 根节点是黑色
  • 每个叶子节点(NIL)是黑色
  • 每个红色节点的两个子节点一定为黑色
  • 任意一个节点到每个叶子节点的路径都包含数量相同的黑色节点
  • 如果一个节点存在黑子节点,那么该节点肯定有两个子节点
  • B-树

     B-树(B树)并不只能有三层。B树的高度取决于其阶数(即每个节点最多可以拥有的子节点数)以及树中存储的元素数量。
  • 每个节点中,都包含数据(key和data域)和指针,相互间隔
  • 叶节点具有相同的深度,叶节点的指针为空
  • 节点中的数据索引从左到右递增排列
  • 所有索引元素不重复
  • B-树相比平衡二叉树优点

  • 每个节点存储多个多个关键词,合理利用空间大小,每次mysql进行读取时,都会进行预读取,每次把该节点数据读取出来并存储到内存中
  • B-树中每个节点存储的关键词变多,导致存储相同数量的数据,B-树的深度相比平衡二叉树深度更浅,减少了数据的查找次数和复杂度
  • B+树

    B+树同样也不只能有三层,从罕见角度来说他也可以一层,二层,但是很罕见
  • 非叶子节点中不存储data,只存储索引,可以放更多的索引
  • 叶子节点包含所有索引字段
  • 叶子节点包含数据(key和data域)和指针
  • 叶子节点用指针连接,提高区间访问的性能
  • B+树对比红黑树

  • 红黑树多用于内部排序,即全放在内存中
  • B+树多用于外存上时,B+也被成为一个磁盘友好的数据结构
  • 红黑树和平衡二叉树有相同缺点,每个节点存储一个关键词,数据量大时,导致红黑树的深度很深,mysql每次读取时消耗大量io

B+树通常设计为三层的原因主要包括以下几点‌:


一个高度为3的B+树大概可以存放:1170*1170*16=21902400行数据。
所以在InnoDB中B+树高度一般为1-3层,它就能满足千万级的数据存储。
在查找数据时一次页的查找代表一次IO,所以通过主键索引查询通常只需要1-3次逻辑IO操作即可查找到数据。
‌性能优化‌:三层B+树可以在保证性能的同时,减少对磁盘的I/O操作。例如,一个三层B+树在查找数据时,最多只需要三次I/O操作,这大大提高了数据查找的效率‌1。
‌存储效率‌:三层B+树可以存储大量的数据。假设每个节点存储16KB的数据,一个三层B+树可以存储大约2000万条数据,这足以满足大多数应用场景的需求‌2。
‌平衡性‌:B+树的插入和删除操作会保持树的平衡,三层结构可以确保树的深度适中,避免过深的树结构导致的性能下降‌2。
‌维护成本‌:三层结构相对简单,维护成本较低。过多的层数会增加树的复杂度,从而增加维护和管理的难度‌2。
‌实际应用场景‌:在实际应用中,三层B+树已经能够满足大多数数据库和文件系统的需求,不需要更深层次的树结构‌2。


B+树的时间复杂度是多少?


由于B+树所有的 data 域都在根节点,所以查询 key 的节点必须从根节点索引到叶节点,时间复杂度固定为 O(log n)。


B+树相比B-树的优点


B+树非叶子节点只存储key值,而B-树存储key值和data值,这样B+树每次读取时可以读取到更多的key值
mysql进行区间访问时,由于B+树叶子节点之间用指针相连,只需要遍历所有的叶子节点即可;而B-树则需要中序遍历那样遍历
B+树非叶子节点只存储key值,而B-树存储key值和data值,导致B+树的层级更少,查询效率更高
B+树所有关键词地址都存在叶子节点上所以每次查询次数都相同,比B-树稳定


为什么高度为3的B+树存储千万级数据?


解释这个问题的前提,mysql使用InnoDB引擎,mysql默认页文件大小为16k
假设我们一行数据大小为1k,那么一页存储16条数据,也就是说一个叶子节点能存储16条数据
再来看看非叶子节点,假设主键ID为bigint类型,那么长度为8B,指针大小在InnoDB引擎中的大小为6B,一共14B,那么一页中可以存放16k/14B=1170个(主键+指针)
也就是说高度为2的B+树可以存储的数据为:1170*16=18720条;高度为3的B+树可以存储的数据为:11701170*16=21902400(千万条数据)
 

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

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

相关文章

【初阶数据结构篇】链式结构二叉树(续)

文章目录 须知 💬 欢迎讨论:如果你在学习过程中有任何问题或想法,欢迎在评论区留言,我们一起交流学习。你的支持是我继续创作的动力! 👍 点赞、收藏与分享:觉得这篇文章对你有帮助吗&#xff1…

VMWARE ESXI VMFS阵列故障 服务器数据恢复

1:河南用户一台DELL R740 3块2.4T硬盘组的RAID5,早期坏了一个盘没有及时更换,这次又坏了一个,导致整组RAID5处于数据丢失的状态, 2:该服务器装的是VMware ESXI 6.7,用户把3块硬盘寄过来进行数据…

使用docker安装zlmediakit服务(zlm)

zlmediakit安装 zlmediakit安装需要依赖环境和系统配置,所以采用docker的方式来安装不容易出错。 docker pull拉取镜像(最新) docker pull zlmediakit/zlmediakit:master然后先运行起来 sudo docker run -d -p 1935:1935 -p 80:80 -p 8554:554 -p 10000:10000 -p …

uni-app跨域set-cookie

set-cookie的值是作为一个权限控制的 首先,无论什么接口都会返回一个set-cookie,但未登录时,set-cookie是没有任何权限的 其次,登录接口请求时会修改set-cookie,并且在后续其他接口发起请求时,会在请求头…

【论文速读】| PathSeeker:使用基于强化学习的越狱攻击方法探索大语言模型的安全漏洞

基本信息 原文标题: PathSeeker: Exploring LLM Security Vulnerabilities with a Reinforcement Learning-Based Jailbreak Approach 原文作者: Zhihao Lin, Wei Ma, Mingyi Zhou, Yanjie Zhao, Haoyu Wang, Yang Liu, Jun Wang, Li Li 作者单位: Beihang University, Nany…

黑马官网2024最新前端就业课V8.5笔记---HTML篇

Html 定义 HTML 超文本标记语言——HyperText Markup Language。 标签语法 标签成对出现&#xff0c;中间包裹内容<>里面放英文字母&#xff08;标签名&#xff09;结束标签比开始标签多 /拓展 &#xff1a; 双标签&#xff1a;成对出现的标签 单标签&#xff1a;只有开…

NXP Zigbee JN5169 开发环境软件 文档和支持资源打包下载

NXP Zigbe JN5169软件、文档和支持资源下载 从NXP官网下载https://www.nxp.com.cn/pages/jn516x-7x-zigbee-3-0:ZIGBEE-3-0&#xff0c;有点蛋疼网站&#xff0c;要注册会员&#xff0c;所以我打包好所有NXP Zigbe JN5169所需的 软件、文档和支持资源打包好&#xff0c;以供开…

基于matlab的语音识别系统

一&#xff0e;设计任务及要求 1.1设计任务 作为智能计算机研究的主导方向和人机语音通信的关键技术&#xff0c;语音识别技 术一直受到各国科学界的广泛关注。以语音识别开发出的产品应用领域非常广泛&#xff0c;有声控电话交换、语音拨号系统、信息网络查询、家庭服务、宾馆…

使用WebStorm开发Vue3项目

记录一下使用WebStorm开发Vu3项目时的配置 现在WebStorm可以个人免费使用啦&#xff01;&#x1f929; 基本配置 打包工具&#xff1a;Vite 前端框架&#xff1a;ElementPlus 开发语言&#xff1a;Vue3、TypeScript、Sass 代码检查&#xff1a;ESLint、Prettier IDE&#xf…

Ansys HFSS:外壳的屏蔽效果演示

欢迎回来&#xff01;随着电子系统变得越来越复杂和集成&#xff0c;确保适当的屏蔽以减轻电磁干扰 &#xff08;EMI&#xff09; 变得越来越重要。 继续讨论屏蔽效果&#xff0c;我们现在将重点转移到另一个强大的工具上&#xff1a;Ansys HFSS&#xff08;高频结构仿真器&am…

Python基于TensorFlow实现双向循环神经网络GRU加注意力机制分类模型(BiGRU-Attention分类算法)项目实战

说明&#xff1a;这是一个机器学习实战项目&#xff08;附带数据代码文档视频讲解&#xff09;&#xff0c;如需数据代码文档视频讲解可以直接到文章最后关注获取。 1.项目背景 随着深度学习技术的发展&#xff0c;循环神经网络&#xff08;RNN&#xff09;及其变种如门控循环…

【C++】C++的单例模式

二十四、C的单例模式 1、C的单例模式 本小标题不是讨论C的语言特性&#xff0c;而是一种设计模式&#xff0c;用于确保一个类在任何情况下都只有一个实例&#xff0c;并提供一个全局访问点来获取这个实例。即C的单例模式。这种模式常用于资源管理&#xff0c;如‌线程池、‌缓…

单元测试(Junit)

系统—模块—子模块&#xff0c;子模块中不可分割的程序单元的测试&#xff0c;单元的粒度根据实际情况可能是 类或方法等。 面向对象编程中&#xff0c;最小单元就是方法。 单元测试目的是在集成测试和功能测试之前对系统可测试单元进行逐一检查和验证。 单元测试基本原则 …

这个自动化框架吧,解决接口间数据依赖

在实际的测试工作中&#xff0c;在做接口自动化测试时往往会遇到接口间数据依赖问题&#xff0c;即API_03的请求参数来源于API_02的响应数据&#xff0c;API_02的请求参数又来源于API_01的响应数据。 因此通过自动化方式测试API_03接口时&#xff0c;需要预先请求API_02接口&a…

JeecgBoot入门

最近在了解低代码平台&#xff0c;其中关注到gitee上开源项目JeecgBoot&#xff0c;JeecgBoot官方也有比较完整的入门教学文档&#xff0c;这里我们将耕者官方教程学习&#xff0c;并将其记录下来。 一、项目简介 JeecgBoot 是一款基于代码生成器的低代码开发平台拥有零代码能力…

修改HarmonyOS鸿蒙图标和名字,打包后安装到真机,应用图标丢失变成透明,修改名字也不生效,还是默认的labeL解决方案教程

HarmonyOS鸿蒙打包hap 安装应用到桌面没有图标&#xff0c;用hdc安装到真机&#xff0c;打包后应用图标丢失变成透明&#xff0c;名字也还是默认的label的bug&#xff0c;以下是解决方案 以下是修改方案&#xff1a; 1、修改应用名字&#xff1a; 2、修改应用图标&#xff1a…

MYSQL安装(ubuntu系统)

rpm -qa 查询安装软件包 ps axj 查询服务 卸载mysql&#xff08;万不得已&#xff09; ps axj | grep mysql 查看是否存在mysql服务 systemctl stop mysqld 关闭该服务 rpm -qa | grep mysql 查安装mysql安装包 rmp -qa | grep mysql | xargs (yum apt) -y remove进行批量…

比ChatGPT更牛!苹果新AI模型刷新交互体验!能看懂你的手机屏幕!平板和安卓机也都行

家人们&#xff0c;苹果一直在悄悄进步&#xff01; 近期&#xff0c;据小鹿观察&#xff0c;各大科技巨头不仅在提升模型解决复杂问题的能力上竞争激烈&#xff0c;而且还在大语言模型应用于用户界面&#xff08;UI&#xff09;交互方面上暗暗发力&#xff01; 最近&#xf…

InstructIR: High-Quality Image Restoration Following Human Instructions 论文阅读笔记

这是Radu大佬所在的Wrzburg大学的computer vision lab实验室发表在ECCV2024上的一篇论文&#xff0c;代码开源。文章提出了一种文本引导的All-in-One的restoration模型&#xff0c;如下图所示&#xff1a; 这个工作其实跟"InstructPix2Pix: Learning to Follow Image Edit…

解决使用Golang的email库发送qq邮件报错short response,错误类型为textproto.ProtocolError

问题阐述 使用email库发送QQ邮件&#xff0c;采用587端口&#xff1a; package mainimport ("fmt""net/smtp""github.com/jordan-wright/email" )func SendEmail(sendTo string, subject string, body string) (err error) {e : email.NewEmai…