[高阶数据结构八] B+树和索引原理深度解析

1.前言

B树并不常用,就是因为有B+树的存在. MySQL的索引底层其实就是使用了B+树,但是B+树和索引都是在了解了B树之后才深度学习的,如果你对于B树海一无所知的话,请阅读下面这篇文章。

[高阶数据结构三] B-树详解_b-树csdn-CSDN博客

本章重点:

本章着重讲解B+树与B树的区别,以及mysql中相关索引的原理。

2.B+树的原理

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

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

B+树所有的非叶子节点都是不存储数据的,只有在叶子节点上面才会存储数据。所以在B+树中的查找时,只有找到叶子节点上面,才能够找到数据,非叶子节点是不可能获得数据的。

B+树的插入和删除这里就不过多的进行赘述,想了解的可自行查找资料。

3.B*树的原理

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

B*树和B+树一样,只有在叶子节点才可能命中数据,而对于B*树来说,由于增加了兄弟之间的指针连接,那么当进行范围的查找数据时,可以不用反复的从根节点出发查找,而是直接在兄弟节点通过指针来进行遍历访问。这样可以减少IO的次数

通过学习B树,B+树,B*树

4.索引的原理

B- 树最常见的应用就是用来做索引 。索引通俗的说就是为了方便用户快速找到所寻之物,比如: 书籍目录可以让读者快速找到相关信息,hao123 网页导航网站,为了让用户能够快速的找到有价 值的分类网站,本质上就是互联网页面中的索引结构。
MySQL官方对索引的定义为:索引(index)是帮助MySQL高效获取数据的数据结构,简单来说:索引就是数据结构。
当数据量很大时,为了能够方便管理数据,提高数据查询的效率,一般都会选择将数据保存到数据库,因此数据库不仅仅是帮助用户管理数据,而且数据库系统还维护着满足特定查找算法的数 据结构,这些数据结构以某种方式引用数据,这样就可以在这些数据结构上实现高级查找算法, 该数据结构就是索引。

MySQL里面有两种索引:Innodb和MyiSAM索引。

MyISAM引擎: B+树

注意:MyiSAM索引在这里面叶子节点存储的并不是数据,而是数据所在磁盘中的地址,如果需要访问数据,还需要拿着这个地址再进行一次IO去磁盘中访问数据。

 上面使用的是主键索引,如果还需要除了主键索引以外的其他索引,那么在MyiSAM这个搜索引擎上面也是可以的。

例如:以col2做一个普通索引

普通索引存储的也是数据在磁盘中的地址,然后想要访问数据也是根据地址再进行一次IO,去磁盘中寻找数据。


总结:

使用的数据结构是一棵 B+Tree data 域保存数据记录的地址。因此, MyISAM 中索引检索的算法为首先按 照B+Tree 搜索算法搜索索引,如果指定的 Key 存在,则取出其 data 域的值,然后以 data 域的值为 地址,读取相应数据记录。 MyISAM的索引方式也叫做“非聚集索引”的 。非聚簇索引简单理解就是数据和KEY值时分离的。
并且MyISAM这个索引是不支持事物的,但是它支持全文索引。--如果需要知道全文索引和事物的可以自行查找资料,这里就不过多进行展开叙述了。
Innodb索引:
InnoDB 存储引擎支持事务 ,其设计目标主要面向在线事务处理的应用,从 MySQL 数据库 5.5.8 本开始, InnoDB 存储引擎是默认的存储引擎 InnoDB 支持 B+ 树索引、全文索引、哈希索引。但 InnoDB使用 B+Tree 作为索引结构时,具体实现方式却与 MyISAM 截然不同。
例:使用主键索引

当使用主键索引时,数据和KEY值是没有分离的,当找到了KEY值,那么就可以直接读取数据,而在MyISAM中,找到了KEY值,还需要进行一次IO。

这种数据和KEY值不分离的索引也可以称之为聚簇索引。

如果需要使用普通索引的话,那么普通索引的叶子节点存储的是普通索引在表中对应的主键索引的值。

例:

结论:在InNoDB中,除了主键索引的叶子节点是存储数据的以外,其他任何索引(普通索引,唯一键索引等)叶子节点存储的都是主键索引的值,想通过普通索引来找到数据,那么就需要先找到主键索引,然后再根据主键索引,查找到对应的值。

那肯定有人就有疑问了,那如果我自己没有设置主键索引呢,只设置了普通索引该怎么办呢?

因为InnoDB的数据文件本身要按主键聚集,所以InnoDB要求表必须有 主键(MyISAM可以没有),如果没有显式指定,则MySQL系统会自动选择一个可以唯一标识数 据记录的列作为主键如果不存在这种列,则MySQL自动为InnoDB表生成一个隐含字段作为主键,那么普通索引的叶子节点对应的主键就是自动生成的这个主键。

总结:在InNoDB中,只有主键索引中的叶子节点才会存储数据,其他的索引的叶子节点根本不存储数据,叶子节点存储的是主键索引的值。当使用Innodb做索引值时,需要多次进行磁盘的IO才能够找到真正的数据。

5.总结

对于索引这一块并没有阐述的非常细致,因为我们这毕竟是在阐述数据结构,并不牵涉数据库,如果对于索引,事物这一块感兴趣,可以后续自行查找资料学习MYSQL。

高阶数据结构写到这就全部讲解完毕了,希望对大家能有所帮助。

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

如若内容造成侵权/违法违规/事实不符,请联系一条长河网进行投诉反馈,一经查实,立即删除!

相关文章

Gitee配置以及如何将本地项目提交到远程仓库

文章目录 准备远程仓库配置注册新建仓库 配置git 生成ssh,输入以下命令,然后连敲三次回车键配置公钥本地代码上传 准备 1.本地下载git 2.注册远程仓库账号 远程仓库配置 注册 官网:https://gitee.com 完成注册 新建仓库 头像->设置-…

圣桥ERP queryForString.dwr SQL注入漏洞复现

0x01 产品描述: 杭州圣乔科技有限公司主要研发全套工业企业ERP系列软件产品,现在公司已经形成ERP 软件、OA办公管理、等四大系列二十小类软件产品。致力于为政府、教育、医疗卫生、文化事业、公共事业(电、水、气等)、交通、住建、应急、金融、电信运营商、企业等用户提供专…

基于MFC框架用C++做一个记账本

目录 一、前言 二、主要功能和技术点 1.主要功能 2.主要技术点 三、准备工作 1.SQLite数据库操作工具 2.SqLiteCpp第三方库 3.安装office导入Excel需要的接口 3.1具体步骤 四、主界面 1.自定义窗口背景 1.1消息映射 1.2选择背景图片 1.3绘制背景 1.4静态控件透明…

qemu搭建aarch64

qemu工具搭建aarch64系统 下载准备 下载qemu: https://qemu.weilnetz.de/w64/2022/qemu-w64-setup-20220831.exe 下载固件:https://publishing-ie-linaro-org.s3.amazonaws.com/releases/components/kernel/uefi-linaro/16.02/release/qemu64/QEMU_EFI.fd?Signat…

Zookeeper3.6.3集群安装

Zookeeper3.6.3三节点集群安装 为保证集群高可用,Zookeeper 集群的节点数最好是奇数,最少有三个节点,所以这里搭建一个三个节点的集群。(在一个节点模拟三节点,真实的三节点把ip替换一下即可,按照hadoop案件把网络打通…

下一代 RAG 技术来了!微软正式开源 GraphRAG

省流总结 优点:检索准确度高 缺点:单个19w字构建用时4分30s、gpt4 token花费12美元 概述 7 月 2 日,微软开源了 GraphRAG,一种基于图的检索增强生成 (RAG) 方法,可以对私有或以前未见过的数据集进行问答。在 GitHub…

MySQL索引(四):字符串索引

前缀索引 MySQL是支持前缀索引的, 也就是说, 你可以定义字符串的一部分作为索引。 默认地,如果你创建索引的语句不指定前缀长度, 那么索引就会包含整个字符串。 使用前缀索引的优缺点: 1)优点&#xff1a…

获取剪切板的图片 -> File -> Base64 -> Blob -> url -> Image,以及它们之间的各种相互转换

🧑‍💻 写在开头 点赞 收藏 学会🤣🤣🤣 一、获取剪切板的图片(拿到 File 对象) js粘贴事件paste简单解析及遇到的坑 - 云社区 - 腾讯云 (tencent.com) document.addEventListener(paste, f…

实战八:模拟京东购物流程

问题描述: 从键盘录入5个商品信息(1001手机)添加到商品列表中,展示商品信息,提示用户选择商品,用户选中的商品添加到购物车中(购物车中的商品要逆序),用户选中的商品不存在需要有相应提示&#…

Selenium安装WebDriver最新Chrome驱动(含116/117/118/119)

目录 1、确认浏览器的版本 2、找到对应的chromedriver版本 3、解压chromedriver文件,放置chrome的安装目录下 4、设置系统属性 5、确认chromedriver是否安装成功及解决方式 1、确认浏览器的版本 在浏览器的地址栏,输入chrome://version/&#x…

攻防世界cat-题解

1.打开题目很想是一个命令执行,但是使用命令之心的语句,无法执行命令,看了wp,是在命令执行的时候;被编码了,我们把url%80使它溢出,把显示出来的代码下载到本地分析 分析代码我们可以知道这个是一…

SSM框架

目录 一. Maven入门和进阶 1.Maven简介和快速入门 (1) Maven介绍 (2) Maven的主要作用理解 ①场景概念 ②依赖管理 ③构建管理 (3)Maven安装和配置 ①软件安装 ②环境变量 ③命令测试 ④配置文件: ⑤idea配置本地maven 2.基于IDEA的Maven工程创建 (1…

AI 名人堂:李飞飞

Fei-Fei Li(李飞飞),斯坦福大学计算机科学系教授,斯坦福人工智能实验室前主任,以其在人工智能领域的开创性工作而闻名。 人工智能教育的倡导者 计算机视觉领域的领军人物 ImageNet的创造者 2AGI.NET AI 教程 2025最…

基于JavaScript实现的操作系统页面置换算法程序

基于JavaScript的操作系统页面置换算法程序 1. 实验目的 页面置换算法是虚拟存储管理实现的关键,通过本次实验理解内存页面调度的机制,在模拟实现FIFO、LRU等页面置换算法的基础上,比较它们的效率及优缺点,从而了解虚拟存储实现…

JAVA-初始JAVA模块化开发

菜鸟为了巩固所写 目录 菜鸟为了巩固所写 一、概述 二、创建步骤 1、打开Intellij IDEA,创建一个名为MyJavaModuleApp的Java项目。 2、向示例项目中添加”模块描述符“文件 3、创建多模块的IntelliJ 项目 4、IntelliJ项目添加“新模块”对话框 解释1:模块声…

Java 中tableaw 实战教程

java中tableaw库通过简单的API实现过滤、连接、绘制和操作表格数据。支持CSV,数据库,Excel等数据源。 安装依赖 tableaw是用于分析表格数据的开源Java库,构建在Java 8流之上。它可以从GitHub下载,也可以作为Maven或Gradle项目的…

力扣206. 反转链表题解

文章目录 题目描述:试析:1.迭代法2.递归法3.双指针法4.数组法 力扣206. 反转链表 题目描述: 给你单链表的头节点 head ,请你反转链表,并返回反转后的链表。 示例 1: 输入:head [1,2,3,4,5] …

Jdk21引入jsoup运行报错:java.lang.NoClassDefFoundError

文章目录 背景抽象类中代码问题分析尝试最终解决 背景 在富文本编译内容中,有些文件是存储到阿里云 oss 中的,所以链接做 STS 临时访问有时效性,每次返回的时候,需要通过STS来签名替换掉其中的链接访问,所以用到 jsoup…

Kafka 物理存储机制

优质博文:IT-BLOG-CN 一个商业化消息队列的性能好坏,其文件存储机制设计是衡量一个消息队列服务技术水平和最关键指标之一。下面将从Kafka文件存储机制和物理结构角度,分析Kafka是如何实现高效文件存储,及实际应用效果。Kafka的基…

【Linux】内核打印函数`printk`详解

在Linux内核开发过程中,printk是一个极其重要的函数,用于将信息输出到内核日志中。通过printk,开发者可以在内核中打印调试信息、错误信息以及其他类型的日志,这对于诊断问题、追踪执行流程以及监控系统状态都非常有帮助。本文将详…