MySQL 索引

MySQL 索引

索引概述

索引是 帮助MySQL高效获取数据的数据结构。

MySQL 数据存储硬盘不是连续存储，记录的存储单位是数据页，每次查询需对数据页的进行读取和加载，免不了 IO 操作，如果遍历全部页，那么意味着进行多次 IO 操作。

索引通过实现了一套数据结构，记录了数据页和记录的关系，使得以更少的 IO 次数获取到目标数据页。此外，该数据结构对数据进行了预先排序，满足特定查找算法，可以更快的查询到数据页上的目标记录。因此，索引可以通过减少 IO 操作次数、使用更加快速的查找算法查找到目标记录。

索引的优缺点

优点

1. 索引可以加快查找数据的速度，减少数据库的 IO 成本；
2. 通过创建唯一索引，可以保证数据库表中每一行 数据的唯一性；
3. 可以 加速表和表之间的连接 。换句话说，对于有依赖关系的子表和父表联合查询时，可以提高查询速度；
4. 在使用分组和排序子句进行数据查询时，可以显著减少查询中分组和排序的时间 ，降低了CPU的消耗。

缺点

1. 创建索引和维护索引耗费时间 ，并且随着数据量的增加，所耗费的时间也会增加；
2. 索引需要占磁盘空间 ，除了数据表占数据空间之外，每一个索引还要占一定的物理空间；
3. 虽然索引大大提高了查询速度，同时却会降低更新表的速度。

InnoDB 索引设计

CREATE TABLE index_demo(
    c1 INT,
    c2 INT,
    c3 CHAR(1),
    PRIMARY KEY(c1)
  ) ROW_FORMAT = Compact;

这个新建的 index_demo 表中有2个 INT 类型的列，1个 CHAR(1) 类型的列，而且我们规定了c1列为主键。以下讨论的是以 c1 建立的索引数据结构。

记录存储结构

这个表使用 Compact 行格式来实际存储记录的。这里我们简化了 index_demo 表的行格式示意图：

1. record_type ：记录头信息的一项属性，表示记录的类型， 0 表示普通记录、 2 表示最小记录、 3 表示最大记录、 1 忽略；
2. next_record ：记录头信息的一项属性，表示下一条地址相对于本条记录的地址偏移量，我们用箭头来表明下一条记录是谁；
3. 各个列的值 ：这里只记录在 index_demo 表中的三个列，分别是 c1 、 c2 和 c3 ；
4. 其他信息 ：除了上述3种信息以外的所有信息，包括其他隐藏列的值以及记录的额外信息。

数据页存储结构

记录的存储单元是数据页，数据页除了存储普通记录之外，还存储了最小记录和最大记录，记录直接通过 next_record 指向进行连接，形成单向链表。

目录项存储结构

跟据某个搜索条件查找一些记录时之所以要遍历所有的数据页，是因为各个页中的记录并没有规律，我们并不知道我们的搜索条件匹配哪些页中的记录，所以不得不依次遍历所有的数据页。MySQL 使用 目录项 来组织数据页，从而更快的判断出符合条件的记录在哪个数据页。

每个目录项对应一个数据页，目录项主要包含 key 和 page_no；其中 key 使用对应数据页的索引键的最小值填充，即对应的是页中 c1 的最小值。page_no 是对应页的页码。

记录目录项的页

显然，要索引到搜索条件匹配哪些页中的记录，还需要存储目录项，MySQL 同样把目录项作为一条记录存储到页中，和记录项不同，目录项的 record_type 值是1。

目录项记录和普通的用户记录的不同点：

• 目录项记录 的 record_type 值是1，而 普通用户记录 的 record_type 值是0；
• 目录项记录只有主键值和页的编号 两个列，而普通的用户记录的列是用户自己定义的，可能包含很多列 ，另外还有InnoDB自己添加的隐藏列。

目录项记录和普通的用户记录的相同点：

• 两者用的是一样的数据页，都会为主键值生成 Page Directory （页目录），从而在按照主键值进行查找时可以使用二分法 来加快查询速度。

现在以查找主键为 20 的记录为例，根据某个主键值去查找记录的步骤就可以大致拆分成下边两步：

1. 先到存储目录项记录的页，也就是页30中通过二分法快速定位到对应目录项，
2. 再到存储用户记录的页9中根据 二分法快速定位到匹配主键值的用户记录。

由于页的存储是有限的，所有每一页存储的目录项有限，当用户记录过大，目录项分布到多个页中，这是就需要再增加页来存储目录页的关系，从而形成树级分布的结构，称为B+树。

一个 B+树 的节点其实可以分成好多层，规定最下边的那层，也就是存放我们用户记录的那层为第 0 层，之后依次往上加。

文件存储

新建一张 InnoDB 引擎的表会生成两个文件，文件格式分别为：.frm、.ibd，.frm 存放了表结构，.ibd 存放索引和数据，所以 innodb 又称索引即数据，数据即索引。

MyISam 索引设计

和 InnoDB 索引 最大的设计区别是：叶子节点的 data 域存放的是数据记录的地址。因此，每次索引到对应的记录之后，数据库会做一次回表，获取记录的整体信息。

文件存储

新建一张 MyISam 引擎的表会生成三个文件，文件格式分别为：.frm、.MYD（存放数据）、.MYI（存放索引），.frm 存放了表结构，MYD 存放数据、MYI 存放索引。

MyISAM 与 InnoDB 索引对比

1. InnoDB 包含1个主键索引，该索引包含了用户记录所有字段的值，根据主键值对 聚簇索引 进行一次查找就能找到对应的记录，MyISAM 中需要进行一次回表操作。MyISAM 数据域存储了记录的地址；
2. InnoDB 的数据文件本身就是索引文件，而 MyISAM 索引文件和数据文件是分离的 ，索引文件仅保存数据记录的地址；
3. InnoDB 的非主键索引 data 域存储相应记录主键的值 ，而 MyISAM 索引记录的是地址；
4. MyISAM 的回表操作是十分快速的，因为是拿着地址偏移量直接到文件中取数据的，InnoDB 是通过获取主键之后再去聚簇索引里找记录，虽然说也不慢，但还是比不上直接用地址去访问。
5. InnoDB要求表 必须有主键 （ MyISAM可以没有 ）。如果没有显式指定，则MySQL系统会自动选择一个可以非空且唯一标识数据记录的列作为主键。如果不存在这种列，则MySQL自动为InnoDB表生成一个隐含字段作为主键，这个字段长度为6个字节，类型为长整型。

索引的代价

空间

每建立一个索引都要为它建立一棵 B+ 树，每一棵 B+ 树的每一个节点都是一个数据页，一个页默认会占用 16KB 的存储空间，一棵很大的 B+树 由许多数据页组成，那就是很大的一片存储空间。

时间

每次对表中的数据进行 增、删、改 操作时，都需要去修改各个 B+ 树索引。B+ 树每层节点都是按照索引列的值从小到大的顺序排序 而组成了 双向链表 。不论是叶子节点中的记录，还是内节点中的记录（也就是不论是用户记录还是目录项记录）都是按照索引列的值从小到大的顺序而形成了一个单向链表。而增、删、改操作可能会对节点和记录的排序造成破坏，所以存储引擎需要额外的时间进行一些 记录移位 ， 页面分裂 、 页面回收等操作来维护好节点和记录的排序。如果我们建了许多索引，每个索引对应的 B+ 树都要进行相关的维护操作，会给性能拖后腿。