MySQL索引特性——会涉及索引的底层B+树

发布于:2025-03-17 ⋅ 阅读:(18) ⋅ 点赞:(0)

1 没有索引,可能会有什么问题

        索引:提高数据库的性能,索引是物美价廉的东西了。不用加内存,不用改程序,不用调sql,只要执行正确的 create index ,查询速度就可能提高成百上千倍。但是天下没有免费的午餐,查询速度的提高是以插入、更新、删除的速度为代价的,这些写操作,增加了大量的IO。所以它的价值,在于提高一个海量数据的检索速度。

        常见索引分为:主键索引(primary key),唯一索引(unique),普通索引(index),

全文索引(fulltext)——解决中子文索引问题

案例:

--进入随便一个数据库后将下面的内容粘贴即可创建一张海量数据表
DROP TABLE IF EXISTS `EMP`;
CREATE TABLE `EMP` (
  `empno` int(6) unsigned zerofill NOT NULL COMMENT '雇员编号',
  `ename` varchar(10) DEFAULT NULL COMMENT '雇员姓名',
  `job` varchar(9) DEFAULT NULL COMMENT '雇员职位',
  `mgr` int(4) unsigned zerofill DEFAULT NULL COMMENT '雇员领导编号',
  `hiredate` datetime DEFAULT NULL COMMENT '雇佣时间',
  `sal` decimal(7,2) DEFAULT NULL COMMENT '工资月薪',
  `comm` decimal(7,2) DEFAULT NULL COMMENT '奖金',
  `deptno` int(2) unsigned zerofill DEFAULT NULL COMMENT '部门编号'
);
--构建一个8000000条记录的数据
--构建的海量表数据需要有差异性,所以使用存储过程来创建, 拷贝下面代码就可以了,暂时不用理解
-- 产生随机字符串
delimiter $$
create function rand_string(n INT)
returns varchar(255)
begin
declare chars_str varchar(100) default
'abcdefghijklmnopqrstuvwxyzABCDEFJHIJKLMNOPQRSTUVWXYZ';
declare return_str varchar(255) default '';
declare i int default 0;
while i < n do
set return_str =concat(return_str,substring(chars_str,floor(1+rand()*52),1));
set i = i + 1;
end while;
return return_str;
end $$
delimiter ;
--产生随机数字
delimiter $$
create function rand_num()
returns int(5)
begin
declare i int default 0;
set i = floor(10+rand()*500);
return i;
end $$
delimiter ;
--创建存储过程,向雇员表添加海量数据
delimiter $$
create procedure insert_emp(in start int(10),in max_num int(10))
begin
declare i int default 0;
set autocommit = 0;
repeat
set i = i + 1;
insert into EMP values ((start+i)
,rand_string(6),'SALESMAN',0001,curdate(),2000,400,rand_num());
until i = max_num
end repeat;
commit;
end $$
delimiter ;
-- 执行存储过程,添加8000000条记录
call insert_emp(100001, 8000000);

        在不创建索引的情况下,查询员工编号为998877的员工,话费了1.99秒

        这仅仅是一个人查询的情况,如果放在公网同时有多个人并发查询,很有可能死机。

        下面我们创建索引,然后查询员工编号为123456的员工,基本不需要时间

2 认识磁盘

        MySQl与存储:MySQL给用户提供存储服务,而存储的是数据,数据在磁盘这个外设当中。磁盘是计算机中的一个机械设备,相比与计算机其他电子元件,磁盘效率是比较低的,在加上IO本身的特征,可以知道,如何提升效率是MySQL的一个重要话题

        先来研究一下磁盘

        再看看磁盘中的一个盘片

        扇区:数据库文件,本质其实就是保存在磁盘的磁片中,也就是上面的一个个小格子中,就是我们经常说的扇区。当然,数据库文件很大,也很多,一定需要占据多个扇区

        从图上看距离圆心越近的扇区越小,所以扇区存储内容并不是通过面积来衡量的,而是通过比特位密度决定的,不过最新的磁盘技术,已经慢慢的让扇区大小不同了。

        我们使用的linux,所看到的大部分目录或者文件,其实就是保存在磁盘当中。(当然,有一些内存文件系统,如proc、sys之类的我们并不考虑)

        所以,最基本的,找到一个文件的全部,本质,就是在磁盘找到所有保存文件的扇区

        而我们能够定位任何一个扇区,那么便能找到所有扇区,因为查找方式是一样的。

        

        柱面(磁道):多盘磁道,每盘都是双面,大小完全相等。那么同半径的磁道,整体上便构成了一个柱面

        每个盘面都有一个磁头,那么磁头和盘面的对应关系便是1对1的

        所以,我们只需要知道,磁头(Heads)、柱面(Cylinder)(等价于磁道)、扇区(Sector)对应的编号,即可在磁盘上定位要访问的扇区,这种磁盘数据定位的方式叫做CHS。不过实际系统软件使用的并不是CHS(但是硬件是),而是LBA,一种线性地址,可以想象成虚拟地址和物理地址。系统将LBA地址最后会转化成为CHS,交给磁盘去进行数据读取。不过,我们现在不关心转化细节,知道这个细节,让我们逻辑自洽起来即可。

结论

        我们现在已经能够在硬件层面定位,任何一个基本数据块了(扇区)。那么在系统软件上,就直接按照扇区(512字节,部分4096字节),进行IO交互吗?不是

        如果操作系统直接使用硬件提供的数据大小进行交互,那么系统的IO代码,就和硬件强相关,换言 之,如果硬件发生变化,系统必须跟着变化

        从目前来看,单次IO 512字节,还是太小了。IO单位小,意味着读取同样的数据内容,需要进行多 次磁盘访问,会带来效率的降低。

        之前学习文件系统,就是在磁盘的基本结构下建立的,文件系统读取基本单位,就不是扇区,而是 数据块。

        故,系统读取磁盘,是以块为单位的,基本单位是 4KB 。

        磁盘随机访问(Random Access)与连续访问(Sequential Access)

        随机访问:本次IO所给出的扇区地址和上次IO给出扇区地址不连续,这样的话磁头在两次IO操作之间,需要做比较大的移动动作才能重新开始读/写数据

        连续访问:如果当次IO给出的扇区地址于上次IO结束的扇区地址是连续的,那磁头就能很快的开始这次IO操作,这样的多个IO操作称为连续访问

        因此尽管相邻的两次IO操作在同一时刻发出,但如果他们的请求扇区地址相差很大的话,也只能称为随机访问,而非连续访问。

        磁盘是通过机械运动进行寻址的,随机访问不需要过多的定位,故效率比较高

3 MySQL与磁盘交互基本单位

        MySQL作为一款应用软件,可以想像成一种特殊的文件系统。它有着更高的IO场景,所以,为了提高基本的IO效率,MySQL进行IO的基本单位是16KB

        也就是说,磁盘这个硬件设备的基本单位是512字节,而MySQL InnoDB引擎使用16KB进行IO交互。即MySQL和磁盘进行数据交互的基本单位是16KB,这个基本数据单元,在MySQL这里叫做page(注意和系统的page区分)

4 建立共识

        MySQL中的数据文件,是以page为单位保存在磁盘当中的

        MySQL的CURD操作,都需要通过计算,找到对应的插入位置,或者找到对应要修改或者查询的数据

        而只要涉及计算,就需要CPU参与,而为了便于CPU参与,一定要能够先将数据移动到内存当中。(CPU只与内存进行交互)

        所以在特定的时间内,数据一定是磁盘中有,内存中也有,后续操作完内存数据之后,以特定的刷新策略,刷新到磁盘。而这时,就涉及到了内存和磁盘的数据交互,也就是IO了。而此时IO的基本单位就是page(16KB)。

        为了更好的进行上面的操作,MySQL服务器在内存中运行的时候,在服务器内部,就申请了被称为Buffer Pool的大空间,来进行各种缓存,其实就是很大的内存空间,来和磁盘数据进行IO交互。

        为了更高的效率,一定要尽可能的减少系统和磁盘IO的次数

5 索引的理解

建立测试表

插入多条数据

查询插入结果,我们发现默认是有序的!

为何IO交互要是Page

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

        如上面的记录,如果MySQL要查询id=2的记录,第一次加载id=1,第二次加载id=2,一次一条记录,那么就需要2次IO,如果需要找id=5那么就需要5次IO

        但,如果这5条记录(或者更多)都被保存在一个Page中(16KB,可以保存很多数据),那么第一次IO查询id=2的时候,整个Page会被加载到MySQL的Buffer Pool中,这里完成了一次IO,但是往后如果在查询id=1,3,4,5等完全不需要进行IO了,而是直接在内存中进行了。所以,就在单Page里面,大大减少了IO次数

        怎么保证,用户下一次找的数据,就在这个Page里面?我们不能严格保证,但是有很大的概率,因为局部性原理

        往往IO效率低下的最主要矛盾不是IO单次数据的大小,而是IO的次数

        理解单个Page:MySQL中要管理很多数据表文件,而要管理好这些文件,就需要先描述,在组织,我们目前可以简单理解成一个独立文件是由一个或者多个Page构成的。

        不同的Page,在MySQL中都是16KB的,使用prev和next构成双向链表

        因为主键的问题,MySQL会默认按照主键给我们的数据进行排序,从上面的Page内数据记录可以看出,数据是有序且彼此关联的。

         为什么数据库在插入数据时要对其进行排序呢?我们按正常顺序插入数据不是挺好的吗?

        插入数据时排序的目的是优化查询的效率。

        页内部存放数据的模块,实质上也是一个链表的结构,链表的特点就是增删块,查询修改慢,所以优化查询的效率是必须的。

        正是因为有序,在查询的时候,从头到后都是有效查找,没有任何一个查询是浪费的,而且,如果运气好,是可以提前结束查询过程的。

        理解多个Page:通过上面的分析,我们知道上面页模式,只有一个功能,就是在查询某条数据的时候直接将一整页的数据加载到内存中,以减少硬盘IO次数,从而提高性能。但是我们可以看到现在的页模式内部,实际上采用了链表的结构,前一条数据指向后一条数据,本质上还是通过数据的逐条比较来取出特定的数据。

        如果有1千万条数据,一定需要多个Page来保存1千万条数据,多个Page彼此使用双链表链接起来,而且每个Page内部的数据也是基于链表的,那么,查找特定一条记录,也一定是线性查找。这效率太低了。

        

        页目录

        我们在看《谭浩强C程序设计》这本书的时候,如果我们要看<指针章节>,找到该章节有两种做法        

         从头逐页的向后翻,直到找到目标内容

        通过书提供的目录,发现指针章节在234页(假设),那么我们便直接翻到234页。同时,查找目录的方案,可以顺序找,不过因为目录肯定少,所以可以快速提高定位

        本质上,书中的目录,是多花了纸张的,但是却提高了效率

        所以,目录,是一种“空间换时间的做法

        单页情况

        针对上面的单页Page,我们能否也引入目录呢?当然可以

        那么当前,在一个Page内部,我们引入了目录。比如,我们要查找id=4记录,之前必须线性遍历4次,才能拿到结果。现在直接通过目录2[3],直接进行定位新的起始位置,提高了效率。现在我们可以再次正式回答上面的问题了,为何通过键值 MySQL 会自动排序?

        可以很方便引入目录

        多页情况

        MySQL 中每一页的大小只有 16KB ,单个Page大小固定,所以随着数据量不断增大, 16KB 不可能存下所有的数据,那么必定会有多个页来存储数据。

        在单表数据不断被插入的情况下, MySQL 会在容量不足的时候,自动开辟新的Page来保存新的数据,然后通过指针的方式,将所有的Page组织起来。

        需要注意,上面的图,是理想结构,大家也知道,目前要保证整体有序,那么新插入的数据,不一定会在新Page上面,这里仅仅做演示。

        这样,我们就可以通过多个Page遍历,Page内部通过目录来快速定位数据。可是,貌似这样也有效率问题,在Page之间,也是需要 MySQL 遍历的,遍历意味着依旧需要进行大量的IO,将下一个Page加载到内存,进行线性检测。这样就显得我们之前的Page内部的目录,有点杯水车薪了。 那么如何解决呢?解决方案,其实就是我们之前的思路,给Page也带上目录。

        使用一个目录项来指向某一页,而这个目录项存放的就是将要指向的页中存放的最小数据的键值。

        和页内目录不同的地方在于,这种目录管理的级别是页,而页内目录管理的级别是行。

        其中,每个目录项的构成是:键值+指针。图中没有画全。

        

        存在一个目录页来管理页目录,目录页中的数据存放的就是指向的那一页中最小的数据。有数据,就可通过比较,找到该访问那个Page,进而通过指针,找到下一个Page

        其实目录页的本质也是页,普通页中存的数据是用户数据,而目录页中存的数据是普通页的地址。

        可是,我们每次检索数据的时候,该从哪里开始呢?虽然顶层的目录页少了,但是还要遍历啊?不用担心,可以在加目录页

        这货就是传说中的B+树啊!没错,至此,我们已经给我们的表user构建完了主键索引。

        随便找一个id=?我们发现,现在查找的Page数一定减少了,也就意味着IO次数减少了,那么效率也就提高了

复盘一下

        Page分为目录页和数据页。目录页只放各个下级Page的最小键值。

        查找的时候,自定向下找,只需要加载部分目录页到内存,即可完成算法的整个查找过程,大大减 少了IO次数

本文并不涉及索引的操作,下文会单独讲索引的操作