MySQL索引内部原理

一、索引概述

索引即一本书的目录，我们通过书的目录能够快速的查到对应文章的页码。数据库的索引也差不多，通过在某些字段建立索引，可以快速的查找某些特定的数据，避免全表搜索。

因为数据库表的数据在磁盘文件中，会将对应数据读取到内存中进行检索，全表搜索会带来更多的IO操作，比较耗时，应尽量避免IO操作。

MySQL官方对索引的定义为：索引（Index）是帮助MySQL高效获取数据的数据结构。

索引是在存储引擎中实现的，所以不同的存储引擎，索引也不一定相同。

索引的优点：

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

索引的缺点：

• 创建索引和维护索引要耗费时间。
• 索引是存储在磁盘上的，如果有大量的索引，索引文件就可能比数据文件更快达到最大文件尺寸
• 虽然索引大大提高了查询速度，同时却会降低更新表的速度。当对表中的数据进行增加、删除和修改的时候，索引也要动态地维护，这样就降低了数据的维护速度。

二、设计索引

想到查找，那我们可能会想到二叉搜索树，然后再到红黑树，但这两种树的类型都是二叉的，所以高度很高，意味着磁盘I/O会产生多次，为了降低树的高度，索引会采用多叉树的结构，即B树。

首先看下面的一张表：

1.  
   mysql> CREATE TABLE index_demo(
2.  
   -> c1 INT,
3.  
   -> c2 INT,
4.  
   -> c3 CHAR(1),
5.  
   -> PRIMARY KEY(c1)
6.  
   -> ) ROW_FORMAT = Compact;

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

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

当插入三条记录后，如下：

记录存放的基本单位是页的形式，一个页默认容量为16KB

 这三条记录是以主键递增的形式排列的，在每个页中也维护了一个数组，称为页目录，该数组记录了主键和该条记录的地址。当我们想查找其中的一条记录时，就可以通过二分法去查找，加快查询速度。

假设当前页满了，此时insert一条记录，就会新建一个页用于存放新纪录(页之间也是链表)，但是如果插入的记录主键不是递增的，需要插入到页的中间，那么会触发另一种机制，即页分裂：新建一个页将当前页的一半移动到新页，然后再插入。所以，尽量使用递增的形式插入。

引入目录项

如果有多个页了，假设我们要查找主键最大的那条记录，此时每个页都需要被加载一遍，因为我们并不知道该条记录在具体的哪个页。为了解决该问题，我们可以为所有页建立一个目录：

 以页28为例，它对应目录项2 ，这个目录项中包含着该页的页号28以及该页中用户记录的最小主 键值5 。

比如：查找主键值为 20 的记录，具体查找过程分两步：

1. 先从目录项中根据二分法快速确定出主键值为20的记录在目录项3中（因为 12 < 20 < 209），它对应的页是页9。
2. 再根据前边说的在页中查找记录的方式去页9中定位具体的记录。至此，针对数据页做的简易目录就搞定了。

当然，多个目录项上也可以生成目录。

在InnoDB中索引结构即如下：

这个数据结构，它的名称是B 树。树中的叶子结点都为数据记录，非叶子结点为目录记录。

B 树一般都不会超过4层，所以查找起来非常快速，需要的I/O次数也很少。

三、常见索引概念

索引按照物理实现方式，索引可以分为2 种：聚簇（聚集）和非聚簇（非聚集）索引。我们也把非聚集索引称为二级索引或者辅助索引。

1. 聚簇索引

聚簇索引不仅仅是索引，它还存放了完整的数据，数据都存放在它的叶子节点上。

特点：

• 使用主键值的大小进行记录和页的排序，这包括三个方面的含义：
  • 页内的记录是按照主键的大小顺序排成一个单向链表 。
  • 各个存放用户记录的页也是根据页中用户记录的主键大小顺序排成一个双向链表。
  • 存放目录项记录的页分为不同的层次，在同一层次中的页也是根据页中目录项记录的主键 大小顺序排成一个双向链表 。
• B 树的叶子节点存储的是完整的用户记录。

聚簇索引并不需要我们在MySQL语句中显式的使用INDEX语句去创建，InnoDB存储引擎会自动的为我们创建聚簇索引。

优点：

• 数据访问更快，因为聚簇索引将索引和数据保存在同一个B 树中，因此从聚簇索引中获取数据比非聚簇索引更快，不需要回表
• 聚簇索引对于主键的排序查找和范围查找速度非常快(因为叶子结点是有序链表)
• 按照聚簇索引排列顺序，查询显示一定范围数据的时候，由于数据都是紧密相连，数据库不用从多个数据块中提取数据，所以节省了大量的io操作。

缺点：

• 插入速度严重依赖于插入顺序，按照主键的顺序插入是最快的方式，否则将会出现页分裂，严重影响性能。因此，对于InnoDB表，我们一般都会定义一个自增的ID列为主键
• 更新主键的代价很高，因为将会导致被更新的行移动。因此，对于InnoDB表，我们一般定义主键为不可更新，二级索引访问需要两次索引查找，第一次找到主键值，第二次根据主键值找到行数据

限制：

• 目前只有InnoDB支持聚簇索引
• 由于数据物理存储排序方式只能有一种，所以每个MySQL的表只能有一个聚簇索引。一般情况下就是该表的主键
• 如果没有定义主键，会选择一个非空的唯一索引充当，如果没有这样的字段，InnoDB会隐式的定义一个主键作为聚簇索引

2. 二级索引（辅助索引、非聚簇索引）

聚簇索引只能在搜索条件是主键值时才能发挥作用，如果是其他的条件，是不能快速查找的，解决方法是：多建几棵B 树。

如下图，建立以c2列作为排序规则的B 树：

 该二级索引和聚簇索引的区别是：为了节省空间，叶子结点存放的不是完整的数据，而是索引列的值和主键的值组成。

需要查找完整的数据时，如需要得到c3的值时，是得不到的，因为这些额外的数据存放在聚簇索引里，这时候的查询步骤为：

• 先根据条件在二级索引中找到对应的叶子结点(数据)
• 拿到叶子结点中保存的主键
• 回到聚簇索引，再去拿着主键去查找对应的数据列

该步骤称为回表查询。比聚簇索引慢一倍。

注意：如果仅仅需要得到二级索引中已经有的列，那么就不需要回表查询

一张表能同时能有多个二级索引

3.联合索引

也属于非聚簇索引，只是一种特殊形式。它同时以多个字段的排序规则创建B 树，如c2，c3做一个联合索引，它包含两个含义：

1. 先把各个记录和页按照c2列进行排序。
2. 在记录的c2列相同的情况下，采用c3列进行排序
    

 如上，每个叶子都包含了c2，c3两个记录，还包含必须的主键c1。

4.MyISAM中的索引

Innodb和MyISAM默认的索引是Btree索引；而Memory默认的索引是Hash索引。

Hash索引查找单个值更快，但是不适合范围查找。

MyISAM引擎使用B Tree作为索引结构，叶子节点的data域存放的是数据记录的地址，而不是主键id，因为MyISAM表的索引和数据存放在两个不同的文件中。

5.MyISAM与InnoDB对比

① 在InnoDB存储引擎中，对聚簇索引查找不需要回表，而在MyISAM中所有索引都需要回表，意味着MyISAM中建立的索引相当于全部都是二级索引。

② InnoDB的数据文件本身就是索引文件，而MyISAM索引文件和数据文件是分离的，索引文件仅保存数据记录的地址。

③ InnoDB的非聚簇索引data域存储相应记录 主键的值，而MyISAM索引记录的是地址 。换句话说， InnoDB的所有非聚簇索引都引用主键作为data域。

④ MyISAM的回表操作是十分快速的，InnoDB是通过获取主键之后再去聚簇索引里找记录，虽然说也不慢，但还是比不上直接用地址去访问。

⑤ InnoDB要求表必须有主键 （ MyISAM可以没有 ）。如果没有显式指定，则MySQL系统会自动选择一个可以非空且唯一标识数据记录的列作为主键。如果不存在这种列，则MySQL自动为InnoDB表生成一个隐含字段作为主键，这个字段长度为6个字节，类型为长整型。

四、B-Tree和B Tree对比

B-Tree结构如下

 树中的非叶子结点是实打实的记录。

B Tree是对B-Tree的一个改进，B Tree更适合文件索引系统。

• B Tree的非叶子结点只需要存目录，不需要存数据，所以在一个页中，能存放更多的目录，树的高度相对更低，需要的磁盘IO也会更少。
• B Tree所以的叶子结点是一个有序链表，所以范围查找和排序等效率更高。

这篇好文章是转载于：学新通技术网