【高阶数据结构(七)】B+树, 索引原理讲解

💓博主CSDN主页:杭电码农-NEO💓

⏩专栏分类:高阶数据结构专栏⏪

🚚代码仓库:NEO的学习日记🚚

🌹关注我🫵带你学习更多数据结构
  🔝🔝


在这里插入图片描述

高阶数据结构

  • 1. 前言
  • 2. B+树讲解
  • 3. B*树讲解
  • 4. 索引原理
  • 5. 总结

1. 前言

B树并不常用,就是因为有B+树的存在. MySQL的索引底层其实就是使用了B+树,请听我娓娓道来

本章重点:

本篇文章着重讲解B+树, B*树的概念和结构, 讲解引擎:MyISAM和 InnoDB的索引的底层原理


2. B+树讲解

B+树是B树的变形,是在B树基础上优化的多路平衡搜索树,B+树的规则跟B树基本类似,但是又在B树的基础上做了以下几点改进优化:

  1. 分支节点的子树指针与关键字个数相同
  2. 分支节点的子树指针p[i]指向关键字值大小在[k[i],k[i+1])区间之间
  3. 所有叶子节点增加一个链接指针链接在一起
  4. 所有关键字及其映射数据都在叶子节点出现

在这里插入图片描述

B+树的这个改进有效的减少了B树的消耗. 在最左边的叶子节点中, 是用链表将不同值链接起来的,并且父节点的关键字5就是链表的第一个元素, 链表中所有的元素都满足 5<=x<10. 所以可以看出, B树系列的数据结构就是一颗矮胖树,设计成为矮胖树的原因是查找时, 进行磁盘OI的次数少了,自然就提高效率了. 某种意义上来讲,B树系列更像是书本前面的目录, 方便你轻松的查找到一个值

在这里插入图片描述

B+树的分裂:

当一个结点满时,分配一个新的结点,并将原结点中1/2的数据复制到新结点,最后在父结点中增加新结点的指针;B+树的分裂只影响原结点和父结点,而不会影响兄弟结点,所以它不需要指向兄弟的指针。

分裂属于拓展,有兴趣可自行查资料


3. B*树讲解

B*树是B+树的变形,在B+树的非根和非叶子节点再增加指向兄弟节点的指针。

在这里插入图片描述

B*树的分裂:

当一个结点满时,如果它的下一个兄弟结点未满,那么将一部分数据移到兄弟结点中,再在原结点插入关键字,最后修改父结点中兄弟结点的关键字(因为兄弟结点的关键字范围改变了);如果兄弟也满了,则在原结点与兄弟结点之间增加新结点,并各复制1/3的数据到新结点,最后在父结点增加新结点的指针。所以,B*树分配新结点的概率比B+树要低,空间使用率更高;

在这里插入图片描述

虽然说B*树的空间利用率更高, 但是它的设计更绕更复杂, 所以在实际生活中, 反而B+树的运用场景比较多


4. 索引原理

B-树最常见的应用就是用来做索引。索引通俗的说就是为了方便用户快速找到所寻之物,比如:
书籍目录可以让读者快速找到相关信息,hao123网页导航网站,为了让用户能够快速的找到有价
值的分类网站,本质上就是互联网页面中的索引结构。

MySQL官方对索引的定义为:索引(index)是帮助MySQL高效获取数据的数据结构,简单来说:索引就是数据结构。

在这里插入图片描述

MyISAM引擎: B+树

在这里插入图片描述

MyISAM引擎的B+树的叶子节点只是保存了表数据的地址, 当你通过索引查找对应的地址后, 再使用此地址直接找到数据. 这种索引方式称为非聚簇索引

InnoDB引擎: B+

InnoDB支持B+树索引、全文索引、哈希索引。但InnoDB使用B+Tree作为索引结构时,具体实现方式却与MyISAM截然不同。第一个区别是InnoDB的数据文件本身就是索引文件。MyISAM索引文件和数据文件是分离的,索引文件仅保存数据记录的地址。而InnoDB索引,表数据文件本身就是按B+Tree组织的一个索引结构,这棵树的叶节点data域保存了完整的数据记录。这个索引的key是数据表的主键,因此InnoDB表数据文件本身就是主索引.

在这里插入图片描述

叶节点包含了完整的数据记录,这种索引叫做聚集索引. 因为InnoDB的数据文件本身要按主键聚集,所以InnoDB要求表必须有主键. 学过MySQL的伙伴可能知道, 不仅仅主键可以根据主键创建索引, 还有唯一键索引,普通索引等. 那么他们是怎样工作的呢? 答案是, 非主键索引的B+树的叶子节点中存储的是这一行对应的主键值, 然后再根据这个主键值去主键索引中找到所有数据


5. 总结

B树系列的应用一般是在磁盘,也就是外数据的查询, 它的思想是值得我们学习的

🔎 下期预告:跳表详解 🔍

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

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

相关文章

【Web】CISCN 2024初赛 题解(全)

目录 Simple_php easycms easycms_revenge ezjava mossfern sanic Simple_php 用php -r进行php代码执行 因为ban了引号&#xff0c;考虑hex2bin&#xff0c;将数字转为字符串 php -r eval(hex2bin(16进制)); 注意下面这段报错&#xff0c;因为加不了引号&#xff0c;开…

【网络原理】HTTPS详解

一.HTTPS的相关基本概念 HTTPS:由于HTTP协议内容都是按照文本的方式明文传输的. 这就导致在传输过程中出现一些被篡改的情况. 可能会出现运营商劫持,黑客入侵等不利影响, 因此就引入了HTTPS,其本质上就是在HTTP协议的基础上,引入了一个加密层SSM.什么是运营商劫持? 例如我们要…

【服务器报错】Pycharm运行服务器代码提示 can‘t open file “本地文件路径“

1. 问题 Pycharm连接远程服务器&#xff0c;代码已经同步&#xff0c;运行时候报错 #模拟报错 bash: line 0: cd: G:/python/hhh/Hi: No such file or directory /home/hhh/anaconda3/envs/hard/bin/python: cant open file G:/python/hhh/hi/hei.py: [Errno 2] No such file…

SpringBootTest测试框架五

示例 package com.xxx;import com.xxx.ut.AbstractBasicTest; import com.xxx.ut.uttool.TestModel; import com.xxx.ut.uttool.TestModelEnum; import org.junit.jupiter.api.Test; import org.springframework.beans.factory.annotation.Autowired;public class QueryXXXImp…

Keras深度学习框架第二十讲:使用KerasCV中的Stable Diffusion进行高性能图像生成

1、绪论 1.1 概念 为便于后文讨论&#xff0c;首先进行相关概念的陈述。 Stable Diffusion&#xff1a;Stable Diffusion 是一个在图像生成领域广泛使用的技术&#xff0c;尤其是用于文本到图像的转换。它基于扩散模型&#xff08;Diffusion Models&#xff09;&#xff0c;这…

软件测试金字塔,对号入座,你在哪层?

自从学习了软件测试,脑袋也清晰了,目标也明确了,就是不知道学到哪里了.中间有很多的困难也有很多成就感,你目前在那个阶段呢? 初级测试工程师 技能要求:需求分析,使用等价类边界值等方法进行用例设计,执行功能测试,发现提交跟踪bug,使用禅道,会在测试中会操作数据库进行检查和…

Android Activity 设计详解

文章目录 Android Activity 设计说明1. Activity 的生命周期2. Activity 的启动模式3. Activity 的通信4. Activity 的布局和视图管理5. Activity 的配置变化处理6. Activity 的保存和恢复状态7. Activity 的任务和返回栈 总结 Android Activity 设计说明 在 Android 中&#…

css3 笔记02

目录 01 过渡 02 rotate旋转 03 translate函数 04 真正的3D 05 动画 06 阴影 07 自定义字体库 08 自定义动画库 01 过渡 过渡属性的使用: transition-property:要过渡的css属性名 多个属性用逗号隔开 过渡所有属性就写all transition-duration: 过渡的持续时间 s秒 …

万博智云×华为云 | HyperBDR云容灾上架,开启联营联运新篇章

日前&#xff0c;万博智云HyperBDR云容灾正式入驻华为云云商店&#xff0c;成为华为云基础软件领域联营联运合作伙伴。通过联营联运&#xff0c;双方将进一步加深在产品、解决方案、渠道拓展等多方面的强强联合&#xff0c;为企业提供更加安全、高效的数据保护解决方案&#xf…

力扣503. 下一个更大元素 II

Problem: 503. 下一个更大元素 II 文章目录 题目描述思路复杂度Code 题目描述 思路 由于此题是环形数组&#xff0c;我们在利用单调栈模板的基础上还需要将给定数组扩大一倍&#xff0c;但实际上我们只需要利用取余的操作模拟扩大数组即可&#xff08;具体操作看代码。在解决有…

【简单介绍下容器是什么?】

&#x1f3a5;博主&#xff1a;程序员不想YY啊 &#x1f4ab;CSDN优质创作者&#xff0c;CSDN实力新星&#xff0c;CSDN博客专家 &#x1f917;点赞&#x1f388;收藏⭐再看&#x1f4ab;养成习惯 ✨希望本文对您有所裨益&#xff0c;如有不足之处&#xff0c;欢迎在评论区提出…

c++ (命名空间 字符串)

思维导图&#xff1a; 定义自己得命名空间myspace,在myspace中定义string类型变量s1,再定义一个函数完成字符串逆置 #include <iostream> #include <cstring> //定义自己得命名空间myspace,在myspace中定义string类型变量s1,再定义一个函数完成字符串逆置 using n…

python 办公自动化-生成ppt文本和图

最终样式 代码实现 # 可编辑折线+写入文字 成功 # 问题: 设置字体类型和加粗和字体为微软雅黑,是只改了字母和数字的字体,中文没变化 pip install pptx_ea_font 这个库可以解决这个问题 import pandas as pd import pptx_ea_font import matplotlib.pyplot as plt from pp…

社交媒体数据恢复:云叙

在使用云盘的过程中&#xff0c;由于误操作或其他原因&#xff0c;我们可能会遇到数据丢失的问题。了解云盘数据恢复的原理和技巧对于确保云盘数据安全非常重要。接下来&#xff0c;我将为您提供一份关于云盘数据恢复的教程。 一、文件恢复 当您发现文件丢失或损坏后&#xff0…

Wpf 使用 Prism 实战开发Day26

首页待办事项编辑和完成以及备忘录编辑功能 当用户双击待办事项或备忘录的时候&#xff0c;希望能进行编辑待办事项及备忘录的功能 一.在IndexView.xaml 视图&#xff0c;为待办和备忘录添加双击编辑功能 1.首先引入一个 behaviors 命名空间&#xff0c;用于进行处理鼠标双击…

K8S认证|CKA题库+答案| 14. 排查故障节点

目录 14、排查集群中的故障节点 CKA v1.29.0模拟系统 下载试用 题目&#xff1a; 开始操作&#xff1a; 1&#xff09;、切换集群 2&#xff09;、查看节点状态 ​3&#xff09;、登录故障节点并提权 4&#xff09;、检查kubelet状态 5&#xff09;、 修复kubelet进程…

实现按块复制元素的进阶技巧

新书上架~&#x1f447;全国包邮奥~ python实用小工具开发教程http://pythontoolsteach.com/3 欢迎关注我&#x1f446;&#xff0c;收藏下次不迷路┗|&#xff40;O′|┛ 嗷~~ 目录 一、按块复制元素的重要性 二、使用LED模块创建数组并复制 三、实现按块复制的具体步骤 四…

隆道专属商城 | 助力企业跨平台整合优势资源,解决采购寻源比价难题!

数字化采购时代&#xff0c;企业面临着日益激烈的市场竞争&#xff0c;如何优化资源配置、降低采购成本、提高采购效率成为企业追求的核心目标。当前&#xff0c;网上商城凭借其强大的供应链资源整合能力&#xff0c;为企业内部采购商城的搭建提供了独特的优势&#xff0c;已然…

Qt自定义标题栏

效果如下&#xff1a; 代码如下&#xff1a; // widget.h #ifndef WIDGET_H #define WIDGET_H#include <QWidget>QT_BEGIN_NAMESPACE namespace Ui { class Widget; } QT_END_NAMESPACEclass Widget : public QWidget {Q_OBJECTpublic:Widget(QWidget *parent nullptr…

加速模型训练 GPU cudnn

GPU的使用 在定义模型时&#xff0c;如果没有特定的GPU设置&#xff0c;会使用 torch.nn.DataParallel 将模型并行化&#xff0c;充分利用多GPU的性能&#xff0c;这在加速训练上有显著影响。 model torch.nn.DataParallel(model).cuda() cudnn 的配置&#xff1a; cudnn.…