MySQL--索引结构

索引-索引结构

    • 1. 概述
    • 2. 二叉树
    • 3. B-Tree
    • 4. B+Tree
    • 5. Hash

1. 概述

MySQL的索引是在存储引擎层实现的,不同的存储引擎有不同的索引结构,主要包含以下几种:
在这里插入图片描述
上述是MySQL中所支持的所有的索引结构,下面展示不同的存储引擎对于索引结构的支持情况。
在这里插入图片描述

注意: 我们平常所说的索引,如果没有特别指明,都是指B+树结构组织的索引。

2. 二叉树

假如说MySQL的索引结构采用二叉树的数据结构,比较理想的结构如下:
在这里插入图片描述
但是如果我们插入的数据是顺序插入的,就会形成一个单向链表,结构如下:
在这里插入图片描述
所以,如果选择二叉树作为索引结构,会存在以下缺点:

  • 顺序插入时,会形成一个链表,查询性能大大降低。
  • 大数据量情况下,层级较深,检索速度慢。

此时大家可能会想到,我们可以选择红黑树,红黑树是一颗自平衡二叉树,那这样即使是顺序插入数
据,最终形成的数据结构也是一颗平衡的二叉树,结构如下:
在这里插入图片描述
但是,即使如此,由于红黑树也是一颗二叉树,所以也会存在一个缺点:

  • 大数据量情况下,层级较深,检索速度慢。、

所以,在MySQL的索引结构中,并没有选择二叉树或者红黑树,而选择的是B+Tree,那么什么是B+Tree呢?在详解B+Tree之前,先来介绍一个B-Tree。

3. B-Tree

B-Tree,B树是一种多叉路平衡查找树,相对于二叉树,B树每个节点可以有多个分支,即多叉。以一颗最大度数(max-degree)为5(5阶)的b-tree为例,那这个B树每个节点最多存储4个key,5个指针:
在这里插入图片描述

树的度数指的是一个节点的子节点个数。

特点:
5阶的B树,每一个节点最多存储4个key,对应5个指针。
一旦节点存储的key数量到达5,就会裂变,中间元素向上分裂。
在B树中,非叶子节点和叶子节点都会存放数据。

4. B+Tree

B+Tree是B-Tree的变种,我们以一颗最大度数(max-degree)为4(4阶)的b+tree为例,来看一下其结构示意图:
在这里插入图片描述
我们可以看到两部分:
绿色框框起来的部分,是索引部分,仅仅起到索引数据的作用,不存储数据。
红色框框起来的部分,是数据存储部分,在其叶子节点中要存储具体的数据。

B+Tree 与 B-Tree相比,主要有以下三点区别:
所有的数据都会出现在叶子节点。
叶子节点形成一个单向链表。
非叶子节点仅仅起到索引数据作用,具体的数据都是在叶子节点存放的。

上述我们所看到的结构是标准的B+Tree的数据结构,接下来,我们再来看看MySQL中优化之后的B+Tree。

MySQL索引数据结构对经典的B+Tree进行了优化。在原B+Tree的基础上,增加一个指向相邻叶子节点的链表指针,就形成了带有顺序指针的B+Tree,提高区间访问的性能,利于排序。

在这里插入图片描述

5. Hash

MySQL中除了支持B+Tree索引,还支持一种索引类型—Hash索引。

1). 结构
哈希索引就是采用一定的hash算法,将键值换算成新的hash值,映射到对应的槽位上,然后存储在hash表中。

在这里插入图片描述
如果两个(或多个)键值,映射到一个相同的槽位上,他们就产生了hash冲突(也称为hash碰撞),可以通过链表来解决。

在这里插入图片描述

2). 特点
A. Hash索引只能用于对等比较(=,in),不支持范围查询(between,>,< ,…)
B. 无法利用索引完成排序操作
C. 查询效率高,通常(不存在hash冲突的情况)只需要一次检索就可以了,效率通常要高于B+tree索引

3). 存储引擎支持
在MySQL中,支持hash索引的是Memory存储引擎。 而InnoDB中具有自适应hash功能,hash索引是InnoDB存储引擎根据B+Tree索引在指定条件下自动构建的。

思考题: 为什么InnoDB存储引擎选择使用B+tree索引结构?

  1. 相对于二叉树,层级更少,搜索效率高;
  2. 对于B-tree,无论是叶子节点还是非叶子节点,都会保存数据,这样导致一页中存储的键值减少,指针跟着减少,要同样保存大量数据,只能增加树的高度,导致性能降低;
  3. 相对Hash索引,B+tree支持范围匹配及排序操作;

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

力扣382.链表随机节点

Problem: 382. 链表随机节点 文章目录 题目描述思路复杂度Code 题目描述 思路 由水塘抽样易得&#xff0c;当遇到i个元素&#xff0c;有 1 / i 1/i 1/i的概率选择该元素&#xff1b;则在实际操作中我们定义一个下标i从1开始遍历每次判断rand() % i 0&#xff08;该操作就是判断…

Chrome插件(二)—Hello World!

本小节将指导你从头到尾创建一个基本的Chrome插件&#xff0c;你可以认为是chrome插件开发的“hello world”&#xff01; 以下详细描述了各个步骤&#xff1a; 第一步&#xff1a;设置开发环境 确保你拥有以下工具&#xff1a; 文本编辑器&#xff1a;如Visual Studio Cod…

2278. 企鹅游行(最大流,拆点)

活动 - AcWing 在南极附近的某个地方&#xff0c;一些企鹅正站在一些浮冰上。 作为群居动物&#xff0c;企鹅们喜欢聚在一起&#xff0c;因此&#xff0c;它们想在同一块浮冰上会合。 企鹅们不想淋湿自己&#xff0c;所以它们只能利用自己有限的跳跃能力&#xff0c;在一块块…

容器_Docker ( 06 )

容器_Docker ( 05 ) Kubernetes 资源对象管理 资源对象文件 模板与帮助信息 资源对象文件优势 命令无法实现高级复杂的功能某些资源对象使用命令无法创建方便管理 , 保存 , 追溯历史 资源对象文件太长 , 记不住怎么办 使用命令创建模板查询帮助信息查询官方手册 生成资源…

区块链游戏解说:什么是 Ultimate Champions

作者&#xff1a;lesleyfootprint.network 编译&#xff1a;cicifootprint.network 数据源&#xff1a;Ultimate Champions Dashboard 什么是 Ultimate Champions Ultimate Champions 是一款免费的奇幻足球和篮球游戏&#xff0c;拥有官方授权的数字卡牌作为区块链上的 NFT…

go interface{} 和string的转换问题

1.遇到的问题 问题来源于,我sql模版拼接遇到的问题。 首先&#xff0c;这样是没有问题的。 var qhx interface{} "qhx"s : qhx.(string)fmt.Println(s) 但是当我在这段代码里用:1.类型断言 var sqlStr "select * from tx_user where username %s" join…

SpringBoot -【SmartInitializingSingleton】基础使用及应用场景

SmartInitializingSingleton 在继续深入探讨 SmartInitializingSingleton接口之前&#xff0c;让我们先了解一下 Spring Framework 的基本概念和背景。Spring Framework 是一个开源的 JavaEE&#xff08;Java Enterprise Edition&#xff09;全栈&#xff08;full-stack&#x…

C++面试题精选与解析

C面试题精选与解析 一、基础与语法 请问C中的指针和引用有什么区别&#xff1f; 指针是一个变量&#xff0c;存储的是另一个变量的内存地址。指针可以被重新赋值以指向另一个不同的对象。而引用是某个变量的别名&#xff0c;一旦引用被初始化为一个变量&#xff0c;就不能改变…

高级统计方法 第4次作业

作业评阅&#xff1a; 概念 2.问题 KNN分类和KNN回归都是KNN算法在不同类型数据上的应用&#xff0c;但它们之间存在明显的区别。 解决的问题类型不同&#xff1a;KNN分类适用于解决分类问题&#xff0c;而KNN回归则适用于解决回归问题。当响应变量是连续的&#xff0c;根据…

windows安装 RabbitMQ

首先打开 RabbitMQ 官网&#xff0c;点击 Get Started(开始) 点击 Download Installation(下载安装)。 这里提供了两种方式进行安装&#xff0c;我们使用第二种方法。 使用 chocolatey以管理用户身份使用官方安装程序 往下滑&#xff0c;第二种方法需要 Erlang 的依赖&#x…

UE蓝图 函数调用(CallFunction)节点和源码

系列文章目录 UE蓝图 Get节点和源码 UE蓝图 Set节点和源码 UE蓝图 Cast节点和源码 UE蓝图 分支(Branch)节点和源码 UE蓝图 入口(FunctionEntry)节点和源码 UE蓝图 返回结果(FunctionResult)节点和源码 UE蓝图 函数调用(CallFunction)节点和源码 文章目录 系列文章目录一、Call…

【Vuforia+Unity】AR06-空间环境识别功能(AreaTargets)

Vuforia原理:把被识别的物体转成图、立体图、柱形图,3D模型、环境模型,然后模型生成Vuforia数据库-导入Unity-参考模型位置开始摆放数字内容,然后参考模型自动隐藏-发布APP-识别生活中实物-数字内容叠加上去! 不论你是否曾有过相关经验,只要跟随本文的步骤,你就可以成功…

uni-app vue3 setup nvue中webview层级覆盖问题

核心就是这两行&#xff0c;&#x1f923;发现设置后不能点击了&#xff0c;这个玩意可能只能弹窗打开的时候动态的修改 position: static, zindex: 0onLoad(options > {loadWebview()})function loadWebview() {let pageInfo uni.getSystemInfoSync();width.value pageI…

强大到怀疑人生!AI视频生成必备的工具推荐!

刚发现的超牛逼AI视频生成&#xff1a;小说文案智能分镜智能识别角色和场景批量Ai绘图自动配音添加音乐一键合成视频——播放量随便破百万。地址&#xff1a;跳转提示 - 3MW短网址https://3mw.cn/3ed5 这个Ai漫画推文软件的优势&#xff1a; 1、无需本地部署&#xff0c;对电脑…

Visual Studio:Entity设置表之间的关联关系

1、选择表并右键-》新增-》关联 2、设置关联的表及关联关系并“确定”即可

机器学习模型的过拟合与欠拟合

机器学习模型的训练过程中&#xff0c;可能会出现3种情况&#xff1a;模型欠拟合、模型正常拟合与模型过拟合。其中模型欠拟合与模型过拟合都是不好的情况。下面将会从不同的角度介绍如何判断模型属于哪种拟合情况。 &#xff08;1&#xff09;欠拟合与过拟合表现方式 欠拟合…

phtread_cancel函数用于取消线程,但不是实时的

如上图所示&#xff0c;线程函数中没有取消点&#xff08;一般是一些系统调用----man 7 pthreads查看&#xff0c;自定义函数是无效的&#xff09;&#xff0c;则使用pthread_cancle函数不生效。 解决方法&#xff1a;可以添加pthread_testcancle(); 通过pthread_join回收的…

广联达Linkworks GetAllData 信息泄露漏洞

免责声明&#xff1a;文章来源互联网收集整理&#xff0c;请勿利用文章内的相关技术从事非法测试&#xff0c;由于传播、利用此文所提供的信息或者工具而造成的任何直接或者间接的后果及损失&#xff0c;均由使用者本人负责&#xff0c;所产生的一切不良后果与文章作者无关。该…

MATLAB练习题:计算中国式排名

​讲解视频&#xff1a;可以在bilibili搜索《MATLAB教程新手入门篇——数学建模清风主讲》。​ MATLAB教程新手入门篇&#xff08;数学建模清风主讲&#xff0c;适合零基础同学观看&#xff09;_哔哩哔哩_bilibili 下表给出了两种不同的排名结果&#xff0c;成绩越高排名越靠前…

基于Springboot的校园求职招聘系统(有报告)。Javaee项目,springboot项目。

演示视频&#xff1a; 基于Springboot的校园求职招聘系统&#xff08;有报告&#xff09;。Javaee项目&#xff0c;springboot项目。 项目介绍&#xff1a; 采用M&#xff08;model&#xff09;V&#xff08;view&#xff09;C&#xff08;controller&#xff09;三层体系结构…