MySQL索引

标签：index 扇区 索引 IO MySQL 磁盘 主键

索引的引入

在数据库表中，查询某条数据记录通常就是遍历，遍历表中所有的数据，然后一条一条比对，因此注定它是O(N)的时间复杂度。由于数据库的数据是存储在磁盘上的，必然要进行大量IO数据的读取，冯诺依曼体系告诉我们，对磁盘数据的读取效率是远低于与内存中数据的，尽管存在局部性原理，O(N)的时间复杂度依旧决定会进行大量的磁盘交互，这就是查询效率慢的主要原因。

索引就是一种提高搜索效率的有效方式，不需要修改程序，不需要调用sql，只需要建立正确的index索引就能提高搜索的效率。mysql会在磁盘上构建特定的数据结果（红黑树），提高优化算法+减少IO次数的方式，提高读取的效率。

必然的，搜索效率的提升，必然导致创建特定数据结构空间的增加。对应的增加/删除/修改等操作会更加费时费力。

所以，索引是为了提升select的速度，这个量级通常是成千上万倍。优化体现在算法+磁盘IO。

 常见的索引：

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

索引的优势

在sql下创建一张海量数据表（8 000 000条数据）。对比这俩次查找的时间

• 1、在没有索引的情况下查询工号:777777的员工
• 2、为员工编号创建索引，继续查询工号:777777的员工

1）在没有索引的情况下，直接查找编号，耗时 1.67s秒

2）为empno创建索引，并且查询777777

alter table EMP add index(empno)

以empno建立索引，会消耗一定的时间，因为底层需要创建相应的数据结构。

创建完毕后，继续查询指定员工

几乎立马就查询到结果，这个速度整整快了几万倍。

见识到索引的优势后，就来学习一下索引的原理，以及如果设置索引。

---

 必备的知识

为了认识索引，必须用要从底层讲起，也必须了解一下数据的存储与读取。

认识磁盘

磁盘的物理结构

磁盘是多种结果组成的，我们只需要了解几个特定的结构即可。

• 磁盘：数据被通过电信号再在磁盘上，磁盘是数据实际存储元件。
• 磁头：用于读取数据
• 磁头臂：带动磁头左右移到
• 主轴：使磁盘转动

认识盘片

 磁道：以主轴为圆心，可以将一块盘片分割成许多同心圆，每一个同心圆称为一个磁道

扇区：从圆心出发，将磁道分为若干段，每一个小段，就是扇区。

• 数据的交互是以扇区为单位的，通常来说一个扇区512字节
• 不难发现靠近圆心的扇区的面积小于远离圆心的扇区面积，所以靠近圆心的扇区密度更大
• 近年来，容量更大的磁盘用4K取代512字节，称为4K扇区。

扇区的定位

linux中的文件就是存储在扇区上的，简单来说，想要获取到磁盘上的指定数据，就必须定位到指定编号的扇区。

定位的方法就是CHS寻址法

先找到柱面---再找到磁头---最后定位扇区。

• 磁盘是由许多盘片组成，每一个盘片是由一个磁头，磁头是双面的，即一个盘片的正反面都能存储数据。
• 先定位到是哪一个磁道，因为一排磁道构成柱面形状，也就是找到柱面。---H
• 找到在哪一个磁头上，就是定位磁头。---H
• 定位到某一个盘面的磁道和扇区后，通过旋转轴旋转，就能找到指定的扇区。

但是系统定位磁盘是通过线性结构LBA，将每一个磁道展开，一个磁道是由对应编号的扇区，这个映射关系由OS替我们完成。

单次IO的大小

通过磁盘的物理结构，我们知道扇区的最小单位是512字节，有的是4K，那么OS与磁盘交互是以512字节为基础建立的吗？
实际上并不是，而是以4K进行交换

原因主要是：

1. 物理内存是被划分为4KB的页框，磁盘也被划分为4KB的页帧，这样符合对齐。
2. 如果读取依赖于磁盘的扇区的大小，那么磁盘和OS就是强相关，不利于硬件的更新换代。
3. 局部性原理：请求某一个扇区的资源后，下一次请求大概率会在这个扇区附近，直接把相邻扇区的资源也进行IO，大概率会减少IO的次数。

磁盘的随机访问与连续访问

连续访问：在某一次访问扇区后，下一次访问靠近该扇区，也就是磁头的转动几乎是不计算的。

随机访问：改变磁头、判断的位置，耗费大量的时间，俩次访问地址相差较大。

所以：连续访问是优于随机访问的。

MySQL与磁盘交互的基本单元

MySQL是建立在应用层上的服务，在客户端会通过OS请求磁盘的IO，完成数据的CURD。

我们可以把MySQL想象成直接和磁盘打交道，注定是要进行大量的磁盘IO，MySQL与磁盘交互的最小单位是16KB！这个交互叫做Page

交互的过程

MySQL进行CURD的操作，首先要找到磁盘上对应扇区的数据，将扇区上的数据加载到内存中，根据冯诺依曼体系结构，真正和磁盘打交道的OS，只有先把数据加载到OS上，在通过OS提供给mysqld，才能进行相应的CURD;

mysql如果对数据修改，就需要从借助OS把数据拷贝到磁盘中。

mysql进行的这一个交换的单位就是page。

为了提高效率，会在mysqld客户端上new一块空间，这个空间就是缓冲区。OS交给mysql客户端的数据被放到缓冲区中。mysql需要刷新到磁盘的数据，会先存在缓冲区，在交给OS，最后由OS进行数据的刷新。

这一个mysql客户端打开就被创建的内存级缓冲区叫做buffer poll，如果数据提前被缓存在bufferpoll中就无需再次进行磁盘IO，没有再去磁盘中寻找。

所以Buffer Poll减少IO的次数，提高效率。

 为什么Page的大小是16字节？

 为什么MySQL与磁盘的交互是16字节的Page呢？而不是按需加载，需要多少就IO多少？
假设有一个员工表，有id和name组成。往表中插入5条数据 id为1~5。

• 如果是按需IO：我们需要查询编号为1的员工，那么就会进行一次IO，如果在查询编号为2的员工，第二次IO,同理会至多进行五次IO。
• 如果是利用Page进行IO，第一次查询编号为1的员工，会将1~5的员工全部加载到Buffer poll中，后续查询 id=1,2,3,4,5的员工只需在内存中查找。
• 根据局部性原理，下一次访问的数据，大概率会在相邻的位置上。

推导Page的结构

单个Page 

磁盘中存在大量的文件，一个文件管理一个或者多个Page，Page是什么？
Page是mysql与磁盘交互的基本单位，所以对Page的管理无非就是先描述，在组织。

• Page的描述，Prev与Next指针，负责找到前一个Page和后一个Page。
• 指针指向数据的存储。

注意:如果数据设置了主键，那么在page的记录是按照主键的顺序存放的。

一个page的大小是16字节，通常来说，单个page会存在大量的数据，就比如我们查找1之后，想要查找5，只能逐个遍历。因此页目录的引入，提高了查找的效率。

页目录：将单个page的数据进行分组（大部分是1-8条，也有1-4条），目录是一个指针，指向最小编号的起始位置。

• 通过引入页目录之后，如果我们想查询id=5的员工，只需要查询3次，即跳转3次页目录（1，2，3） 

虽然页目录也会占用一定的存储空间，但是它能够在消耗非常少空间的情况下，极大的提高数据的查询效率，数据的记录越多，目录查询的效率就越显著。

就像我们有一本书，我们想查找某个单元的内容，就会先找到目录，通过目录跳转页码。

管理多个Page 

 随着数据量增大,单个Page必然无法存储下数据，也就会存在大量的page。

对大量page的管理就是利用链表数据结构，组织起来，就是一个双向链表！

如果在大量的page中查找指定的主键值（key），凭借链表的查找，时间复杂度是O(N)。

查询的方法，先在第一个page内查询，在往后的page跳转。这是O(N)的空间复杂度。

为了能够优化page的查找，减少IO的次数，为page页也增加目录。

page页目录的序号是以最小存放的那一页最小的编号起始。

这一个结果有一个特点：页page不存储数据，只存储对应page的地址。普通页中即存储数据记录，也存储少量的目录。

如果数据量再大，为了提高搜索速度，会在加一层页目录

这一个结构的特点完全符合B+树的特点

• 叶子存储数据
• 非叶子节点保存叶子节点的指针
• 查找的时候，是从上往下查找，只要拿着key和page的编号比较，就能跳转到叶子中。在叶子节点中，继续通过叶子跳转。

 在mysql中，如果设置是索引，mysql就会自动在磁盘构建以page以基本的B+树，每一种索引键就构建一棵树。实际上，上图画的就是InnoDB的索引结构。

OS进行IO操作，读取对应的叶子节点放到bufferPoll缓冲区中，并不意味着整颗树都会被加载进缓冲区，只是一部分。

选择B+树的原因

为什么只有B+树行？

换句话就是为什么mysql选择B+树？而不是链表、普通搜索树、哈希等？
要解决这个问题，主要围绕着优化算法+减少磁盘IO次数。

链表？不行：线性遍历，IO次数非常大。

普通二叉搜索树？极端情况下会退化为线性链表 ，高IO

AVL和红黑树 ？AVL和红黑树是绝对平衡的树，时间复杂度是O(logN)。但是AVL和红黑树都是二叉树，就会导致如果数据很多，高度就会很高，形成一颗瘦高的树。如果一颗瘦高的树，每一个高度都会进行IO，会进行高度次IO操作，也是不够优秀的。

B树？B树是多叉树，但是它的存储方式是非叶子节点保存数据，就会导致它的高度比B+树高，IO的次数多于B+树，和B+树比起来不够优秀。

Hash?官方的mysql是支持哈希做索引的结构，只不过InnoDB和MyISAM存储引擎并不支持；因为哈希会存在严重的哈希碰撞，导致空间浪费。实际上，哈希也不利于数据的范围查找。

所以mysql选择B+树，完全是因为B+符合磁盘的IO，是一颗绝对矮胖的树，IO次数充分的少。并且能够将范围内的数据同时获取到。

---

聚簇索引 VS 非聚簇索引

• 数据记录和索引放在一起的数据结构叫做聚簇索引，常见的有Innodb
• 数据记录和索引分离的数据结构叫做聚簇索引，常见的有MyISAM

MyISAM 存储引擎-主键（普通）索引

之前推导的B+树是Innodb存储引擎的主键索引，而MyISAM同样采用B+树的的基本结构。

但是不同的是，Innodb的叶子节点存储key主键，而MyISAM的叶子节点存储指向记录的地址

MyISAM最大的特点就是索引page和数据page分离，也就是叶子节点没有数据，只有地址。

而Innodb是索引和page放在一起的，叶子节点存储数据记录。

InnoDB存储引擎 - 普通索引结构

普通索引和主键索引没有本质的区别，无非就是普通索引是可以重复的。

InnoDB的普通索引叶子节点保存的是主键索引的key，通过普通索引找到key后，在通过主键索引找到叶子的数据记录，这一过程就叫做回表查询。

为什么不给普通索引的叶子节点也上数据呢？因为太浪费空间了。

---

索引的操作

创建索引

主键索引

• 在创建表的时候，附带哪一列是主键；

create table if not exists t1 ( 
    id int primary key auto_increment,
     name varchar(20) not null);

直接指定以id为主键primary key建立索引

• 在创建表的最后，指明哪一列是主键；

mysql> create table if not exists t2(
    -> id int ,
    -> name varchar(20),
    -> primary key(id));

• 表被创建后，添加某一列为主键

create table t3 (
     id int , 
     name varchar(20) not null);
Query OK, 0 rows affected (0.02 sec)

mysql> alter table t3 add primary key (id);

注意：关于主键索引的注意点

1. 主键索引不能重复，不能为空null。
2. 主键索引的效率最高，搜索速度最快。
3. 一张表只能有一个主键索引。

---

唯一键索引

• 在创建表的时候，指定某一列为唯一键

create table t1( id int primary key, 
    name varchar(20) unique );

• 在创建表的最后，指定为唯一键

mysql> create table t2(
    -> id int ,
    -> name varchar(20),
    -> primary key(id),
    -> unique(name));

• 表被创建后，在指定唯一键

mysql> create table t3( 
    id int , 
    name varchar(20));
mysql> alter table t3 add unique (name);

唯一键索引的特点：

1. 一个表中可以有多个唯一键索引，唯一键可以为null。
2. 如果给唯一键索引设置了not null ，等价于主键索引。

---

普通键索引

本质上唯一键索引也是普通索引，它们唯一的区别就是是否重复。

普通键索引的创建方式和主键、唯一键类似。

• 在创建表的最后，指定为唯一键

mysql> create table t1(
    -> id int primary key,
    -> name varchar(20) ,
    -> index(name));

• 表创建后，添加普通键 

 alter table t2 add index(name);

• 表创建后，通过为表创建普通索引 

mysql> create table t3( id int, name varchar(20));
//创建名为index_name 的普通索引
mysql> create index index_name on t3(name);

 

---

查看索引

常用的查看索引的方式有三种

主要是:

• desc
• show index from 
• show keys from 

例如：desc + 表名

对应的key这一列就是索引的情况，普通索引：mul 。唯一键索引：unl 。主键索引:pri。

show index from +表名

 show index from index_table\G;

一种索引方式就会创建一个B+树，每个B+树都会以表的形式显示出来。

show keys form +表名

得到的结果和show index from 是一样的

---

删除索引

 索引的删除主要有三种

• alter table from 表名 primary key

alter table index_table drop primary key;

• 删除其它索引

 alter table +表名 drop index (index_name) ：index_name 就是show index form 中的key_name

mysql> alter table index_table drop index(qq);

• drop index  索引名 on 表名

mysql> drop index name on index_table;

---

全文索引 

全文索引是针对文章内容关键字的快速检索。

全文索引只支持MyISAM，而且只支持中文。

主要用到FULLTEXT关键字和match匹配。

创建测试表

CREATE TABLE articles (
id INT UNSIGNED AUTO_INCREMENT NOT NULL PRIMARY KEY,
title VARCHAR(200),
body TEXT,
FULLTEXT (title,body)
)engine=MyISAM;

插入一堆数据

INSERT INTO articles (title,body) VALUES
('MySQL Tutorial','DBMS stands for DataBase ...'),
('MySQL vs. YourSQL','In the following database comparison ...'),
('MySQL Security','When configured properly, MySQL ...');

查询关键字database;

普通的方法就是模糊匹配 like %

select * from articles where body like '%database%';

这是没有用到索引的，在大量数据下效率不高。

通过fulltext索引查询database

SELECT * FROM articles
-> WHERE MATCH (title,body) AGAINST ('database');

 

 创建索引的原则

1. 查找频繁的字段要创建索引
2. 在where不会出现的字段不应该创建索引
3. 唯一性太差的字段，不应该被设为索引
4. 索引应该尽量以数字为主

标签：index,扇区,索引,IO,MySQL,磁盘,主键
From： https://blog.csdn.net/m0_73299809/article/details/140670906