MySQL索引原理

时间:2022-10-11 08:51:44

一、索引的作用及现象

对于数据库来说,最常使用的操作不是插入和删除,而是查找。只要为数据库加上正确的索引,查找的速度就会提高很多。但是查找效率的提高是以插入,删除数据的速度为代价的。
常见的索引分为:

  • 主键索引
  • 唯一索引
  • 普通索引
  • 全文索引–解决中文子索引的问题。

添加索引的语法是:index(字段)添加索引也是需要消耗时间的,但是一旦添加了就不需要进行重复添加了。
为了更加清晰的看到这一现象,我们建立一个拥有海量数据的数据库,并通过查询时间的变化体现索引的价值:
MySQL索引原理
该数据库大概有八百多万条数据,在没有加入索引的时候,查询数据,发现时间在7s到9s之间。
下面对数据库进行加入索引:

mysql> alter table EMP add index(empno);

MySQL索引原理
此时显示添加成功,下面我们再重复查询一下上述数据:
MySQL索引原理
会发现时间已经变成了0.0几秒。
这就是索引的作用,大大提高了搜索的效率。

二、理解索引的准备工作

1.MySQL的工作过程

要理解索引的底层原理,我们需要先认识磁盘,因为MySQL是可以近似认为是直接和磁盘打交道的(实际上也是将数据从磁盘先加载到内存)。
MySQL数据库对数据的访问,全部都是内存中进行的,定期将数据刷新到磁盘中,所以MySQL是多线程的。
MySQL在启动的时候,就会直接给自己malloc出一大块内存空间(buffer_pool),然后由这个buffer_pool将数据刷新到磁盘中。刷新的过程是一个系统调用,如果不想让OS帮忙做这件事,也可以手动刷新:
MySQL索引原理
所以数据库访问磁盘的方式,大致是这样的,与用户访问磁盘的方式基本相同。只不过有了数据库之后,用户直接访问数据库即可。
MySQL索引原理

2.MySQL与磁盘的交互

这里的一切交互指的是I/O交互,要理解I/O交互,首先需要认识一下磁盘。

(1)磁盘的结构

我们可以把磁盘近似认为一个柱状结构,它的每一个切面都有很多个同心圆,每个同心圆称为一个磁道。每个磁道都有一个编号,最外面的磁道的编号是0。每个磁道又被划分成若干段(段又叫扇区),每个扇区存储的容量为512字节。每个扇区都有一个编号。
MySQL索引原理

(2)定位扇区

如果我们知道磁头位置,柱面位置,扇区位置即可定位扇区,磁头,柱面和扇区都是有对应的编号的。这种磁盘数据定位的方式我们称为CHS。不过实际上系统软件使用的并不是CHS(但是硬件是),而是LBA。它是一种线性地址,可以类比虚拟地址与物理地址。系统将LBA地址最后会转化为CHS,交给磁盘去进行数据读取,不过我们现在不关心这些细节,知道这个东西,让我们逻辑自洽起来就好。

(3)磁盘与内存交互的单位

Page的引入

在系统上不是以扇区大小(512字节)为单位进行数据交互的。

  • 如果操作系统直接使用硬件提供的数据大小进行交互,那么系统的IO代码,就需要和硬件强相关,换言之,如果硬件发生变化,那么系统也必须跟着变化。
  • 从目前来看,单词IO使用512字节,还是太小了。IO单位小,意味着读取相同的数据内容,需要进行多次访问操作,会降低磁盘效率。
  • 之前学习文件系统,就是在磁盘的基本结构下建立的,文件系统读取基本单位,不是扇区而是数据块。

因此引入了数据块,系统读取磁盘是以块为单位的,基本单位是4KB。
而MySQL是一个应用软件很难想象成一种特殊的文件系统,它有着更高级的IO场景。所以为了提高基本的IO效率,MySQL进行IO的基本单位是16KB(后面统一使用InnodeDB存储引擎讲解)

mysql> show global status like 'innodb_page_size';

MySQL索引原理
16384/1024=16。
也就是说,磁盘这个硬件设备基本单位是512字节,而MySQL innodb引擎使用的是16KB进行IO交互。即MySQL和磁盘进行数据交互的基本单位是16KB。这个基本数据单元,在MySQL这里叫做page(注意和系统的page进行区分)。
但是在实际上MySQL还是通过内存与磁盘交互的,可以理解为16KB的数据被分为四份,进行内存与磁盘间的交互。

为何要是Page

因为局部性原理。
当要查找一条数据的时候,假设第一次加载了id=1的数据,第二次要查找id=2的数据,还需要再加载一次,这样就进行了两次IO。
而这两条数据数值相近,很可能就保存在同一个Page中,那么第一次查询id=1的时候,id=2已经被加载到内存了,就不需要再进行IO了。当然也可能不在,当不在的时候再去进行IO也不迟。
以上原理称为局部性原理,其实IO效率低下的最主要矛盾不是IO单次数据量的大小,而是IO的次数。

(4)磁盘随机访问与连续访问

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

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

(5)总结

  • MySQL中的文件,是以page为单位保存在磁盘中的。
  • MySQL的增删查改操作,都是需要通过计算找到对应的插入位置的,或者找到对应要修改或者查询的数据。
  • 而只要涉及运算,就需要有CPU的参与,为了便于CPU的参与,一定要先将数据加载到内存中。
  • 所以在特定的时间内,数据一定是在磁盘中有,内存中也有,后续操作完内存数据之后,以特定的刷新策略,刷新到磁盘。而这时,就涉及到磁盘和内存数据交互,也就是IO了。此时的IO的基本单位是Page。即改变一个数据哪怕只改变了1bit,也需要刷新Page大小。
  • 为了更好的进行上面的操作,MySQL服务器在内存中运行的时候,在服务器内部,就申请了被称为Buffer_Pool的大内存空间,来进行各种缓存,其实就是很大的内存空间,来进行IO交互。
  • 为了更高的效率,一定要减少系统和磁盘IO的次数。

三、索引的原理

1.主键默认排序

首先建立一个测试表:

mysql> create table user(
    -> id int primary key,---一定要添加主键
    -> age int not null,
    -> name varchar(16) not null
    -> );
mysql> insert into user(id,age,name) values(3,18,'祖国人'),
    -> (4,16,'星光'),
    -> (2,26,'梅芙女王'),
    -> (5,36,'屠夫'),
    -> (1,56,'士兵男孩')
    -> ;

MySQL索引原理
我们是乱序插入的,但是显示出来之后是有序的,这是为什么呢?这是因为为了方便以后的主键索引,所以在有主键的情况下进行了默认的排序。

2.I/O请求

系统中一定存在大量的I/O请求(多个进程),OS需要对这些IO请求来进行管理,管理的方式还是先描述,再组织。可以将每一个请求看成一个结构体,通过链表的形式来进行链接。同时在磁盘中一定存在一个IO运行队列以及等待队列。

struct request_io
{
	char* start,end;
	pid_t id;
}
struct disk
{
	struct request_io queue;
	struct task_struct* wait_queue;
}

3.单页情况

(1)数据的链表结构

类比到MySQL,MySQL中在任何一个时刻一定存在大量的Page,MySQL本身也需要对这些Page来进行管理。方式依然是先描述,再组织。

struct Page
{
	struct Page* prev;
	struct Page* next;
	char buffer[];//Page空间
}

以上这些内容都是存在于内存中的。
MySQL索引原理
不同的Page,在MySQL中,都是16KB,使用prev和next构成双向链表,因为有主键的问题,MySQL会默认按照主键给我们的数据来进行排序,从上面的Page中的数据可以看出,它们也是使用链表进行连接的,是彼此进行关联的。

插入数据不按照插入的顺序,而进行排序的原因:
插入数据进行排序的目的就是提高查找的效率,页内部存放数据的模块,实际上也是一个链表的结果,链表的特点也就是增删查改,查询修改慢,所以优化查询的效率是必须的。
正因为有序,在查找的时候,从头到后都是有效查询,没有任何一个查找时浪费的,而且如果运气好,是可以提前结束查找的过程的。

(2)目录的引入

通过上面的分析,我们知道:在查询某条数据的时候直接将一整页的数据加载到内存中,以减少IO次数,从而提高性能。但是我们也可以看到,在内部,每一条数据也是通过链表链接起来的,本质上还是需要取出来特定的数据进行逐条比较。
但别忘了,这些数据都是有序的,我们可以根据这些数据的有序性,为每一个Page建立一个目录。
建立目录一定会耗费空间,但是会提高查找的效率,比如假设每一百个数据为一个目录中的内容我们要找第222个数据,那么我们直接从目录中的200页开始找起就可以了。
因此一个Page中的真正的结构是这样的
MySQL索引原理
目录的引入就大大提高了单个Page中的查找效率。

4.多页情况

以上只是一个Page的情况,只解决了在一个Page中进行查找的效率的问题。不过Page也是使用链表链接起来的,在查找的时候需要先找到这个Page,然后在Page中查找,显然使用遍历的方式进行查找太浪费时间了。
MySQL索引原理
MySQL解决这个问题的方式还是使用目录,不过这次做的是页的目录,将每页的数据的最小编号作为这个页的编号,然后创建目录页,目录页中的内容是一个个指针,指向各个页。
MySQL索引原理
我们可以来计算一下,每一个页目录中至少有一个数据和一个指针,暂时不考虑前后指针,它的大小大概是8字节,则:

16*1024/8=2048

即一个目录Page可以索引2048个存储数据的Page。那么如果Page非常非常多,导致目录也很多呢?梅开二度,为目录Page也创建一个目录Page。
这样在查找的时候,就可以先将最顶端的Page先加载到内存中,然后一层一层进行排除,最终找到要索引的值。比如我们要找18:
MySQL索引原理
只需要查询三次即可找到。
我们可以看出这实际上就是一棵B+树,MySQL底层就是使用B+树来建立索引的。这棵完整的B+树是存在于磁盘中的,而内存中有不完整的B+树。

5.为什么要是B+

  • 链表:线性遍历,不可取。
  • 二叉搜索树:有退化成链表的风险。
  • AVL或者红黑:是二叉树,太高了,比较次数太多。
  • Hash:官方的索引实现中MySQL是支持Hash的,但是Innodb和MyISAM并不支持,Hash跟进其算法特征,决定了虽然有时候也很快O(1),但是在面对范围查找就明显不行。
  • B:B树节点,既有数据,又有Page指针.而B+,只有叶子节点有数据,其他目录页,只有键值和Page指针。同时叶子节点相连是有利于进行查找的。叶子节点不存储data,这样一个节点就可以存储更多的key,可以使树更矮,所以IO操作次数更少。叶子节点相连,更便于进行范围查找。

6.总结

MySQL解决搜索效率的问题从两方面入手:

1.Page解决效率的问题
2.Page和Page之间解决效率的问题

两种解决方式都是建立一棵B+树来解决。所有的数据既有可能在磁盘中,也有可能在buffer_pool中,所有的数据必须以Page为单位进行IO,以Page为单位进行组织。
在MySQL内部,将Page以B+树的方式组织起来,形成的数据结构和与其配套的查找算法称为索引。

四、MyISAM引擎

1.聚簇索引与非聚簇索引

以上讲的都是innodb引擎下的主键索引。它是一种将用户数据和索引数据放在一起的方案,称为聚簇索引。而MyISAM引擎是将用户数据和索引数据进行分离。做法就是将数据页中的用户数据改成存放用户数据的地址。
MySQL索引原理
因此在解耦方面,MyISAM更有优势。它的叶子节点不保存数据,而是保存数据的地址。
我们可以观察一下两种引擎建立索引的不同之处:

mysql> create table mtest( id int primary key, name varchar(11) not null)engine=MyISAM;
mysql> create table istest(
    -> id int primary key,
    -> name varchar(11) not null
    -> )engine=InnoDB;

此时我们就分别使用MyISAM引擎和InnoDB引擎建立一个表。
查询索引的方式是:

mysql> show index from istest\G;
mysql> show index from mtest\G;

此时我们就可以看到该表的索引了,这里只有一个索引,即主键索引。
MySQL索引原理
其中BTree表示的是B+树。

五、索引操作

1.创建主键索引

通常情况下,我们使用的就是主键索引。主键索引的特点在于,当我们指定主键之后,MySQL会自动为其创建索引,而不需要我们自己操作,因此我们只需要指定主键即可。

//建表时直接指定主键的两种方式
mysql> create table user1(id int primary key,name varchar(30));
mysql> create table user2(
    -> id int,
    -> name varchar(30),
    -> primary key(id)
    -> );
//建表后指定主键    
mysql> create table user3( id int, name varchar(30) );
mysql> alter table user3 add primary key(id);

当我们指定主键之后,其实也就默认使用了主键索引。

2.创建普通索引

//建表时在表的最后指定索引
mysql> create table user8(
    -> id int primary key,
    -> name varchar(20),
    -> email varchar(30),
    -> index(name)
    -> );
//建表后指定某列为索引    
mysql> alter table user8 add index(email);
//新建一个索引并取别名
mysql> create table user10(
    -> id int primary key,
    -> name varchar(20),
    -> email varchar(30)
    -> );
mysql> create index idx_name on user10(name);

如果不取别名,那么索引的名字应该为列的名字。同时,一个表中可以有多个索引。
MySQL索引原理
可以看到user8是有三个索引的。分别是主键索引,name和email。而且结构都是B+树。

3.唯一键索引

当创建唯一键的时候,和主键一样,MySQL也为其创建了索引,因此我们只需要建立唯一键即可:

//建表的时候建立唯一键
mysql> create table user4(
    -> id int primary key,
    -> name varchar(30) unique
    -> );
//建表的时候再最后指定唯一键    
mysql> create table user5(
    -> id int primary key,
    -> name varchar(30),
    -> unique(name)
    -> );
//建表之后添加索引    
mysql> create table user6( id int primary key, name varchar(30) );
mysql> alter table user6 add unique(name);

4.全文索引

我们目前使用的所有索引建立都是基于一列的,一列的信息量都不大,但如果一列是一篇文章呢?
当对文章字段或有大量文字的字段进行检索时,会使用到全文索引。MySQL提供全文索引机制,但是有要求,要求表的存储引擎必须是MyISAM,而且默认的全文索引支持英文,不支持中文,如果对中文进行全文索引,可以使用sphinx的中文版(coreseek)。
我们建立一个表并向其中插入数据:

mysql> CREATE TABLE articles (
    -> id INT UNSIGNED AUTO_INCREMENT NOT NULL PRIMARY KEY,
    -> title VARCHAR(200),
    -> body TEXT,
    -> FULLTEXT (title,body)
    -> )engine=MyISAM;
mysql> INSERT INTO articles (title,body) VALUES
    -> ('MySQL Tutorial','DBMS stands for DataBase ...'),
    -> ('How To Use MySQL Well','After you went through a ...'),
    -> ('Optimizing MySQL','In this tutorial we will show ...'),
    -> ('1001 MySQL Tricks','1. Never run mysqld as root. 2. ...'),
    -> ('MySQL vs. YourSQL','In the following database comparison ...'),
    -> ('MySQL Security','When configured properly, MySQL ...');

此时我们使用一段话来模拟一篇文章,下面我们来查询一下有没有database数据:

mysql> select * from articles where body like '%database%';
mysql> explain select * from articles where body like '%database%'\G;//使用explain工具可以看出是否用到了索引

我们发现,使用这条语句是完全可以查询到的,但是却没有用到索引:
MySQL索引原理
如何使用全文索引呢?

mysql> select* from articles where match(title,body) against('database');
mysql> explain select* from articles where match(title,body) against('database');

MySQL索引原理
此时我们发现key是title,说明使用到了全文索引。

六、索引创建原则

  • 比较频繁作为查询条件的字段应该创建索引。
  • 唯一性太差的字段不适合单独创建索引,即使频繁作为查询条件。
  • 更新非常频繁的字段不适合作创建索引。