参考文章

MySQL 是怎样运行的:从根儿上理解MySQL

前言

我们知道 InnoDB 基本存储单元为页,每个数据页也可以组成一个双向链表,每个数据页中的记录会按照主键值从小到大的顺序组成一个 单向链表,每个页都会为存储在它里边的记录生成一个页目录,在通过主键查找时可以在页目录中使用二分法快速定位到对应的槽,然后再遍历该槽中对应分组中的记录,这样就可以快速找到指定的记录。

从页的存储结构中就可以映射出 B+ 索引的基本结构。

没有索引的查找

在介绍索引之前,我们需要知道没有索引的时候是怎么查找记录的。为了方便理解,我们只考虑精确匹配

1
2
3
SELECT id, name FROM USERS WHERE id=1;

SELECT id, name FROM USERS WHERE name='lyon.lei';

在页中查找

假设我们数据量很少,不需要考虑多个页的情况下,记录都存放在一个页中。

  • 以主键为搜索条件

    ​ 就像前言说的,我们可以通过页目录通过二分查找,快速的定位到对应的相应的记录。

  • 以其他列作为搜索条件

    ​ 如果搜索条件不是主键,那么可能就有些费力了,不能通过页目录快速定位对应记录,只能通过从最小的记录开始遍历页中所有的记录,然后对比每条记录是否符合条件。

在很多页中查找

大部分场景下,表记录是非常多的,需要很多数据页来存储这些记录。

  • 以主键为搜索条件

    从第一页沿着双向链表一直往下找,通过每页的页目录判断查找的条件是否符合,如果符合则通过二分查找,定位对应的记录

  • 以其他列作为搜索条件

    ​ 从第一页沿着双向链表一直往下找,每页都需要遍历所有记录,然后一一对比是否符合条件,非常恐怖。

在没有索引的条件下,不论是不是以主键搜索,都需要从第一页开始沿着双向链表一直往下找,这样是非常耗时与消耗资源的。这时候索引就发挥了很大的作用了。

索引

一个简单的索引方案

假设我们没页只存几条记录,我们仿照着页生成的页目录,给它们做个目录,每个页对应一个目录项,每个目录项对应着两部分

  • 页的用户记录中最小的主键值

  • 页号

几个页的目录大概样子:

我们只需要把几个目录项在物理存储器中连续存储,比如放在一个数组中,就可以实现根据主键值款速查找某条记录的功能了,那么具体的查找过程就可以分为两步:

  1. 先从目录项中根据二分查找快速定位主键所在的目录项。

  2. 然后根据目录项找到所对应的页,在根据页目录查找到对应的记录。

以上的“目录”其实就是一个简单的索引。

InnoDB 中的索引方案

以上是一个简单的索引方案,是因为我们假设所有目录项都可以在物理存储器上连续存储,但是这样会有几个问题:

  • InnoDB 是使用页来作为基本存储单位的,也就是最多能保证 16KB 的连续存储空间,而随着表记录数量的增多,需要非常大的连续存储空间,这肯定是不现实的。
  • 我们经常需要对记录进行增删,假设我们连续存储空间中的一个页,那么后面的所有目录项都向前移动一下,这种牵一发而动全身的设计并不是很好的注意。

其实目录项长得和我们的用户存储的记录是差不多的,只不过存储的内容主要有主键和页号而已,所以MySQL大佬们,就复用了之前存储用户记录的数据页来存储目录项,为了区分,我们把这样来标识目录项的记录成为“目录项记录”,数据库如何区分的呢,利用记录中的头信息里record_type 值来进行区分。

虽说目录项记录中只存储主键值和对应的页号,会比用户记录需要的空间小很多,但是一个页只有 16KB 的大小,终归还是有上限的,所以当一个页存满了,会再分配一个页来进行存储,就像存储用户记录一样。

现在因为存储目录项记录的页不止一个,所以如果我们想根据主键值查找一条记录大致需要三步:

  1. 确定目录记录页
  2. 确定记录真实所在页
  3. 确定记录所在具体位置

那么有个问题,在第一步中我们需要定位存储目录项记录的页,但是这些页在存储空间中也可能不挨着,如果我们数据量很大,产生很多存储目录项记录的页,那么我们怎么根据主键值快速定位一个存储目录项记录的页呢?其实很简单,我们再生成一个更高级的目录即可。

最终的结构就是这样,这就是 B+树:

索引的代价

索引虽然是个好东西,可是不能乱建,它在空间和时间上都会拖后腿:

  • 空间上的代价

    这个是显而易见的,每建立一个索引都要为它建立一颗 B+ 树,每一颗 B+ 树的每个节点都是一个数据页,一个页默认占用 16 KB的存储空间,一颗很大的 B+ 树由很多数据页组成,那么就会消耗一大片存储空间。

  • 时间上的代价

    每次对表中的数据进行增删改操作时,都需要去修改各个 B+ 树索引,而且,B+树每层节点都是按照索引列的值从小到大顺序排列而组成双线链表。不论是叶子节点中的记录,还是内节点的记录,都是按照索引列的值从小到大的顺序而形成的单向链表。所以在增删改操作时,会对节点和记录的排序造成破坏,所以存储引擎需要额外的时间进行一些记录位移,页面分裂、页面回收的操作来维护好节点和记录的排序。

所以说,一个表的索引建的越多,就会占用越多的存储空间,在增删改记录的时候性能就越差。

全值匹配

如果我们的搜索条件中的列和索引列一致的话,这种情况就称为全值匹配。

1
select * from users where name='lyon.lei' and age=24 and phone = '12345678910'

我们建立的 idx_name_age_phone 索引包含的3个列在这个查询语句中都展现出来了,那么这个查询过程就是:

  • 因为B+树的数据页和记录先是按照name列的值进行排序的,所以先可以很快定位name列的值是 lyon.lei记录位置
  • 在 name 列相同的记录里又是按照age列的值进行排序的,所以在name列的值是 lyon.lei 的记录里又可以快速定位到 age为 24 的记录位置
  • 如果name和age列的值都完全匹配上,那么记录按照 phone 列的值排序的,所以联合索引的三个列都有可能用到

如果我们的SQL这样写:

1
select * from users where  phone = '12345678910' and age=24 and  name='lyon.lei'

如果我们条件语句与索引的顺序不一致的话,那么查询优化器会分析搜索条件并按照可以使用的索引中的列顺序来决定先使用哪个搜索条件,后使用哪个搜索条件。

匹配左边的列

其实在我们的搜索语句中也可以不用包含全部联合索引中的列,只包含左边的即可:

1
select * from users where name='lyon.lei'

或者包含多个左边的列也行:

1
select * from users where name='lyon.lei' and age=24

如果是这种SQL就不会用到建立的索引:

1
select * from users where phone='123'

因为B+树的数据页和记录先是按照name列的值排序,在name值相同的情况下才使用age列拍讯,也就是说name列的值不同的记录中age列的值可能是无序的,而现在是跳过name以及age去查找phone,那么数据库引擎是办不到的,如果非要只差 phone 一个字段的话,可以多建立一个索引即可。

所以,如果我们想使用联合索引中尽可能多的列,搜索条件中的各个列必须是联合索引中从最左边连续的列。比方说联合索引 idx_name_age_phone 中定义的顺序是 name,age,phone,如果我们的搜索条件只有 name 和 phone,那么就只会用到 name 索引,因为 name 值相同的记录,先按照 age 的值进行排序,age值相同的记录才按照 phone 值排序。

1
select * from users where name='lyon.lei' and phone='123'

匹配列前缀

1
select * from users where name like 'AB%'

在某个列建立索引其实就在对应的 B+树的记录中试用该列的值进行排序,所以对于字符串类型的索引列来说,我们只匹配它的前缀也是可以快速定位记录的。

回表的代价

idx_name_age_phone 索引为例

1
select * from users where name > 'Aaa' and name < 'Zzz'

在使用 idx_name_age_phone 索引进行查询时大致可以分为两步:

  1. 从索引 idx_name_age_phone 对用的B+树种取出name值在 Aaa ~ Zzz 之间的记录。
  2. 由于索引 idx_name_age_phone 对应 B+树用户记录只包含 name,age,phone,id 四个字段,而查询的字段列表为 * 所以,这时还需要把从上一步中获取到的每一条记录的 id 字段都到聚簇索引对应的 B+索引对应的B+树找到完整的用户记录,这就是所谓的回表,然后把完整的用户记录返回给查询用户。

由于 idx_name_age_phone 索引对应B+树中的记录首先会按照name值进行排序,所以值在 Aaa~Zzz之间的记录在磁盘中的存储都是相连的,集中分布在一个或几个数据页中,我们可以很快的把这些连着的记录从磁盘中读出来,这种读取方式我们也可以称之为顺序I/O

根据搜索条件获取到的记录的id字段值可能不是相连的,而聚簇索引中记录是根据id的顺序排列的,,所以根据这些并不连续的id值到聚簇索引中访问完整的用户记录可能分布在不同的数据页中,这样读取完整的用户记录可能要访问更多的数据页,这种读取方式就称之为随机I/O

一般情况下,顺序I/O比随机I/O性能高很多,所以第一步执行很快,而第二步就相对慢一些,所以使用idx_name_age_phone索引的查询就有这么两个特点:

  • 会使用到两个 B+树索引,一个二级索引,一个聚簇索引
  • 访问二级索引使用顺序I/O,访问聚簇索引使用随机I/O

需要回表的记录越多,使用二级索引的性能就月底,甚至某些查询宁愿使用全表扫描也不适用二级索引,比方说,name值 Aaa ~ Zzz 之间的记录数超过 90%的id需要回表,那还不如直接扫描聚簇索引来的快。

那么什么时候采用全表扫描,什么时候采用二级索引+回表的方式进行查询呢?这个选择其实就是查询优化器需要做的工作,但是我们可以通过SQL语句来让查询优化器倾向于选择某种方式,例如:

1
select * from users where name > 'Aaa' and name < 'Zzz' limit 10

添加了 limit 的查询,查询优化器会更倾向于采用二级索引+回表的方式进行查询,因为是范围查询,而且回表的记录数较少。

1
select * from users order by name, age, phone

由于是查询列表时 * ,所以如果使用二级索引进行排序的话,需要把排序完的二级索引记录全部进行回表操作,这样操作的成本还不如直接遍历聚簇索引然后再进行文件排序来得快呢,所以查询优化器会更倾向于全表扫描

最后

  1. B+树索引在空间和时间上都有代价,所以没事儿别瞎建索引。
  2. B+树索引适用于下边这些情况:
    • 全值匹配
    • 匹配左边的列
    • 匹配范围值
    • 精确匹配某一列并范围匹配另外一列
    • 用于排序
    • 用于分组
  3. 在使用索引时需要注意下边这些事项:
    • 只为用于搜索、排序或分组的列创建索引
    • 为列的基数大的列创建索引
    • 索引列的类型尽量小
    • 可以只对字符串值的前缀建立索引
    • 只有索引列在比较表达式中单独出现才可以适用索引
    • 为了尽可能少的让聚簇索引发生页面分裂和记录移位的情况,建议让主键拥有AUTO_INCREMENT属性。
    • 定位并删除表中的重复和冗余索引
    • 尽量使用覆盖索引进行查询,避免回表带来的性能损耗。