文章目录

为什么要有索引？
认识磁盘
- 磁盘的结构
- 磁盘的盘片结构
- 定位扇区
- 磁盘随机访问 (Random Access)与连续访问 (Sequential Access)
MySQL与磁盘交互
索引的理解
- 测试主键索引
- 索引的原理
- 索引结构是否可以使用其他数据结构
- B树 vs B+树
- 聚簇索引 vs 非聚簇索引

为什么要有索引？

MySQL索引的建立对于MySQL的高效运行是很重要的，索引可以大大提高MySQL的检索速度。

打个比方，如果合理的设计且使用索引的MySQL是一辆兰博基尼的话，那么没有设计和使用索引的MySQL就是一个人力三轮车。

索引的引入，使得查询速度的提高，这种提高是以插入、更新、删除的速度为代价的，这些写操作，增加了大量的IO。所以它的价值，在于提高一个海量数据的检索速度。

常见索引：

主键索引（primary key）
唯一索引（unique key）
普通索引（index）
全文索引（fulltext）

案例：构建一个海量数据表，来验证索引带来的查询差异性

drop database if exists `test_index`;
create database if not exists `test_index` default character set utf8;
use `test_index`;

-- 构建一个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 ;

-- 雇员表
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条记录
call insert_emp(100001, 8000000);

上面的sql创建了test_index数据库，test_index中有一个含有8000000条记录的EMP表，select * from EMP limit 10 查看部分数据：

在这里插入图片描述

desc EMP;查看表结构，EMP表没有创建任何索引：

在这里插入图片描述

尝试查询EMP表的记录：

在这里插入图片描述

可以发现查询EMP表的记录，由于数据量很大而且EMP没有建立任何索引，每次都需要较长的时间进行查询。

为EMP表建立索引：

在这里插入图片描述

由于数据量很大，EMP表在创建索引需要花费较长的时间。
创建索引后尝试查询：

在这里插入图片描述
可以发现，索引大大提高了数据库表的查询速度。

认识磁盘

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

磁盘的结构

在这里插入图片描述

磁盘的盘片结构

在这里插入图片描述

在MySQL中创建数据库，本质上是在Linux下创建特定目录，在MySQL中创建数据库表，本质上是在特定的目录下创建特定的文件。数据库文件，本质上就是保存在磁盘的盘片中，也就是上图的一个个小格子中，即扇区。所以找到一个数据库文件，本质上就是在磁盘上找到对应的扇区，就需要能够定位某个盘片中的某些扇区。

定位扇区

在这里插入图片描述

柱面(磁道): 多盘磁盘，每盘都是双面，大小完全相等。那么同半径的磁道，整体上便构成了一个柱面
每个盘面都有一个磁头，那么磁头和盘面的对应关系便是1对1的

定位文件在扇区中的位置，需要知道磁头（Heads）、柱面(Cylinder)(等价于磁道)、扇区(Sector)对应的编号，即可在磁盘中定位所要访问的扇区，这种磁盘定位方式叫做CHS。在实际上硬件使用的是CHS定位方式，但是软件所用的是LBA定位方式，这是一种线性地址，可以抽象成虚拟地址和物理地址的关系，系统会将LBA地址转化成CHS地址，交给硬盘进行数据处理。

❔ 在硬件层面上，我们已经可以定位某一个扇区，那么系统软件和磁盘进行IO交互也是按照扇区（512KB）来进行的吗

系统软件和磁盘进行IO交互不是按照扇区（512KB）进行交互的
如果系统直接使用硬件提供的数据大小进行交互，那么系统的IO代码就和硬件强相关，如今硬件的发展日新月异，换言之，如果硬件发生变化，系统代码就必须大规模更改，维护成本大
512byte作为单次IO的大小太小了，这就意味着系统需要重复读取相同大小的数据，需要多次访问磁盘，效率较低
文件系统中，物理内存实际上是被分为一个个4KB的数据块的，文件系统读取磁盘的基本单位，不是扇区，而是数据块，基本单位是4KB

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

随机访问：本次IO所给出的扇区地址和上次IO给出扇区地址不连续，这样的话磁头在两次IO操作之间需要作比较大的移动动作才能重新开始读/写数据。
连续访问：如果当次IO给出的扇区地址与上次IO结束的扇区地址是连续的，那磁头就能很快的开始这次IO操作，这样的多个IO操作称为连续访问。

因此尽管相邻的两次IO操作在同一时刻发出，但如果它们的请求的扇区地址相差很大的话也只能称为随机访问，而非连续访问，因为连续访问的连续指的是物理上的连续，而不是时间上的连续。磁盘是通过机械运动进行寻址的，连续访问不需要过多的定位，故效率比较高。

MySQL与磁盘交互

MySQL作为一款应用软件，可以想象成是一种特殊的文件系统，它有着更高频的IO场景，因此为了提高基本的IO效率，MySQL与磁盘交互的基本单位是16KB，这个基本数据单元在MySQL这里也叫做Page

show global status like 'innodb_page_size查看page大小：

在这里插入图片描述

在MySQL进行CRUD时，是需要计算数据的位置的，涉及到计算就需要CPU的参与，根据冯诺依曼体系结构，CPU只和内存打交道，因此MySQL访问数据，不可能直接和磁盘交互，全部需要加载到内存进行访问。

数据库的数据是可能同时存在于内存和磁盘中的，数据在进行CRUD之后发生更改，就需要有对应的刷新策略将数据刷新到磁盘，这就说明MySQL需要较高频次的进行IO操作，为了提高效率，MySQL服务器会在内存中预先开辟一大块空间进行数据缓存，这块空间叫做buffer pool，磁盘的数据会预先加载到buffer pool中，刷新磁盘的数据也是从buffer pool中将数据刷新到磁盘。

数据是不会直接从内存刷新到磁盘的，它们的交互会经过操作系统，操作系统有对应的内核级缓冲区，当MySQL需要从磁盘上加载数据时，数据会先通过磁盘和内核缓冲区进行每次4KB的IO交互，操作系统再通过对应刷新策略，数据从内核缓冲区以每次16KB的IO交互拷贝到buffer pool中。

简化图：

在这里插入图片描述

索引的理解

测试主键索引

建立测试表：

在这里插入图片描述

插入多条记录：

在这里插入图片描述

查看插入结果：

在这里插入图片描述

索引的原理

❔ 可以发现，插入数据的时候并没有按照主键的顺序进行插入，但是插入多条数据后，结果默认就是有序的，这是为什么？

MySQL中需要管理很多的数据，管理这些数据就需要先描述，再组织，MySQL中有一个个的Page结构体，用来存放数据，MySQL中存在很多Page结构体，它们通过两个指针构成双向链表。

伪代码：

struct Page 
{
	struct Page* page_prev;
	struct Page* page_next;
	char buffer[]
};

在这里插入图片描述

在插入数据时排序，是为了优化链表增删改效率高，查询效率低的特点。但是当Page内的数据越来越多时，在页内查找也还是线性查找，于是数据库在插入时，进行排序，是为了便于建立Page中的目录。在单个Page中引入页内目录，将Page中数据分为若干区域，目录中存储这些区域中主键的最小值。
引入目录后，MySQL在进行查找时，预先查找目录中的内容，对于插入数据的主键处于目录的哪一个区间，从而到区间中查找，大大提高了在单个Page中查找数据的效率。

在这里插入图片描述