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+树作为索引的数据结构

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

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

相关文章

打造高效租赁小程序让交易更便捷

内容概要 在如今节奏飞快的商业世界里,租赁小程序如同一只聪明的小狐狸,迅速突围而出,成为商家与消费者之间的桥梁。它不仅简化了交易流程,还在某种程度上将传统租赁模式带入了互联网时代。越来越多的企业意识到,这种…

抓取手机HCI日志

荣耀手机 1、打开开发者模式 2、开启HCI、ADB调试 3、开启AP LOG 拨号界面输入*##2846579##* 4、蓝牙配对 5、抓取log adb pull /data/log/bt ./

GPT人工智能在医疗文档中的应用

应用场景 用于文档的整理。主要是针对医疗方面的文档整理。病人在打官司或者办理其他业务时,需要把很多文档整理成册并添加目录、编写概要(Summary)。这些文档有电子版本的,有纸质的扫描件,还有拍照(一般是…

GitCode 光引计划投稿 | GoIoT:开源分布式物联网开发平台

GoIoT 是基于Gin 的开源分布式物联网(IoT)开发平台,用于快速开发,部署物联设备接入项目,是一套涵盖数据生产、数据使用和数据展示的解决方案。 GoIoT 开发平台,它是一个企业级物联网平台解决方案&#xff…

golang 并发--goroutine(四)

golang 语言最大的特点之一就是语法上支持并发,通过简单的语法很容易就能创建一个 go 程,这就使得 golang 天生适合写高并发的程序。这一章节我们就主要介绍 go 程,但是要想完全理解 go 程我们需要深入研究 GPM 模型,关于 GPM 模型…

选择FPGA开发,学历是硬性要求吗?

在踏入FPGA开发领域之前,心中难免会泛起的疑虑。 选择FPGA开发,就一定需要高学历作为支撑吗? 一、先说结论:学历非必需,但建议不断提升自我。 FPGA开发的门槛意味着你需要投入比其他行业更多的时间和精力去学习&…

面试场景题系列:设计一致性哈希系统

为了实现横向扩展,在服务器之间高效和均匀地分配请求/数据是很重要的。一致性哈希是为了达成这个目标而被广泛使用的技术。首先,我们看一下什么是重新哈希问题。 1 重新哈希的问题 如果你有n个缓存服务器,常见的平衡负载的方法是使用如下哈希…

778-批量删除指定文件夹下指定格式文件(包含子孙文件夹下的)

778-批量删除指定文件夹下指定格式文件(包含子孙文件夹下的) 批量删除指定文件夹下所有指定格式文件,包括子孙文件夹下 文件扩展名输入时一行一个,可以同时删除多个格式文件, 输入格式是可以带.也可以不带&#xff…

MarkItDown的使用(将Word、Excel、PDF等转换为Markdown格式)

MarkItDown的使用(将Word、Excel、PDF等转换为Markdown格式) 本文目录: 零、时光宝盒🌻 一、简介 二、安装 三、使用方法 3.1、使用命令行形式 3.2、用 Python 调用 四、总结 五、参考资料 零、时光宝盒🌻 &a…

数字工厂管理系统就是ERP系统吗

在制造业数字化转型的进程中,数字工厂管理系统与ERP系统常常被提及,不少人疑惑这两者是否为同一概念。事实上,它们虽有联系,却存在诸多显著差异。 ERP系统,即企业资源计划系统,其核心在于对企业全方位资源的…

【Linux】Linux开发利器:make与Makefile自动化构建详解

Linux相关知识点可以通过点击以下链接进行学习一起加油!初识指令指令进阶权限管理yum包管理与vim编辑器GCC/G编译器 在现代软件开发中,自动化构建工具显得尤为重要,make和Makefile是Linux环境下的常用选择。它们通过定义规则和依赖关系&#…

【MinIO系列】MinIO Client (mc) 完全指南

💝💝💝欢迎来到我的博客,很高兴能够在这里和您见面!希望您在这里可以感受到一份轻松愉快的氛围,不仅可以获得有趣的内容和知识,也可以畅所欲言、分享您的想法和见解。 推荐:kwan 的首页,持续学…

在跨平台开发环境中构建高效的C++项目:从基础到最佳实践20241225

在跨平台开发环境中构建高效的C项目:从基础到最佳实践 引言 在现代软件开发中,跨平台兼容性和高效开发流程是每个工程师追求的目标。尤其是对于 C 开发者,管理代码的跨平台构建以及调试流程可能成为一项棘手的挑战。在本文中,我…

2. SQL窗口函数使用

背景 窗口函数也叫分析函数,主要用于处理相对复杂的报表统计分析场景,这个功能在大多商业数据库和部分开源数据库中已经支持,mysql从8.0开始支持窗口函数。经典使用场景是数据错位相减的场景,比如求查询每年支付时间间隔最长的用…

Qt creator ,语言家功能缺失解决方法

1、找到工具->外部->配置 2、添加目录,双击命名语言家 3、在语言家目录下,添加工具 双击重命名lupdate,即更新翻译 %{CurrentDocument:Project:QT_INSTALL_BINS}\lupdate%{CurrentDocument:Project:FilePath}%{CurrentDocument:Projec…

软件测试之全链路压测详解

随着业务的快速发展我们日常遇到的系统性能压力问题也逐渐出现,甚至在部分场合会遇到一些突发的营销活动,会导致系统性能突然暴涨,可能导致我们系统的瘫痪。最近几年随着电商的各种促销活动,有一个词也渐渐进入我们眼帘&#xff0…

基于推理的目标检测 DetGPT

基于推理的目标检测 DetGPT flyfish detgpt.github.io 近年来,由于大型语言模型(LLMs)的发展,计算机视觉领域取得了重大进展。这些模型使人类与机器之间能够进行更有效、更复杂的交互,为模糊人类与机器智能界限的新技…

优化 invite_codes 表的 SQL 创建语句

-- auto-generated definition create table invite_codes (id int auto_incrementprimary key,invite_code varchar(6) not null comment 邀请码,6位整数,确保在有效期内…

如何在 Ubuntu 22.04 上安装以及使用 MongoDB

简介 MongoDB 因其灵活性、可扩展性、性能和生态系统而受到开发人员的青睐,这些都是构建和驱动现代应用程序的关键能力。通过几个配置步骤,你就可以在你的 Ubuntu 22.04 LTS 机器上安装 MongoDB,这是 Ubuntu Linux 发行版的最新长期支持版本…

小程序app封装公用顶部筛选区uv-drop-down

参考ui:DropDown 下拉筛选 | 我的资料管理-uv-ui 是全面兼容vue32、nvue、app、h5、小程序等多端的uni-app生态框架 样式示例&#xff1a; 封装公用文件代码 dropDownTemplete <template><!-- 顶部下拉筛选区封装公用组件 --><view><uv-drop-down ref&…