数据库之索引＜保姆级文章＞

目录：

一. 什么是索引

二. 索引应该选择哪种数据结构

三. MySQL中的页

四. 索引分类及使用

一. 什么是索引：

1. MySQL的索引是⼀种数据结构，它可以帮助数据库高效地查询、更新数据表中的数据。
索引通过 ⼀定的规则排列数据表中的记录，使得对表的查询可以通过对索引的搜索来加快速度
2.MySQL 索引类似于书籍的目录，通过指向数据行的位置，可以快速定位和访问表中的数据，如汉语字典的目录（索引）页，我们可以按笔画、偏旁部首、拼音等排序的目录（索引）快速查找到需要的字。
 
3. 使⽤索引的⽬的只有⼀个，就是提升数据检索的效率，在应⽤程序的运⾏过程中，查 询操作的频率远远⾼于增删改的频率。

二. 索引应该选择哪种数据结构：

 下面让我们来逐个分析：

1.哈希：

如果我们使用第一种：哈希，哈希确实是一种很优秀的数据结构时间复杂度是 O(1) 查询速度非常快，但是但是MySQL并没有选择哈希，主要原因是哈希不支持持范围查找，哈希是通过哈希函数构建的，由数组+链表或红黑树组成，是通过哈希函数来定位，因此哈希不支持持范围查找。 

 

2.二叉搜索树：

如果我们使用二叉搜索树的中序遍历是⼀个有序数组

但有几个问题导致它不适合用作索引的数据结构：

2.1.最坏情况下时间复杂度为O(N)

2.2.相关搜索树AVL和红⿊树 节点个数过多无法保证树高：
包括AVL和红⿊树，虽然是平衡或者近似平衡，但是毕竟是⼆叉结构
在检索数据时，每次访问某个节点的⼦节点时都会发⽣⼀次磁盘IO，⽽在整个数据库系统中，IO是性能的瓶颈，减少IO次数可以有效的提升性能，所以树高导致磁盘IO次数多是个硬伤。所以MySQL并也没有选择搜索树
 

 
3.N叉树：
通过观察，相同数据量的情况下，N叉树的树⾼可以得到有效的控制，也就意味着在相同数据量的情况下可以减少IO的次数，从而提升效率。但是MySQL认为N叉树做为索引的数据结构还不够好
  
 

 
4.B+树：
B+树是⼀种经常用于 数据库和文件系统 等场合的平衡查找树， MySQL索引采用的数据结构
该数据结构解决了树高 导致磁盘IO次数多问题 ，解决了范围查询问题，由于 叶子节点保存着所有数据，性能也比较均衡。
5. B+树 特点 ：
5.1.能够保持数据稳定有序，插入与修改有较稳定的时间复杂度
5.2.非叶子节点仅具有索引作用，不存储数据，所有叶子节点保存着所有数据
5.3.所有叶子节点构成⼀个有序链表，可以按照主键值排序的次序依次遍历全部数据

6. B+树与B树的对比
6.1.叶子节点中的数据是连续的，且相互链接，便于区间查找和搜索。
6.2.⾮叶⼦节点的值都包含在叶⼦节点中
6.3.对于B+树⽽⾔，在相同树⾼的情况下，查找任⼀元素的时间复杂度都⼀样，性能均衡。

三. MySQL中的页（每一个节点就是一页）：

1.为什么要使用页：
在 .ibd ⽂件中最重要的结构体就是Page(页)，页是内存与磁盘交互的最⼩单元，默认⼤⼩为
16KB，每次内存与磁盘的交互⾄少读取一页，所以在磁盘中每个页内部的地址都是连续的，之所以这样做，是因为在使⽤数据的过程中，根据局部性原理，将来要使用的数据大概率与当前访问的数据在空间上是临近的 ，所以⼀次从磁盘中读取一页的数据放⼊内存中，当下次查询的数据还在这个页中时就可以从内存中直接读取，从而减少磁盘I/O提高性能。
 （解释：上面的.ibd ⽂件，是innodb储存引擎，生成的文件。）
注意：每⼀个页中即使没有数据也会使用 16KB 的存储空间，同时与索引的B+树中的节点对应，这里可以查看页大小：使用命令： show variables like ' innodb_page_size ';

2. 局部性原理：
是指程序在执⾏时呈现出局部性规律，在⼀段时间内，整个程序的执⾏仅限于程序中的某⼀部分。相应地，执⾏所访问的存储空间也局限于某个内存区域，局部性通常有两种形式：时间局部性和空间局部性。
时间局部性 （Temporal Locality）： 如果⼀个信息项正在被访问，那么在近期它很可能还会被再次访问。
空间局部性 （Spatial Locality）： 将来要⽤到的信息⼤概率与正在使⽤的信息在空间地址上是临近的。 
 

 
 
 
3.页文件头和页文件尾：
在MySQL中有多种不同类型的页，最常⽤的就是⽤来存储数据和索引的"索引⻚"，也叫做"数据⻚"，但不论哪种类型的⻚都会包含⻚头，和⻚尾页的主体信息使用数 据"⾏"进⾏填充，数据⻚的基本结构如下：
页文件头和页文件尾如图所示：
  
这里上一页页号和下一页页号，通过这两个属性可以把页与页之间链接起来，形成⼀个
双向链表。 
 

 
 
 
4.页主体： 
页主体部分是保存真实数据的主要区域，每当创建⼀个新页，都会⾃动分配两个行⼀个是页内最⼩行Infimun ，另⼀个是页内最⼤⾏ Supremun ，这两个行并不存储任何真实信息，⽽是做为数据⾏链表的头和尾，第⼀个数据⾏有⼀个记录下⼀⾏的地址偏移量的区域 next_record 将⻚内所有数据行组成了⼀个单向链表
当向一个新页插⼊数据时，将 Infimun 连接第⼀个数据行，最后⼀⾏真实数据行连接
Supremun ，这样数据行就构建成了⼀个单向链表，更多的行数据插⼊后，会按照主键从⼩到⼤的顺序进行链接
此时新 页 的结构如下所示：
  
5.页目录 ：
 
1.说明：⼀个⻚有16KB，通常会存在数百⾏数据，每次都要遍历数百⾏，⽆法满⾜⾼效查
询，为了提⾼查询效率，InnoDB采⽤⼆分查找来解决查询效率问题  
 2. 因此加入 页目录 这个结构：
将页内包括头行、尾⾏在内的所有⾏进⾏分组，约定头行单独为⼀组，其他每个组最多8条数据，同时把每个组最后⼀行在页中的地址，按主键从⼩到⼤的顺序记录在页⽬录中在，页⽬录中的每⼀个位置称为⼀个槽，每个槽都对应了⼀个分组，⼀旦分组中的数据行超过分组的上限8个时，就会分裂出⼀个新的分组；后续在查询某⾏时，就可以通过⼆分查找，先找到对应的槽，然后在槽内最多8个数据行中进行遍历即可，从⽽⼤幅提高了查询效率，这时⼀个页的核⼼结构就完成了
总结：分组时会在页目录中创建一个个的槽，最小行单独为一组，⼀旦分组中的数据行超过分组的上限8个时，就会分裂出⼀个新的分组，槽指向对应分组的最后一条记录，并且储存该组的主键值，方便来 ⼆分查找。

6. B+在MySQL索引中的应用 ：
注意：
(1).非叶子节点存的是索引页的信息
(2).索引页保存的是主键和子节点的引用信息。
(3).叶子节点保存的是真实数据的信息
(4).叶子节点形成一个双向链表
1.以查找id为5的记录，完整的检索过程如下：
步骤一：首先找到这条记录所对页
步骤二：再找到对应的槽
步骤三：根据槽的主键值，通过二分查找找到对应的记录。
具体如下：
首先判断B+树的根节点中的索引记录，此时 5 < 7 ，应访问左孩⼦节点，找到索引页2
然后在索引页2中判断主键id的大小，找到对应的槽的主键值与之不对
最后槽的主键值，通过二分查找找到对应的记录 找到与5相等的记录，命中，加载对应的数据页。
注意：这里每进行一次查找之前都要进行一次IO加载到内存，遍历几个节点IO几次。

2.三层B+树数据存放数（略）：

索引⻚⼀条数据的⼤⼩为，主键⽤BIGINT类型占8Byte，下⼀⻚地址6Byte，⼀共14Byte，⼀个 索引页可以保存 16*1024/14 = 1170 条索引记录

综合只保存索引的根节点和⼆级节点的索引⻚以及保存真实数据的数据页，那么⼀共可以保存 1170*1170*16 = 21,902,400 条记录，也就是说在两千多万条数据的表中，可以通过三次IO就完成数据的检索

四. 索引分类及使用:

注意：创建多少索引就会生成多少索引树
1.主键索引:
当在⼀个表上定义⼀个主键 PRIMARY KEY 时，InnoDB使⽤它作为聚集索引 
代码：创建主键两种方式：
方式三：修改表中的列为主键索引：（修改表中的id列为主键索引）
语法：添加：ALTER TABLE + 表名 add PRIMARY KEY （...）
修改：ALTER TABLE + 表名 modify ...

 

2. 唯⼀索引：
当在⼀个表上定义⼀个唯⼀键 UNQUE 时，自动创建唯⼀索引
与普通索引类似，但区别在于唯⼀索引的列不允许有重复值
下图是创建索引的三种方式：
3.普通索引：
最基本的索引类型，没有唯⼀性的限制
可能为多列创建组合索引，称为复合索引或组和索引
 
方式一：创建表的时候创建普通索引 
-- 创建表的时候创建普通索引
CREATE TABLE t_index1 (id bigint PRIMARY KEY auto_increment,name varchar(20) UNIQUE,sno varchar(20),index(sno)
)

方式二：修改表中的列为普通索引

修改表中的列为普通索引
CREATE TABLE t_index2 (id BIGINT PRIMARY KEY auto_increment,name VARCHAR(20),sno VARCHAR(20));ALTER TABLE t_index2 ADD INDEX (sno);

方式三：单独创建索引并指定索引名

 -- 单独创建索引并指定索引名 
CREATE TABLE t_index3 (id bigint PRIMARY KEY auto_increment,name varchar(20),sno varchar(20)
);-- 索引名推荐使用 idx_表名_列名[_列名]
CREATE INDEX idx_t_index3 on t_index3(sno);

 

创建普通索引三种方式：

-- 创建复合索引：-- 创建表时指定索引列
create table t_index_4 (id bigint PRIMARY key auto_increment,name varchar(20),sno varchar(20),class_id bigint,INDEX(sno,name)
)-- 单独创建复合索引并指定索引名
create table t_index_6 (id bigint PRIMARY key auto_increment,name varchar(20),sno varchar(20),class_id bigint
);CREATE INDEX idx__t_index_6_sno_name ON t_index_6 (sno,name);

 

4.全⽂索引：
4.1。基于⽂本列(CHAR、VARCHAR或TEXT列)上创建，以加快对这些列中包含的数据查询和4.2.DML操作
4.3.用于全文搜索，仅MyISAM和InnoDB引擎支持 
 
 
5.聚集索引：
与主键索引是同义词 如果没有为表定义 PRIMARY KEY, InnoDB使⽤第⼀个 UNIQUE 和 NOT NULL 的列作为聚集索引
注意：
如果表中没有 PRIMARY KEY 或合适的 UNIQUE 索引，InnoDB会为新插⼊的行生成⼀个⾏号并用6字节的 ROW_ID 字段记录， ROW_ID 单调递增，并使⽤ ROW_ID 做为索引 
 
6 非聚集索引：
6.1.聚集索引以外的索引称为非聚集索引或⼆级索引
6.2.⼆级索引中的每条记录都包含该⾏的主键列，以及⼆级索引指定的列。
6.3.InnoDB使⽤这个主键值来搜索聚集索引中的⾏，这个过程称为回表查询 
 
7.非聚集索引的查询->回表查询解释 ：
我们知道创建多少索引就会生成多少索引树.
我的理解是，通过索引查询到叶子节点的索引记录，根据这个索引记录去整棵包含全部数据的索引树中查找数据的过程，因为总共查询了两张表索引叫回表查询。
例子： 
-- 回表查询
select * from student where student_id = 1 and name = '韩立';

8.索引覆盖：
通过索引查询的列 不需要 根据索引记录 去整棵 包含全部数据的 索引树中查找 数据
例子： 
select sn from student where name = '厉飞羽';

 

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

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

相关文章

F28335 时钟及控制系统

F28335 时钟及控制系统

1 F28335 系统时钟来源 1.1 振荡器OSC与锁相环PLL 时钟信号对于DSP来说是非常重要的，它为DSP工作提供一个稳定的机器周期从而使系统能够正常运行。时钟系统犹如人的心脏，一旦有问题整个系统就崩溃。DSP 属于数字信号处理器， 它正常工作也必须为其提供时钟信号。那么这个时钟…
阅读更多...
【例题】lanqiao3225 宝藏排序Ⅰ

【例题】lanqiao3225 宝藏排序Ⅰ

这里的n的范围可以使用冒泡排序、选择排序和插入排序等算法。 冒泡排序 nint(input()) alist(map(int,input().split()))def pop_sort(a):for i in range(n):for j in range(n-i-1):if a[j]>a[j1]:a[j],a[j1]a[j1],a[j] pop_sort(a) print( .join(map(str,a)))选择排序 n…
阅读更多...
数据结构(7.3_2)——平衡二叉树

数据结构(7.3_2)——平衡二叉树

平衡二叉树&#xff0c;简称平衡树(AVL树)----树上任一结点的左子树和右子树的高度之差不超过1. 结点的平衡因子左子树高-右子树高 //平衡二叉树结点 typedef struct AVLNode {int key;//数据域int blalance;//平衡因子struct AVLNode* lchild, * rchild; }AVLNode,*AVLTree; …
阅读更多...
4. Python之运算符

4. Python之运算符

一. Python运算符 常用的运算符有&#xff1a;算述运算符&#xff0c;赋值运算符&#xff0c;比较运算述&#xff0c;逻辑运算符&#xff0c;位运算符等等。 1. 算述运算符 用于处理四则运算的符号&#xff0c;主要有&#xff1a; 运算符描述加法-减法*乘法/除法//整除%取余…
阅读更多...
Nature Climate Change | 全球土壤微生物群落调控微生物呼吸对变暖的敏感性(Q10)

Nature Climate Change | 全球土壤微生物群落调控微生物呼吸对变暖的敏感性(Q10)

本文首发于“生态学者”微信公众号&#xff01; 全球变暖将加速有机物分解&#xff0c;从而增加土壤中二氧化碳的释放&#xff0c;触发正的碳-气候反馈。这种反馈的大小在很大程度上取决于有机质分解的温度敏感性(Q10)。Q10仍然是围绕土壤碳排放到大气的预测的主要不确定性来源…
阅读更多...
FreeRTOS实战指南 — 3.2 FreeRTOS中链表的实现

FreeRTOS实战指南 — 3.2 FreeRTOS中链表的实现

目录 1 FreeRTOS中链表的实现 1.1 实现链表节点 1.2 实现链表根节点 1.3 将节点插入到链表的尾部 1.4 将节点按照升序排列插入到链表 1.5 将节点从链表删除 1.6 节点带参宏小函数 2 链表操作实验 1 FreeRTOS中链表的实现 1.1 实现链表节点 在FreeRTOS操作系统中&…
阅读更多...
第二界陇剑杯赛-MISC

第二界陇剑杯赛-MISC

1 题目名称&#xff1a;hard_web-1 题目内容&#xff1a;1.服务器开放了哪些端口&#xff0c;请按照端口大小顺序提交答案&#xff0c;并以英文逗号隔开(如服务器开放了80 81 82 83端口&#xff0c;则答案为80,81,82,83) 题目分值&#xff1a;100.0 题目难度&#xff1a;容易 …
阅读更多...
go语言中的数组指针和指针数组的区别详解

go语言中的数组指针和指针数组的区别详解

1.介绍 大家知道C语言之所以强大&#xff0c;就是因为c语言支持指针&#xff0c;而且权限特别大&#xff0c;c语言可以对计算机中任何内存的指针进行操作&#xff0c;这样自然而然也会带来一些不安全的因素&#xff0c;所以在golang中&#xff0c;「取消了对指针的一些偏移&…
阅读更多...
自动排课管理系统(源代码+论文+开题报告)

自动排课管理系统(源代码+论文+开题报告)

一、题目摘要 题目简要说明&#xff1a; 选排课系统功能的设计上&#xff0c;选排课系统可以分为登录、排课和选课3个子系统。登录子系统区分排课者(也即系统的管理者)、教师和学生这三者的不同身份&#xff0c;给出不同的权限&#xff0c;在页面中根据身份判断其相应具有的功…
阅读更多...
战斗机检测系统源码分享

战斗机检测系统源码分享

战斗机检测检测系统源码分享 [一条龙教学YOLOV8标注好的数据集一键训练_70全套改进创新点发刊_Web前端展示] 1.研究背景与意义 项目参考AAAI Association for the Advancement of Artificial Intelligence 项目来源AACV Association for the Advancement of Computer Visio…
阅读更多...
【K230 实战项目】气象时钟

【K230 实战项目】气象时钟

【CanMV K230 AI视觉】 气象时钟 功能描述&#xff1a;说明HMDI资源3.5寸屏幕 使用方法 为了方便小伙伴们理解&#xff0c;请查看视频 B站连接 功能描述&#xff1a; 天气信息获取&#xff1a;通过连接到互联网&#xff0c;实时获取天气数据&#xff0c;包括温度、湿度、天气状…
阅读更多...
您的计算机已被.lcrypt勒索病毒感染？恢复您的数据的方法在这里！

您的计算机已被.lcrypt勒索病毒感染？恢复您的数据的方法在这里！

导言 在网络安全领域&#xff0c;勒索病毒已经成为一种威胁极大的恶意软件&#xff0c;其中.lcrypt勒索病毒&#xff08;.lcrypt ransomware&#xff09;是最近出现的一种新的变种。它以加密用户数据并要求赎金为手段&#xff0c;严重影响个人和组织的日常运营。本文91数据恢复…
阅读更多...
力扣题解1184

力扣题解1184

大家好&#xff0c;欢迎来到无限大的频道。 今日继续给大家带来力扣题解。 题目描述&#xff08;简单&#xff09;&#xff1a; 公交站间的距离 环形公交路线上有 n 个站&#xff0c;按次序从 0 到 n - 1 进行编号。我们已知每一对相邻公交站之间的距离&#xff0c;distanc…
阅读更多...
【Motion Forecasting】【摘要阅读】BANet: Motion Forecasting with Boundary Aware Network

【Motion Forecasting】【摘要阅读】BANet: Motion Forecasting with Boundary Aware Network

BANet: Motion Forecasting with Boundary Aware Network 这项工作发布于2022年&#xff0c;作者团队来自于OPPO。这项工作一直被放在arxiv上&#xff0c;并没有被正式发表&#xff0c;所提出的方法BANet在2022年达到了Argoverse 2 test dataset上的SOTA水准。 Method BANet…
阅读更多...
计算机三级网络技术总结（一）

计算机三级网络技术总结（一）

RPR环中每一个节点都执行SRP公平算法IEEE 802.11a和g将传输速率提高到54Mbps一个BGP发言人与其他自治系统中的BGP发言人要交换路由信息就要先建立TCP连接在一个区域内的路由器数一般不超过200个进入接口配置模式&#xff1a;Router(config)#interface <接口名> 封装ppp协…
阅读更多...
QT 事件 Event 应用

QT 事件 Event 应用

文章目录 一、事件处理过程1. QT 事件应用介绍2. 事件分发过程 二、重写事件案例1. 鼠标事件2. 自定义按钮事件 一、事件处理过程 1. QT 事件应用介绍 众所周知Qt是一个基于C的框架&#xff0c;主要用来开发带窗口的应用程序&#xff08;不带窗口的也行&#xff0c;但不是主流…
阅读更多...
数据结构和算法之线性结构

数据结构和算法之线性结构

原文出处:数据结构和算法之线性结构 关注码农爱刷题&#xff0c;看更多技术文章&#xff01;&#xff01;&#xff01; 线性结构是一种逻辑结构&#xff0c;是我们编程开发工作应用最广泛的数据结构之一。线性结构是包含n个相同性质数据元素的有限序列。它的基本特征是&…
阅读更多...
QT--connect的使用

QT--connect的使用

在qt里面我们可以用connect将信号与槽函数连接器起来&#xff0c;而connect是一个常用的函数&#xff0c;用法也非常简单。 来看一个非常简单的栗子 Widget::Widget(QWidget *parent): QWidget(parent), ui(new Ui::Widget) {ui->setupUi(this);qpbnew QPushButton(this)…
阅读更多...
速通汇编（五）认识段地址与偏移地址，CS、IP寄存器和jmp指令，DS寄存器

速通汇编（五）认识段地址与偏移地址，CS、IP寄存器和jmp指令，DS寄存器

一&#xff0c;地址的概念 通常所说的地址指的是某内存单元在整个机器内存中的物理地址&#xff0c;把整个机器内存比作一个酒店&#xff0c;内存单元就是这个酒店的各个房间&#xff0c;给这些房间编的门牌号&#xff0c;类比回来就是内存单元的物理地址 在第一篇介绍debug的…
阅读更多...
242. 有效的字母异位词（排序后用Map或者滑动窗口用Map）

242. 有效的字母异位词（排序后用Map或者滑动窗口用Map）

文章目录 242. 有效的字母异位词49. 字母异位词分组438. 找到字符串中所有字母异位词 242. 有效的字母异位词 242. 有效的字母异位词 给定两个字符串 s 和t&#xff0c;编写一个函数来判断t是否是s的 字母异位词(字母异位词是通过重新排列不同单词或短语的字母而形成的单词或…
阅读更多...
最新文章

Copyright @ 2022~2023