MySQL索引为什么是B+树

MySQL索引为什么是B+树


索引是帮助MySQL高效获取数据的数据结构,在数据之外,数据库还维护着满足特定查找算法的数据结构B+树,这些数据结果以某种特定的方式引用数据,这样就可以在这些数据结构上实现高级查找算法,提升数据的查找速度,这种数据结构就是索引

如果此时有一个user表,在它还未建立索引的时候,如果想要查找age为35岁的用户:

select * from user where age = 35

那么此时在user表中会逐个查找每一行,直到查找到最后一行,然后返回age为35的行

idnameusernameage
1001张三zhangsan20
1002李四lisi18
1003王九wangjiu35
1004赵六zhaoliu22
1005王八wangba17

这样的查找无疑是非常耗时的,当数据量非常庞大时,全部检索整张表会消耗大量的时间和性能,因此需要为数据建立合适的索引来提高查询的效率

那为什么MySQL采用的是B+数呢?而不是二叉树、红黑数呢?

二叉树

二叉树在查找时,使用的是二分查找算法,查询效率得到了提高,并且二叉树简单易实现,当数据量较小时,普通二叉树的性能已经能满足要求,开销更小

38
22
45
15
31
40
49

但是二叉树有一个非常致命的缺点:高度不稳定

普通二叉树在数据分布不均时可能变成链表状,最坏情况下高度为 O(n),影响查找性能:

38
22
20
15

红黑树

红黑树是一种自平衡二叉搜索树,保证任何路径的最大深度不超过最小深度的两倍,自平衡的特性完美解决了二叉树中高度不稳定的特点,查找、插入和删除操作的时间复杂度始终保持在 O(log⁡n),在插入和删除操作引入了旋转变色等机制,确保平衡性,无需频繁重构树结构

红黑规则:

  • 每个节点都有一个颜色属性,可以是红色或黑色。

  • 红黑树的根节点必须是黑色。

  • 所有的叶子节点(即树中的 null 节点)是黑色的。叶子节点不包含数据,只是辅助结构。

  • 如果一个节点是红色的,则其子节点必须是黑色。这确保了没有两个红色节点相连,从而避免了树的高度过高。

  • 任何路径从根节点到叶子节点或者空节点的过程中,必须经过相同数量的黑色节点。这保证了红黑树的平衡性,避免了一些路径比其他路径过长,从而影响查找效率。

50
30
70
20
40
60
80
17

但是当数据规模量巨大时,他也会暴露出来缺点:深度较大

因此红黑数无法适应大规模数据,而且每个节点只存储一个键值,导致树的层数增加,浪费存储空间,红黑树需要通过中序遍历才能完成范围查询,因此在大规模数据量的场景下,查询效率依然不高


B树

B树(B-tree)是一种自平衡的多路搜索树,它能够保持数据有序,并允许高效的插入、删除和查找操作

B树的特点包括:

  1. 平衡性:B树是一种平衡树,所有叶子节点的深度相同。通过这种结构,B树保证了对所有节点的访问时间是相同的,从而提高了查找效率。
  2. 多路性:B树的每个节点可以有多个子节点(通常是 m 个子节点)。这使得B树能够存储更多的数据,并且能更快地完成查找、插入、删除等操作。
  3. 节点结构:每个节点包含若干个关键字(data),并且包含指向其子节点的指针。对于每个节点中的关键字,子节点的关键字范围是有序的。
  4. 查找效率:B树的查找操作类似于二叉查找树,但是每个节点具有多个子节点。查找操作的时间复杂度为O(log n),其中n是树中的元素个数。
  5. 插入和删除操作:插入和删除操作需要保证树的平衡性,插入时可能会导致节点分裂,删除时可能会引起节点合并或借用关键字。所有这些操作都在O(log n)时间内完成。

在这里插入图片描述

他的单个节点可以存储多个数据和多个指针,每个节点也可以有多个分支,因此他的每一层级可以存放大量数据,同样遵循左边大右边小的存储规则,因此B树的查找效率是十分优秀的,B树通常用于数据库和文件系统中,用于存储和管理大量数据

但是MySQL中使用的数据结构并不是B树,而是B+树,相比B树,B+树更加优秀


B+树

B+树是B树的变种,它具有与B树类似的结构和特点,但在某些方面有所改进,特别是在存储和查找效率上。B+树通常用于数据库和文件系统中,作为一种高效的索引结构

  1. 所有数据都存储在叶子节点中
    • 在B树中,数据可以存储在内部节点和叶子节点中,而在B+树中,所有的数据(即关键字)都仅存储在叶子节点中。内部节点只存储关键字,用于引导查找过程。
    • 这种设计可以减少内部节点的存储空间,提高查询效率。
  2. 叶子节点通过链表连接
    • B+树的叶子节点通常是通过一个链表连接起来的,这使得范围查询(例如查找某个区间内的所有数据)变得更加高效。通过遍历链表,可以一次性返回区间内的所有数据,而不需要回溯到其他节点。
  3. 树的高度较小
    • 由于所有数据都存储在叶子节点中,B+树的内部节点只需要存储关键字和指向子节点的指针。因此,相比于B树,B+树可以将更多的数据存储在每个节点中,从而使树的高度变得更小,查找操作的效率更高。
  4. 查找操作的效率更高
    • B+树的查找操作通常仅限于叶子节点,而B树在查找时可能需要在内部节点和叶子节点之间反复跳转。由于叶子节点之间有链表连接,B+树在范围查询时特别高效。

在这里插入图片描述

B+树相较于B树,在查找和范围查询上有显著的优势,尤其在数据库和文件系统中,因为它能够有效地减少磁盘I/O操作,并提高查询效率。因此,MySQL选择了B+树作为索引的数据结构

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

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

相关文章

C#实现图像骨架化(ZhangSuen细化算法)

原始图像: 骨架化后图像: 需要安装一个NuGet包:System.Drawing.Common 代码如下: using System.Drawing; using System.Drawing.Imaging;public class Image {public int Width { get; }public int Height { get; }private bool[,] pixels;// 构造函数,初始化图像的宽度…

【无标题】学生信息管理系统界面

网页是vue框架,后端直接python写的没使用框架

Flow Field——流场寻路算法

目的 一群物体到达某个目的地时,需要对这些海量单位做寻路和避障,类似塔防类游戏的怪物步行到终点的过程。 参考视频:https://www.bilibili.com/video/BV12bzZY2EfA 演示动画:https://howtorts.github.io/examples/4-basic-flow-f…

Bash 脚本教程

注:本文为 “Bash 脚本编写” 相关文章合辑。 BASH 脚本编写教程 as good as well于 2017-08-04 22:04:28 发布 这里有个老 American 写的 BASH 脚本编写教程,非常不错,至少没接触过 BASH 的也能看懂! 建立一个脚本 Linux 中有…

区块链期末复习3.2:比特币脚本

目录 一、输入输出脚本的执行 二、简单脚本实例及压栈过程 1.P2PK(pay to public key hash) 2、P2PH(pay to public key hash) 3.多重签名 4.比特币脚本的应用: 三、其他常见指令 1.OP_EQUAL与OP_EQ…

2024大模型在软件开发中的具体应用有哪些?(附实践资料合集)

大模型在软件开发中的具体应用非常广泛,以下是一些主要的应用领域: 自动化代码生成与智能编程助手: AI大模型能够根据开发者的自然语言描述自动生成代码,减少手动编写代码的工作量。例如,GitHub Copilot工具就是利用AI…

【数据可视化复习方向】

1.数据可视化就是数据中信息的可视化 2.数据可视化主要从数据中寻找三个方面的信息:模式、关系和异常 3.大数据可视化分类:科学可视化、信息可视化、可视分析学 4.大数据可视化作用:记录信息、分析推理、信息传播与协同 5.可视化流程&…

Python 多进程编程详解

目录 一、多进程编程简介 1. 什么是多进程 2. 多进程与多线程的区别 二、Python 中的多进程编程 1. 创建进程 2. 进程间通信 3. 进程池 4. 进程同步 5. 注意事项 三、实际应用案例 四、总结 在 Python 中,多进程编程是一种提高程序运行效率的有效手段。相…

Redis篇--应用篇1--会话存储(session共享)

1、概述 实现Session共享是构建分布式Web应用时的一个重要需求,尤其是在水平扩展和高可用性要求较高的场景下。 在分布式服务或集群服务中往往会出现这样一个问题:用户登录A服务后可以正常访问A服务中的接口。但是我们知道,分布式服务通常都…

ip-协议

文章目录 1. 网络层2. ip协议2.1 ip协议格式2.2 网段划分基本概念网段划分的两种方式为什么要网段划分?特殊的IP地址IP地址数量不足 2.3 私有IP与公网IP2.4 路由 3. IP的分片与组装为什么要分片与组装?如何分片?如何组装? 1. 网络…

ECharts散点图-气泡图,附视频讲解与代码下载

引言: ECharts散点图是一种常见的数据可视化图表类型,它通过在二维坐标系或其它坐标系中绘制散乱的点来展示数据之间的关系。本文将详细介绍如何使用ECharts库实现一个散点图,包括图表效果预览、视频讲解及代码下载,让你轻松掌握…

Jmeter录制https请求

jmeter 5.5版本,chrome浏览器 1、首先添加Test Plan-Thread Group-HTTP(S) Test Script Recorder 2、设置HTTP(S) Test Script Recorder界面的Port(监听端口,设置浏览器代理时需要与这里保持一致)、HTPS Domains(录制…

【Git 常用操作:pull push】

Git 基本概念 Git 是一个先进的开源的分布式版本控制系统,常用于管理工作内容、项目代码等功能。 Git 工作流程 图片来源:https://www.runoob.com/git/git-basic-operations.html 说明: workspace:工作区staging area&#xff…

LLaMA-Factory GLM4-9B-CHAT LoRA 指令微调实战

🤩LLaMA-Factory GLM LoRA 微调 安装llama-factory包 git clone --depth 1 https://github.com/hiyouga/LLaMA-Factory.git进入下载好的llama-factory,安装依赖包 cd LLaMA-Factory pip install -e ".[torch,metrics]" #上面这步操作会完成…

基于kraft部署kafka集群

kafka介绍 Apache Kafka 是一个开源的分布式事件流平台,被数千家公司用于高性能数据管道、流分析、数据集成和关键任务应用。 Kafka是一个拥有高吞吐、可持久化、可水平扩展,支持流式数据处理等多种特性的分布式消息流处理中间件,采用分布式…

Day13 苍穹外卖项目 工作台功能实现、Apache POI、导出数据到Excel表格

目录 1.工作台 1.1 需求分析和设计 1.1.1 产品原型 1.1.2 接口设计 1.2 代码导入 1.2.1 Controller层 1.2.2 Service层接口 1.2.3 Service层实现类 1.2.4 Mapper层 1.3 功能测试 1.4 代码提交 2.Apache POI 2.1 介绍 2.2 入门案例 2.2.1 将数据写入Excel文件 2.2.2 读取Excel文…

Web前端基础知识(三)

表单的应用非常丰富&#xff0c;可以说&#xff0c;每个网站都会用到表单。下面首先介绍表单中的form标签。 --------------------------------------------------------------------------------------------------------------------------------- <form></form&g…

NLP中的神经网络基础

一&#xff1a;多层感知器模型 1&#xff1a;感知器 解释一下&#xff0c;为什么写成 wxb>0 &#xff0c;其实原本是 wx > t ,t就是阈值&#xff0c;超过这个阈值fx就为1&#xff0c;现在把t放在左边。 在感知器里面涉及到两个问题&#xff1a; 第一个&#xff0c;特征提…

docker安装MySQL--宝塔面板操作版

记录 1 在centos中安装宝塔面板 参照宝塔面板官方网页上步骤进行操作&#xff0c;然后登录网页地址 成功后直接拉取 成功后可以在本地镜像中看到 2 创建配置文件 cd /home/mysql/conf vim my.cnf [rootplmomn-gw conf]# cat /home/mysql/conf/my.cnf [client] #设置客户端…

C++简明教程(3)(初识VS)

一、编程工具大揭秘——IDE 当我们准备踏入 C 编程的奇妙世界时&#xff0c;首先要认识一个重要的“魔法盒子”——集成开发环境&#xff08;IDE&#xff09;。IDE 就像是一个全能的编程工作室&#xff0c;它把我们写代码所需要的各种工具都整合到了一起&#xff0c;让编程这件…