文章目录

• 索引
• MySQL
• 认识磁盘
• MySQL与磁盘交互的基本单位
• 建立共识
• 索引的理解
• • 单个page
• 多页情况
• 什么是主键索引
• • 为什么只能是B树
• 聚簇索引vs非聚簇索引
• • 非聚簇索引
  • 聚簇索引

索引

索引提高数据库的性能提高数据库的检索速度不用加内存不用改sql不用改程序速度可以提高成败上千倍但是插入更新删除的速度就比较慢

常见的索引

• 主键索引primarykey
• 唯一键索引unique
• 普通索引index

MySQL

MySQL的工作过程

• mysql对数据做的CURD的操作根据冯诺依曼体系mysql是不可能直接去访问磁盘的
• 实际上数据库对数据做的所有访问全部都是在内存中进行的
• 如果数据有变化再定期的把数据刷新到磁盘里面
• sync使用使用这个系统调用把内核数据刷新到磁盘里面不经过OS

• 示例添加索引前

我们插入了大量的数据然后从里面进行查找数据这样我们就会发现了查询的结果会查很久

• 查询员工号2998877
  
  

我们发现很慢时间过了很久才能查询出来

• 示例添加索引后

altertableEMPaddindex(empno);

我们在添加索引之后发现查找的非常块几乎每花什么时间

select*fromEMPwhereempno998877;

我们会发现搜索的时间不到一秒

认识磁盘

数据存储效率很低路上还要有带宽限制因为我们在传输数据的时候不仅要在自己的磁盘中传送还要在网络中进行跨网络传输

所有的数据都是基于LInux文件系统的

要找到一个文件的全部本质上就是在磁盘中找到所有保存文件的扇区

磁盘里面磁头确认的是哪一个面磁盘确认的是哪个圈扇区来进行确认是哪一块区域来定位到某一个扇区CHS定位方案磁盘使用的方案
磁盘的使用使用的LBA逻辑块地址可以理解为虚拟地址和物理地址这个是操作系统使用的方案

• 结论
  我们已经能够在硬件层面上定位到对应的地址了任何一个数据块扇区在系统软件上直接按照扇区512字节会造成过度寻址所以我们基本都是使用4096来进行寻址4页

• 如果OS直接用硬件提供的数据大小进行交互那么系统软件

磁盘的交互都是使用4KB进行交互
连续磁盘访问

MySQL与磁盘交互的基本单位

MySQL作为一款软件可以想象成一个特殊的文件系统它有更高的IO场景为了提高效率

• MySQL数据交互的基本单位16KB

也就是说磁盘这个硬件的基本单位是512字节而MySQL使用16kb进行IO交互即
MySQL和磁盘进行数据交互通过OS的基本单位是16KB这个基本数据单位在mysql里面叫做page

如果它的基本单位和磁盘一样的话万一磁盘的基本单位变了它也要跟着变兼容性不行

所以这里规定MySQL数据交互的基本单位是16KB1page

建立共识

• MySQL中数据文件一定是在磁盘当中的以page为基本单位
• MySQL的CURD操作都需要计算找到对应的插入位置或者找到对应要修改或者查询的数据
• 只要涉及计算就要有CPU参与为了cpu参与一定把数据加载到内存cpu只和内存打交道根据需要把数据从外设掉到内存中不是所有数据都加载进去
• 所以在特定时间内数据一定是在磁盘中有内存中也有后序操作完内存数据之后以特定的刷新策略刷新到磁盘里面这个时候就涉及磁盘和内存数据的交互此时基本单位就是page即便只改一个字节也要以16kb的大小来进行交互
• 为何更高的效率一定要减少系统和内存之间的IO请求次数

IO请求----系统中一定存在大量的IO请求————操作系统一定也要管理这些IO请求
先描述再组织

structrequest_io{char*start,*end;pid_tid;}

磁盘中,磁盘中一定是要对这些io请求进行管理的

structdisk{structrequestt_io*queue;//访问对应的磁盘都有对应的对应进行保存起来};

索引的理解

创建表

createtableuser(-idintprimarykey,--再id这个地方添加主键建立了一个主键索引-ageintnotnull,-namevarchar(16)notnull-);

我们这里是故意乱序的进行数据的插入

我们select之后发现查询的结果是按照主键顺序进行排序的

我们中断一下排序的工作是由谁操作的为什么要这样干呢?
为何IO交互要使用page?

每次交互都使用page16KB这样一次可以预加载很多可以充分利用局部性原理。1

单个page

为何MySQL和磁盘进行IO交互的时候要采用page的方案进行交互用多少加载多少的方式不香吗

• 如上面的5条数据MySQL要查id2第一次加载id1第二次加载id2一次一条数据就要进行2次IO如果要找id5就需要5次IO

• 但是如果5条数据都被保存再page里面16kb能保存很多记录第一次IO查找的时候整个page就直接加载MySQL的bufferpool里面了这里完成了一次IO但是往后的id1345等就不需要进行IO了而是直接再内存里面进行了大大减小了IO的次数

• 你怎么保证用户下次找的数据就再这个page里面我们不能保证但是会由很大的概率因为由局部性原理往往IO效率低下唉最主要矛盾不是单次IO的数据量大小而是IO的次数

正式理解索引结构,一定会存在page结构体

1. mysql会预先开辟一段空间来保留这些page
2. MySQL在任何一个时刻一定会存在大量的page页存在MySQL内部
3. MySQL本身也要对page进行管理也是要先描述再组织

structpage{structpage*prev;//指向前一个pagestructpage*next;//指向后一个pagecharbuff(16kb-其他字段占用的大小);}

对page的管理就是对链表的管理

之后的操作都是再内存当中实现的
mysql插入数据时按照主键来进行排序插入后page里面就是有序的,查找的时候就能优化查找算法有序的就可以提高查找效率如二分查找方便我们进行查找

理解多个page

• 在page之间和page里面查找数据都是基于链表的线性遍历一个遍历一遍没找到下一个继续遍历效率非常的低还是ON的方式进行遍历

页内目录

用目录查找效率就很高第一章是什么在第几页这样查找就很快以空间换时间
先在一个page里面提高搜索效率那么在所有page里面效率也提高了很多
有了目录就能一次淘汰很多数据这样就会导致单页中数据减少我们是先遍历数据目录再去便利数据记录这样提高的效率就很大我们先遍历目录

假如说数据500条我们目录10条这样就是只要遍历10次目录遍历50次目录中对应的数据大大减少了遍历的次数

• 所以有主键的时候默认的进行排序可以方便我们引入页内目录方便查询

page之间也是线性的怎么提高page之间的搜索效率

1. page内部的效率问题

2. page和page之间的效率问题

多页情况

数据不断的插入新增mysql很容易容量不足所以就需要开辟一个新的page来保存数据然后通过指针的方式来将所有的page组织起来
问题

• 因为我们要保证一个整体有序所以新来的数据不会放在新的page里面

• 这样我们就可以通过多个page的遍历page内部用目录进行定位数据可是这样也有效率问题在page里面我们也需要用mysql进行遍历这样就显得我们之前的page有点没用了,我们查找一个数据需要把前面的所有page遍历一遍

解决方案

给我们的一个一个page也带上目录

把每个page里面最小的记录作为每个page的键值这样page和page之间键值就不会重复了
在page里面中在开一个page里面就只保存下面所管理的主键和指针只保存一个一个目录
用一个page专门来保存page目录和page对应的地址一个page可以管理2000多个page
直接到顶层的page目录

数据量很大的话还要继续在中间增加page目录
相当于一个b树一个节点可以索引到很多地址至此我们就已经可以给我们的表user构建完主键索引了
随便找一个id我们发现现在查找的page树一定减少了说明我们IO次数也减少了那么效率也高了

在page之间和page内部都添加目录结构这样就能构建一个b树

什么是主键索引

1. 所有的数据最终都可以在磁盘中也可以在mysql的bufferpool内存中
2. 我们所有的数据都必须要以page为单位进行IO以page为单位组织

在MySQL内部将热点数据以B树的形式将所有的page页进行组织形成的数据结构与其配套的查找算法叫做索引

添加索引就给业内加目录给顶层添加目录结构方便对数据进行筛查
如果没有添加索引所有的数据都是以链表的形式串联起来数据没有做优化没有排序插入什么样就是什么样的

有了b树每次从叶子节点中进行搜索一路找下去就可以查找到对应的数据了
现在我们就不用加载很多数据到内存中不需要查找的page就不需要加载到内存中了我们需要哪个page加载哪个page即可一路把我们查询过程中的路径page加载进去即可

只要我们把页目录加载进去之后这些目录就常驻了以后就不需要再加载到内存了减少了IO的次数

但是其实目录页本来就没多少所以可以直接都加载进来

但是如果插入数据删除数据的时候会影响一下效率因为会影响整个页目录的结构
修改了一个数据都要以整个page进行刷新到磁盘中

为什么只能是B树

• 链表线性遍历效率太低
• 二叉树可能会退化成线性结构
• AVL/RBtree二叉树相较于多阶B树意味着整体的树比较高需要系统与磁盘进行的IOpage更多而B矮胖的层级低数据量大访问次数少
• Hash有的索引就是基于Hash但是Innodbhash有的时候也能O1但是最大的问题不能够支持区间性的范围查找比如我们要查找4060但是hash是乱序的无法实现区域性哈希但是b树只需要知道自己找40到40里面查找即可
• B树B树下面的叶子节点都被链表连起来这样page之间都能够查找跨范围而且非叶子节点也会携带数据增加的空间大小逻辑上没有解耦

B树

• 只有叶子节点有数据
• 叶子节点相连非常便于进行范围查找
• IO次数较少

创建了一个索引它就会创建一个文件叫.ibdindex_block_data,这个说明数据和索引合在一起的
把索引和数据都加载进去了

B树在哪里

• 在磁盘上有完整的B和数据
• 在内存中有局部高频被访问的B核心Page
• mysql查找一定会伴生着mysql进行根据B进行page的换入换出

同样文件也是内存中一定是被打开的文件

聚簇索引vs非聚簇索引

非聚簇索引

数据和索引分离

myisam的叶子节点不存储数据只存储数据对应的地址这样就能保存更多键值和索引关系把数据放到对应的一个地方用指针进行索引

把索引page和数据page进行分离也就是叶子节点没有数据只有对应数据的地址

聚簇索引

innodb就是聚簇索引
把数据和索引聚合在一起

辅助索引

MySQL除了会建立主键索引之外还会建立按照其他列信息建立索引一般这叫做辅助索引其他字段也能建立索引
和主键索引没有差别无非是主键不能重复而非主键可以重复

主键就是叶子有地址有索引
同样是构建b树innodb非主键索引中叶子节点保存对应地址的索引但是没有保存数据太浪费空间了包含的是对应主键再根据主键进行查询索引回调索引两边索引先获得主键再主键索引获得索引的记录

附上数据太浪费空间了会造成数据的冗余但是myisam不需要进行回表查询效率还是回更高一点但是innodb支持事务而mysiam不保证事务