【高阶数据结构(七)】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树的基础上做了以下几点改进优化:
- 分支节点的子树指针与关键字个数相同
- 分支节点的子树指针p[i]指向关键字值大小在[k[i],k[i+1])区间之间
- 所有叶子节点增加一个链接指针链接在一起
- 所有关键字及其映射数据都在叶子节点出现

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树系列的应用一般是在磁盘,也就是外数据的查询, 它的思想是值得我们学习的
相关文章:
【高阶数据结构(七)】B+树, 索引原理讲解
💓博主CSDN主页:杭电码农-NEO💓 ⏩专栏分类:高阶数据结构专栏⏪ 🚚代码仓库:NEO的学习日记🚚 🌹关注我🫵带你学习更多数据结构 🔝🔝 高阶数据结构 1. 前言2. B树讲解…...
ML307R OpenCPU 网络初始化流程介绍
一、网络初始化流程 二、函数介绍 三、示例代码 四、代码下载地址 一、网络初始化流程 模组的IMEI/SN获取接口可在include\cmiot\cm_sys.h中查看,SIM卡IMSI/ICCID获取接口可以在include\cmiot\cm_sim.h中查看,PDP激活状态查询可以在include\cmiot\cm_modem.h中查看 二、函…...
分享:怎么才能保证大数据查询的准确性?
随着大数据应用到金融风控领域,大数据越来越重要了,很多朋友在查大数据的时候都会遇到一个问题,那就是自己查询的大数据什么信息都没有,要么就是很少,这是什么原因呢?要怎么才能保证大数据查询的准确性呢?下面小编就…...
AI Agent教育行业落地案例
【AI赋能教育】揭秘Duolingo背后的AI Agent,让学习更高效、更有趣! ©作者|Blaze 来源|神州问学 引言 随着科技的迅猛发展,人工智能技术已经逐步渗透到我们生活的各个方面。而随着AI技术的广泛应用,教育培训正引领着一场新的…...
Flutter 中的 LimitedBox 小部件:全面指南
Flutter 中的 LimitedBox 小部件:全面指南 Flutter 是一个功能强大的 UI 框架,它提供了大量的小部件来帮助开发者构建美观且响应式的用户界面。在 Flutter 的布局小部件中,LimitedBox 是一个不太常见但非常有用的组件,它可以用来…...
OrangePi AIpro初体验,码农的第一台个人AI云电脑
介绍 香橙派联合华为精心打造,建设人工智能新生态 官网地址:Orange Pi AIpro Orange Pi官网-香橙派 Orange Pi论坛:Orange Pi论坛 昇腾社区:为开发者免费提供数百个代码参考样例昇腾社区-官网丨昇腾万里 让智能无所不及 学习…...
剪画小程序:”霸屏各大平台“的黏土滤镜是怎么制作的呢?
最近,网上出现大量“黏土”风格的人物照片。尤其是在社交平台,这类型的分享数量急剧上升。 这是马斯克开车的样子 还有这张是周杰伦七里香的专辑图片 一张照片,十几秒钟,就能还原出你在黏土世界的样子。 以上这些照片是用-【剪画…...
图解 BERT 模型
节前,我们星球组织了一场算法岗技术&面试讨论会,邀请了一些互联网大厂朋友、参加社招和校招面试的同学. 针对算法岗技术趋势、大模型落地项目经验分享、新手如何入门算法岗、该如何准备、面试常考点分享等热门话题进行了深入的讨论。 汇总合集&…...
关于软件设计模式的理解
系列文章 关于时间复杂度o(1), o(n), o(logn), o(nlogn)的理解 关于HashMap的哈希碰撞、拉链法和key的哈希函数设计 关于JVM内存模型和堆内存模型的理解 关于代理模式的理解 关于Mysql基本概念的理解 关于软件设计模式的理解 文章目录 前言一、软件设计模式遵循的六大原则…...
Java开发官方文档
Spring中文网 Spring Cloud中文网 Hutool工具类 Ant Design官方文档 遇见狂神说学习文档 若依后台管理系统测试环境 FineBI官方文档 vscode教程 新一代微服务全家桶AlibabaCloudSpringCloud实战 分布式任务调度平台XXL-JOB...
AI大模型探索之路-实战篇9:探究Agent智能数据分析平台的架构与功能
系列篇章💥 AI大模型探索之路-实战篇4:深入DB-GPT数据应用开发框架调研 AI大模型探索之路-实战篇5:探索Open Interpreter开放代码解释器调研 AI大模型探索之路-实战篇6:掌握Function Calling的详细流程 AI大模型探索之路-实战篇7…...
本地spark3.5(不整合hive) 集成paimon0.9
spark官网下载集成hadoop的spark包: spark-3.5.1-bin-hadoop3.... 解压后 环境变量配置 SPARK_HOME spark-defaults.conf 中增加一行配置(避免启动spark-sql报错hive元数据连不上): spark.sql.catalogImplementationhive 打开paimon官网: https://paimon.apache.org/docs/mas…...
Linux IO模型深度解析与实战应用
linux的5种IO模型 一、这里IO是什么 操作系统设有用户态与内核态,确保系统安全。应用程序默认在用户态运行,而执行如IO操作等底层任务时,需切换至内核态以高效执行。 服务器从网络接收的大致流程如下: 1、数据通过计算机网络来到了网卡 2、把网卡的数据读取到 socket 缓…...
软件系统开发标准流程文档(Word原件)
目的:规范系统开发流程,提高系统开发效率。 立项申请需求分析方案设计方案评审开发调整测试阶段系统培训试运行测试验收投入使用 所有文档过去进主页获取。 软件项目相关全套精华资料包获取方式①:点我获取 获取方式②:本文末个人…...
嵌入式进阶——外部中断(EXTI)
🎬 秋野酱:《个人主页》 🔥 个人专栏:《Java专栏》《Python专栏》 ⛺️心若有所向往,何惧道阻且长 文章目录 STC8H中断外部中断外部中断编写配置外部中断调用中断触发函数 外部中断测试测试外部中断0测试外部中断2、3或者4 PCB中断设计 STC8…...
flinkcdc 3.0 源码学习之客户端flink-cdc-cli模块
注意 : 本文章是基于flinkcdc 3.0 版本写的 我们在前面的文章已经提到过,flinkcdc3.0版本分为4层,API接口层,Connect链接层,Composer同步任务构建层,Runtime运行时层,这篇文章会对API接口层进行一个探索.探索一下flink-cdc-cli模块,看看是如何将一个yaml配置文件转换成一个任务…...
香橙派 AIpro开发体验:使用YOLOV8对USB摄像头画面进行目标检测
香橙派 AIpro开发体验:使用YOLOV8对USB摄像头画面进行目标检测 前言一、香橙派AIpro硬件准备二、连接香橙派AIpro1. 通过网线连接路由器和香橙派AIpro2. 通过wifi连接香橙派AIpro3. 使用vscode 通过ssh连接香橙派AIpro 三、USB摄像头测试1. 配置ipynb远程开发环境1.…...
Python中正则表达式详解
Python中正则表达式详解 引言 正则表达式是一种用于字符串搜索和操作的强大工具。它使用单个字符串来描述、匹配一系列符合某个句法规则的字符串。在Python中,正则表达式通过内置的re模块来实现,使得文本处理变得简洁而高效。 正则表达式基础 在深入…...
vue使用EventBus进行跨组件通信
Vue中的EventBus,又称为事件总线,是一种常用的通信模式,它允许在Vue应用程序的不同组件之间进行松耦合的通信,尤其是对于那些没有直接父子关系的组件间的通信非常有用。EventBus基于Vue的自定义事件系统实现,工作原理遵…...
boot项目中定时任务quartz
最近换项目组,发现项目中定时任务使用的是quartz框架,上一篇文章[springboot定时任务]也是使用的quartz,只不过实现方式不同,于是整理下 定时任务常用方法有Quartz,Spring自带的Schedule框架 Quartz基础知识 quartz…...
【根据当天日期输出明天的日期(需对闰年做判定)。】2022-5-15
缘由根据当天日期输出明天的日期(需对闰年做判定)。日期类型结构体如下: struct data{ int year; int month; int day;};-编程语言-CSDN问答 struct mdata{ int year; int month; int day; }mdata; int 天数(int year, int month) {switch (month){case 1: case 3:…...
智慧工地云平台源码,基于微服务架构+Java+Spring Cloud +UniApp +MySql
智慧工地管理云平台系统,智慧工地全套源码,java版智慧工地源码,支持PC端、大屏端、移动端。 智慧工地聚焦建筑行业的市场需求,提供“平台网络终端”的整体解决方案,提供劳务管理、视频管理、智能监测、绿色施工、安全管…...
Redis相关知识总结(缓存雪崩,缓存穿透,缓存击穿,Redis实现分布式锁,如何保持数据库和缓存一致)
文章目录 1.什么是Redis?2.为什么要使用redis作为mysql的缓存?3.什么是缓存雪崩、缓存穿透、缓存击穿?3.1缓存雪崩3.1.1 大量缓存同时过期3.1.2 Redis宕机 3.2 缓存击穿3.3 缓存穿透3.4 总结 4. 数据库和缓存如何保持一致性5. Redis实现分布式…...
在QWebEngineView上实现鼠标、触摸等事件捕获的解决方案
这个问题我看其他博主也写了,要么要会员、要么写的乱七八糟。这里我整理一下,把问题说清楚并且给出代码,拿去用就行,照着葫芦画瓢。 问题 在继承QWebEngineView后,重写mousePressEvent或event函数无法捕获鼠标按下事…...
Chromium 136 编译指南 Windows篇:depot_tools 配置与源码获取(二)
引言 工欲善其事,必先利其器。在完成了 Visual Studio 2022 和 Windows SDK 的安装后,我们即将接触到 Chromium 开发生态中最核心的工具——depot_tools。这个由 Google 精心打造的工具集,就像是连接开发者与 Chromium 庞大代码库的智能桥梁…...
五子棋测试用例
一.项目背景 1.1 项目简介 传统棋类文化的推广 五子棋是一种古老的棋类游戏,有着深厚的文化底蕴。通过将五子棋制作成网页游戏,可以让更多的人了解和接触到这一传统棋类文化。无论是国内还是国外的玩家,都可以通过网页五子棋感受到东方棋类…...
Python训练营-Day26-函数专题1:函数定义与参数
题目1:计算圆的面积 任务: 编写一个名为 calculate_circle_area 的函数,该函数接收圆的半径 radius 作为参数,并返回圆的面积。圆的面积 π * radius (可以使用 math.pi 作为 π 的值)要求:函数接收一个位置参数 radi…...
从零开始了解数据采集(二十八)——制造业数字孪生
近年来,我国的工业领域正经历一场前所未有的数字化变革,从“双碳目标”到工业互联网平台的推广,国家政策和市场需求共同推动了制造业的升级。在这场变革中,数字孪生技术成为备受关注的关键工具,它不仅让企业“看见”设…...
Java并发编程实战 Day 11:并发设计模式
【Java并发编程实战 Day 11】并发设计模式 开篇 这是"Java并发编程实战"系列的第11天,今天我们聚焦于并发设计模式。并发设计模式是解决多线程环境下常见问题的经典解决方案,它们不仅提供了优雅的设计思路,还能显著提升系统的性能…...
MySQL体系架构解析(三):MySQL目录与启动配置全解析
MySQL中的目录和文件 bin目录 在 MySQL 的安装目录下有一个特别重要的 bin 目录,这个目录下存放着许多可执行文件。与其他系统的可执行文件类似,这些可执行文件都是与服务器和客户端程序相关的。 启动MySQL服务器程序 在 UNIX 系统中,用…...
