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

Mysql--技术文档--B+树-数据结构的认知

阿丹解读:

之前的文章中写道了有关mysql底层索引,那么在数据量特别大的情况下。mysql采用了B+来管理索引。和存储的数据。

Mysql--技术文档--索引-《索引为什么查找数据快?》-超底层详细说明索引_一单成的博客-CSDN博客

B树解读:

Mysql--技术文档--B树-数据结构的认知_一单成的博客-CSDN博客

基本概念-B+树/B树

B树(B-tree)和B+树(B+ tree)是常见的自平衡搜索树数据结构,用于在存储和检索大量数据时提供高效的操作。它们具有一些共同的基本概念:

节点(Node):B树和B+树的数据存储在节点中。节点可以包含多个关键字和对应的指针。在B树中,叶子节点和内部节点的结构相同,都存储数据和关键字。而在B+树中,叶子节点只存储关键字和指向数据的指针,而内部节点存储关键字和指向子节点的指针。

关键字(Key):关键字是B树和B+树中用于对数据进行排序和搜索的值。关键字按照升序排列,并被存储在节点中。

指针(Pointer):指针用于连接节点,形成树的结构。在B树和B+树中,指针可以指向子节点、父节点或兄弟节点,实现树的平衡。

根节点(Root Node):根节点是B树和B+树的顶层节点。它是树的起点,通过根节点可以访问到整个树的结构。

叶节点(Leaf Node):叶节点是树的最底层节点。在B树中,叶节点存储数据和关键字。而在B+树中,叶节点只存储关键字和指向数据的指针。叶节点之间通过指针进行连接,形成一个有序的双向链表。

内部节点(Internal Node):内部节点是B树和B+树中非叶节点。它们用于指向子节点,并存储关键字。

B树和B+树作为自平衡的搜索树,具有增删改查的操作,每次操作后都会进行平衡以保持树的高度接近最小值。这样可以确保查询效率的稳定性,并提供高效的范围查询和区间搜索能力。

以上是B树和B+树的基本概念,它们在实际应用中有着广泛的应用,尤其在数据库和文件系统中用于管理和查找大量数据。


B+树

        B+树相对于B树主要有一个关键区别,那就是在每个子节点之间添加了指针。在B+树中,所有的数据记录都存储在叶子节点上,而非叶子节点只存储索引信息。每个非叶子节点都有指向其子节点的指针,形成一个链表结构,这个链表结构使得在范围查询时更加高效。而对于B树,非叶子节点既存储索引信息又存储部分数据记录。所以可以说B+树的设计更适合在数据库等需要范围查询的场景中使用。这种设计有效地减少了磁盘I/O操作的次数,提高了查询效率。

当谈到B+树和B树的区别时,以下是一些重要的方面需要考虑:

  1. 数据记录存储:在B树中,每个节点都包含索引和对应的数据记录。而在B+树中,只有叶子节点包含数据记录,而非叶子节点只包含索引信息。这使得B+树的叶子节点形成了一个有序链表,便于范围查询操作。

  2. 非叶子节点的指针:在B树中,非叶节点包含指向子节点的指针。而在B+树中,非叶子节点只包含指向子节点的指针,并且这些指针形成了一个链表结构。这样的设计可以更快地在范围查询时遍历数据。

  3. 查询性能:由于B+树的叶子节点上存储了较多的数据记录,并且有序排列,所以范围查询效率更高。而B树需要在非叶子节点和叶子节点之间来回检索,相对而言,范围查询的性能较差。

  4. 插入和删除操作:对于B+树来说,由于只需调整叶子节点的指针,所以插入和删除操作相对较快。而B树在插入和删除时可能需要在非叶子节点之间进行调整。

总体来说,B+树在数据库系统中更为常见,尤其在需要范围查询和排序的场景中非常适用。对于大型数据库,B+树的使用可以提供更高的性能和效率。而B树在一些特殊场景中可能仍然有其应用,但在绝大多数情况下,B+树是更好的选择。

B+树复杂度

B+树的复杂度取决于具体的操作,下面是一些常见操作的复杂度分析:

  1. 插入和删除:B+树的插入和删除操作通常具有O(log N)的时间复杂度,其中N是树中的节点数。插入和删除通常需要在树的高度上进行搜索,并且在找到合适的位置后,可能需要进行节点的分裂或合并操作。

  2. 查找:B+树的查找操作也具有O(log N)的时间复杂度。通过从根节点开始,根据索引值逐级搜索子节点,直到叶子节点找到目标记录。

  3. 范围查询:由于B+树的叶子节点形成有序链表,使得范围查询操作非常高效。通过定位范围的起始和结束位置,可以在O(log N + M)的时间复杂度内定位到范围内的M个记录。

注意:这些复杂度分析是对平衡的B+树而言。在实际使用中,性能可能受到硬件、存储引擎、数据分布和索引设计等多个因素的影响。因此,在特定情况下,可能需要进一步考虑这些因素以获得更准确的性能评估。

提供一个网址可手动看见树的工作流程

B-Tree Visualization

详解工作流程

  1. B+树的根节点是一个特殊的节点,存储在内存中,并且是树的入口点。根节点可以包含一些索引信息,指向下层节点。

  2. 当需要插入一条记录时,首先从根节点开始,按照索引值逐级向下搜索,找到合适的叶子节点。在叶子节点中,根据索引值的顺序将记录插入到合适的位置。

  3. 如果插入操作导致叶子节点超过了预设的容量,会进行节点的分裂操作。分裂会创建一个新的叶子节点,并将一部分记录移动到新节点中。同时,更新上层节点的索引信息以反映叶子节点的变化。

  4. 当需要删除一条记录时,同样从根节点开始搜索,找到包含目标记录的叶子节点,并将其删除。

  5. 如果删除操作导致叶子节点的记录数过少,会进行节点的合并操作。合并操作会将相邻的叶子节点合并为一个节点,并更新上层节点的索引信息。

  6. 在B+树中进行范围查询时,首先定位到起始位置和结束位置所在的叶子节点,然后按照链表结构遍历那些在范围内的叶子节点,找到满足条件的记录。

总之,B+树的工作流程是从根节点开始,按索引值逐级搜索,最终找到叶子节点来插入、删除或查询记录。在修改树的结构时,可能需要进行节点的分裂和合并操作,以保持树的平衡性。这种工作流程使得B+树在数据库中成为一种高效的索引结构,适用于大规模数据存储和高性能查询的场景。

相对于B树的升级点以及特性点

  1. 范围查询效率更高:B+树的叶子节点形成有序链表,使得范围查询操作更高效。通过链表结构,可以轻松地在范围内遍历叶子节点,从而实现更快速的范围查询。

  2. 只有叶子节点存储数据记录:在B+树中,只有叶子节点存储数据记录,而非叶子节点只存储索引信息。这种设计减少了冗余数据的存储,提高了数据存储的效率。

  3. 非叶子节点的指针:B+树的非叶子节点包含指向子节点的指针,并形成链表结构。这样的设计使得范围查询更高效,因为只需要在链表上遍历节点,而不需要返回到父节点进行下一步搜索。

  4. 插入和删除操作更高效:插入和删除操作只需要在叶子节点上进行操作,而不需要涉及到上层非叶子节点。这样可以减少操作的复杂性和开销,提高了插入和删除操作的效率。

  5. 有利于磁盘I/O的优化:B+树的有序链表结构有利于优化磁盘I/O操作。通过顺序读取叶子节点的数据记录,可以减少随机I/O的次数,提高磁盘访问的效率。

  6. 适用于大型数据库系统:由于B+树的优化特性,它更适用于大型数据库系统。B+树在处理大量数据和频繁查询时表现良好,具有更好的查询性能和数据存储效率。

总体而言,B+树相对于B树提供了更高效的范围查询、更高的插入和删除效率以及更好的存储效率。这使得B+树成为了许多数据库系统中常用的索引结构。

mysql中的B+树

在MySQL中,B+树被广泛应用于索引结构。B+树在数据库系统中解决了多个问题,并且成为了一种优秀的索引方案,这也是为什么它被使用的原因之一。

以下是MySQL中B+树的应用和解决的问题:

  1. 高效数据访问:B+树的有序链表结构和索引在叶子节点的使用,使得在数据库中高效地访问和查询数据成为可能。通过树的平衡和有序性,B+树的查询操作可以在最坏情况下以O(log N)的时间复杂度完成,这意味着即使对于大量数据,查询也可以很快完成。

  2. 范围查询优化:B+树的特性之一是叶子节点形成有序链表,这使得范围查询的执行非常高效。例如,对于给定的范围条件,可以直接定位到范围内的第一个叶子节点,并沿着链表顺序遍历到最后一个满足条件的叶子节点,从而减少了搜索的次数。

  3. 数据排序:B+树可以根据索引的有序性来对数据进行排序。当表使用B+树作为主键索引时,在插入新记录或更新现有记录时,B+树会自动维护有序性。

  4. 减少磁盘访问:B+树的有序链表结构和索引的使用有助于优化磁盘I/O操作。通过顺序读取叶子节点,可以减少磁盘随机I/O的次数,从而提高了查询性能。

  5. 支持快速插入和删除:B+树的插入和删除操作通常只需要操作叶子节点,不涉及上层非叶子节点。这减少了操作的复杂性和开销,提高了插入和删除操作的效率。

总的来说,MySQL中的B+树应用广泛,它解决了高效数据访问、范围查询优化、数据排序和减少磁盘访问等问题。使用B+树作为索引结构可以提供更好的查询性能、支持大型数据库系统,并且具备高效的数据插入和删除操作。

相关文章:

Mysql--技术文档--B+树-数据结构的认知

阿丹解读: 之前的文章中写道了有关mysql底层索引,那么在数据量特别大的情况下。mysql采用了B来管理索引。和存储的数据。 Mysql--技术文档--索引-《索引为什么查找数据快?》-超底层详细说明索引_一单成的博客-CSDN博客 B树解读&#xff1a…...

cms之wordpress主题安装

WordPress主题安装教程的方法有两种,分为在线安装和上传安装,下面是主题详细安装方法的步骤。 后台在线安装主题 从后台的主题界面在线安装主题是最方便的WordPress主题安装方式。方法如下: 1 在WordPress后台,转到外观→主题 …...

【Python程序设计】Python 中的环境变量【05/8】

一、说明 以下文章是有关 Python 数据工程系列文章的一部分,旨在帮助数据工程师、数据科学家、数据分析师、机器学习工程师或其他刚接触 Python 的人掌握基础知识。本篇将讲述环境变量的问题。 迄今为止,本初学者指南包括: 第 1 部分&#xf…...

查漏补缺 - ES6

目录 1,let 和 const1,会产生块级作用域。2,如何理解 const 定义的变量不可被修改? 2,数组3,对象1,Object.is()2,属性描述符3,常用API4,得到除某个属性之外的新对象。 4…...

基于视觉重定位的室内AR导航APP的大创项目思路(1):最初的项目思路(SLAM)

文章目录 最初的项目思路(SLAM):后文: 前情提要: 是第一次做项目的小白,文章内的资料介绍如有错误,请多包含! 最初的项目思路(SLAM): 由于我们在…...

C 编译原理

C 编译原理 目录 C 编译原理引入GCC 工具链介绍C运行库 编译准备工作编译过程1.预处理2.编译3.汇编4.链接 分析ELF文件1.ELF文件的段2.反汇编ELF C语言编译过程 - 摘录编译预处理编译、优化汇编链接过程 引入 大家肯定都知道计算机程序设计语言通常分为机器语言、汇编语言和高…...

服务管理工具systemctl

服务管理工具systemctl Linux服务管理两种方式 service 和 systemctl systemd 是Linux系统最新的初始化系统(init),作用是提高系统的启动速度,尽可能启动较少的进程,尽可能更多进程并发启动. systemd 对应的进程管理命令是systemctlsystemctl 是systemd的主命令,用于管理系统…...

Spring boot环境搭建

使用IDE工具:IntelliJ IDEA 目录 一、安装JAVA 二、安装maven(Java项目管理工具) 三、安装IDE 四、在IDE中配置spring boot项目环境 1、配置jdk 2、配置maven 3、安装创建spring boot项目插件:Spring Assistant 4、安装简…...

【C++】list的模拟实现【完整理解版】

目录 一、list的概念引入 1、vector与list的对比 2、关于struct和class的使用 3、list的迭代器失效问题 二、list的模拟实现 1、list三个基本函数类 2、list的结点类的实现 3、list的迭代器类的实现 3.1 基本框架 3.2构造函数 3.3 operator* 3.4 operator-> 3…...

Linux C++ OpenVINO 物体检测 Demo

目录 main.cpp #include <iostream> #include <string> #include <vector> #include <openvino/openvino.hpp> #include <opencv2/opencv.hpp> #include <dirent.h> #include <stdio.h> #include <time.h> #include …...

解决运行Docker镜像报错:version `GLIBC_2.32‘ not found

解决运行Docker镜像&#xff0c;报错&#xff1a;version GLIBC_2.32’ not found 详细报错日志 xapi-backend % docker logs 036de55b5bc6 ./xapi-backend: /lib/aarch64-linux-gnu/libc.so.6: version GLIBC_2.32 not found (required by ./xapi-backend) ./xapi-backend: …...

网络层--IP协议

引入&#xff1a; IP协议主要解决什么问题呢&#xff1f; IP协议提供一种将数据从主机&#xff21; 发送到 主机&#xff22;的能力。&#xff08;有能力不一定能做到&#xff0c;比如小明很聪明&#xff0c;可以考100分&#xff0c;但是他也不是每次搜能考100分&#xff0…...

Vue2 | Vant uploader实现上传文件和图片

需求&#xff1a; 实现图片和文件的上传&#xff0c;单个图片超过1M则压缩&#xff0c;全部文件加起来不得超过10M。 效果&#xff1a; 1. html <van-form ref"form"><van-field name"uploader" label"佐证材料" required><t…...

第二十一章 Classes

文章目录 第二十一章 ClassesClasses类名和包类定义的基本内容 第二十一章 Classes Classes 类定义并不是 ObjectScript 的正式组成部分。相反&#xff0c;可以在类定义的特定部分中使用 ObjectScript&#xff08;特别是在方法定义中&#xff0c;可以在其中使用其他实现语言&…...

Ubuntu不能上网解决办法

问题及现象 Ubuntu的虚拟机&#xff08;18.04&#xff09;总是莫名就不能上网了。 使用ifconfig -a 查看&#xff0c;ensxx&#xff08;xx为虚拟机分配的id号&#xff09;对应的网卡有mac地址&#xff0c;但是没有分配ip地址。 Network中也没有Wired的选项。 临时解决方案 使…...

百度飞浆OCR识别表格入门python实践

1. 百度飞桨&#xff08;PaddlePaddle&#xff09; 百度飞桨&#xff08;PaddlePaddle&#xff09;是百度推出的一款深度学习平台&#xff0c;旨在为开发者提供强大的深度学习框架和工具。飞桨提供了包括OCR&#xff08;光学字符识别&#xff09;在内的多种功能&#xff0c;可…...

直接插入排序、希尔排序详解。及性能比较

直接插入排序、希尔排序详解。及性能比较 一、 直接插入排序1.1 插入排序原理1.2 代码实现1.3 直接插入排序特点总结 二、希尔排序 ( 缩小增量排序 )2.1 希尔排序原理2.2 代码实现2.3 希尔排序特点总结 三、直接插入排序和希尔排序性能大比拼 !!!3.1 如何对比性能&#xff1f;准…...

2023备战秋招Java面试八股文合集

Java就业大环境仍然根基稳定&#xff0c;市场上有很多机会&#xff0c;技术好的人前景就好&#xff0c;就看你有多大本事了。小编得到了一份很不错的资源&#xff0c;建议大家可以认真地来看看以下的资料&#xff0c;来提升一下自己的核心竞争力&#xff0c;在面试中轻松应对面…...

SLAM中的二进制词袋生成过程和工作原理

长期视觉SLAM (Simultaneous Localization and Mapping)最重要的要求之一是鲁棒的位置识别。经过一段探索期后&#xff0c;当长时间未观测到的区域重新观测时&#xff0c;标准匹配算法失效。 当它们被健壮地检测到时&#xff0c;回环检测提供正确的数据关联以获得一致的地图。…...

算法训练第五十九天

503. 下一个更大元素 II - 力扣&#xff08;LeetCode&#xff09; 代码&#xff1a; class Solution { public:vector<int> nextGreaterElements(vector<int>& nums) {vector<int> nums1(nums.begin(), nums.end());nums.insert(nums.end(), nums1.beg…...

K8S认证|CKS题库+答案| 11. AppArmor

目录 11. AppArmor 免费获取并激活 CKA_v1.31_模拟系统 题目 开始操作&#xff1a; 1&#xff09;、切换集群 2&#xff09;、切换节点 3&#xff09;、切换到 apparmor 的目录 4&#xff09;、执行 apparmor 策略模块 5&#xff09;、修改 pod 文件 6&#xff09;、…...

.Net框架,除了EF还有很多很多......

文章目录 1. 引言2. Dapper2.1 概述与设计原理2.2 核心功能与代码示例基本查询多映射查询存储过程调用 2.3 性能优化原理2.4 适用场景 3. NHibernate3.1 概述与架构设计3.2 映射配置示例Fluent映射XML映射 3.3 查询示例HQL查询Criteria APILINQ提供程序 3.4 高级特性3.5 适用场…...

MongoDB学习和应用(高效的非关系型数据库)

一丶 MongoDB简介 对于社交类软件的功能&#xff0c;我们需要对它的功能特点进行分析&#xff1a; 数据量会随着用户数增大而增大读多写少价值较低非好友看不到其动态信息地理位置的查询… 针对以上特点进行分析各大存储工具&#xff1a; mysql&#xff1a;关系型数据库&am…...

1688商品列表API与其他数据源的对接思路

将1688商品列表API与其他数据源对接时&#xff0c;需结合业务场景设计数据流转链路&#xff0c;重点关注数据格式兼容性、接口调用频率控制及数据一致性维护。以下是具体对接思路及关键技术点&#xff1a; 一、核心对接场景与目标 商品数据同步 场景&#xff1a;将1688商品信息…...

什么是库存周转?如何用进销存系统提高库存周转率?

你可能听说过这样一句话&#xff1a; “利润不是赚出来的&#xff0c;是管出来的。” 尤其是在制造业、批发零售、电商这类“货堆成山”的行业&#xff0c;很多企业看着销售不错&#xff0c;账上却没钱、利润也不见了&#xff0c;一翻库存才发现&#xff1a; 一堆卖不动的旧货…...

【配置 YOLOX 用于按目录分类的图片数据集】

现在的图标点选越来越多&#xff0c;如何一步解决&#xff0c;采用 YOLOX 目标检测模式则可以轻松解决 要在 YOLOX 中使用按目录分类的图片数据集&#xff08;每个目录代表一个类别&#xff0c;目录下是该类别的所有图片&#xff09;&#xff0c;你需要进行以下配置步骤&#x…...

unix/linux,sudo,其发展历程详细时间线、由来、历史背景

sudo 的诞生和演化,本身就是一部 Unix/Linux 系统管理哲学变迁的微缩史。来,让我们拨开时间的迷雾,一同探寻 sudo 那波澜壮阔(也颇为实用主义)的发展历程。 历史背景:su的时代与困境 ( 20 世纪 70 年代 - 80 年代初) 在 sudo 出现之前,Unix 系统管理员和需要特权操作的…...

QT: `long long` 类型转换为 `QString` 2025.6.5

在 Qt 中&#xff0c;将 long long 类型转换为 QString 可以通过以下两种常用方法实现&#xff1a; 方法 1&#xff1a;使用 QString::number() 直接调用 QString 的静态方法 number()&#xff0c;将数值转换为字符串&#xff1a; long long value 1234567890123456789LL; …...

图表类系列各种样式PPT模版分享

图标图表系列PPT模版&#xff0c;柱状图PPT模版&#xff0c;线状图PPT模版&#xff0c;折线图PPT模版&#xff0c;饼状图PPT模版&#xff0c;雷达图PPT模版&#xff0c;树状图PPT模版 图表类系列各种样式PPT模版分享&#xff1a;图表系列PPT模板https://pan.quark.cn/s/20d40aa…...

学校时钟系统,标准考场时钟系统,AI亮相2025高考,赛思时钟系统为教育公平筑起“精准防线”

2025年#高考 将在近日拉开帷幕&#xff0c;#AI 监考一度冲上热搜。当AI深度融入高考&#xff0c;#时间同步 不再是辅助功能&#xff0c;而是决定AI监考系统成败的“生命线”。 AI亮相2025高考&#xff0c;40种异常行为0.5秒精准识别 2025年高考即将拉开帷幕&#xff0c;江西、…...