深入MySQL索引细节

索引基本概念

维基百科对索引的定义：数据库索引是一种数据结构，它以额外的写入和存储空间为代价来提高数据库表上数据索引操作的速度。

MySQL官方对索引的定义是用于快速查找记录的一种数据结构。

索引是一个以空间换时间的经典案例。

  • 索引是物理数据页，数据页大小决定了一个页可以存储多少个索引行，以及需要多少页来存储指定大小的索引。
  • 索引可以加快检索速度，也可以降低索引列插入、删除、更新的速度，索引维护需要代价。

有两种基本的索引类型：

  • 顺序索引：基于值的顺序排序
  • 散列索引：基于将值平均分布到若干bucket中，一个值所属的bucket是由一个散列函数决定。

索引的数据结构

B Tree

查询的时间主要依赖于磁盘I/O的次数，每次节点访问需要进行一次磁盘IO操作。 B Tree取代平衡二叉树主要是降低了树的高度，减少了磁盘IO的次数。其基本结构如下：

B Tree

B Tree别称平衡的多路搜索树，每个节点最多包括M个子节点，M称为B树的阶。

M阶的B树（M > 2）有以下的特性：

  • 根节点的儿子数的范围是 [2,M]。
  • 每个中间节点包含 k-1 个关键字和 k 个孩子，孩子的数量 = 关键字的数量 +1，k 的取值范围为 [ceil(M/2), M]。
  • 叶子节点包括 k-1 个关键字（叶子节点没有孩子），k 的取值范围为 [ceil(M/2), M]。
  • 假设中间节点节点的关键字为：Key[1], Key[2], …, Key[k-1]，且关键字按照升序排序，即 Key[i]<Key[i+1]。此时 k-1 个关键字相当于划分了 k 个范围，也就是对应着 k 个指针，即为：P[1], P[2], …, P[k]，其中 P[1] 指向关键字小于 Key[1] 的子树，P[i] 指向关键字属于 (Key[i-1], Key[i]) 的子树，P[k] 指向关键字大于 Key[k-1] 的子树。
  • 所有叶子节点位于同一层。

B+ Tree

B+ Tree与B Tree的差异主要有以下几点：

  1. 有 k 个孩子的节点就有 k 个关键字。也就是孩子数量 = 关键字数，而 B 树中，孩子数量 = 关键字数 +1。
  2. 非叶子节点的关键字也会同时存在在子节点中，并且是在子节点中所有关键字的最大（或最小）。
  3. 非叶子节点仅用于索引，不保存数据记录，跟记录有关的信息都放在叶子节点中。而 B 树中，非叶子节点既保存索引，也保存数据记录。
  4. 所有关键字都在叶子节点出现，叶子节点构成一个有序链表，而且叶子节点本身按照关键字的大小从小到大顺序链接。

其基本结构如下图所示：

B+Tree

B+ Tree与B Tree的根本的差异在于B+ Tree的中间节点不直接存储数据。

  1. B+ Tree更矮胖，IO次数更少，同样的磁盘页大小， B+ Tree可以存储更多的节点关键字。
  2. B+ Tree查询效率更稳定，每次只有访问到叶子节点才能获取到对应的数据。
  3. 范围查询的效率高于B Tree，因为所有的关键字都出现在B+ Tree的叶子节点中，并通过有序链表进行连接。

Hash索引

与B+ Tree的区别：

  • Hash索引不能进行范围查询，不支持ORDER BY排序。因为Hash索引指向的数据是无序的。
  • Hash索引不支持联合索引的最左前缀原则，因为Hash索引计算Hash的时候是将索引键合并后再一起计算。
  • 等值查询效率高，无法进行模糊查询。

MySQL中Memory引擎支持Hash索引，InnoDB本身不支持Hash索引，但是提供了自适应Hash索引（Adaptive Hash Index）：当某个数据经常被访问，当满足一定条件时，就会把数据页地址放到Hash表中，下次查询时，则直接找到页面的地址。

InnoDB索引模型

MySQL中，索引在存储引擎层实现，所以不同的存储引擎层支持的索引类型可以不同，InnoDB和MyISAM的索引都是使用B+ Tree实现的。B+ Tree结构如下图所示： B+ Tree

上图中页面号为20的页面是根页面，根页面存储了<key + pageno>，pageno存储指向叶子节点的页面号。叶子节点存放的数据由索引类型决定。聚簇索引的节点存放的是列数据，二级索引存放的是主键信息。

的是<key + data>，真正存放哪些数据还是取决于B+ Tree是还是辅助索引。

B+ Tree索引的特点：

  • 根页面位置不动：
  • 非叶子节点中目录项记录的唯一性
  • 一个页面最少存储两条记录

分类

在 MySQL InnoDB 中索引通常可以分为两大类(物理实现方式)：主键索引（即聚簇索引）和辅助索引（非聚簇索引） 。

  • 聚簇索引：表中的数据按照主键顺序存储，是索引组织表，在InnoDB中就是按照主键顺序构建B+ Tree，叶子节点就是行记录，数据行和主键值存储在一起。只能创建一个。
    • 为了充分利用聚簇索引的特性，表的主键尽量使用有序id，不建议使用UUID，HASH等方式。
  • 辅助索引（二级索引）：根据索引列构建B+ Tree，B+ Tree每一个叶子节点的data域存储主键值，查询到主键后，再去聚簇索引中进行回表查询。

聚簇索引占用的空间就是整个表数据量的大小，而二级索引只是存储主键值，主要提高查询效率。

对于没有指定主键的表，InnoDB会自己选择合适的字段作为主键，选择顺序如下： 1. 显式主键 2. 第一个唯一索引 3. 内置的6字节ROWID

根据索引列个数和功能描述不同索引也可以分为：联合索引和覆盖索引。 - 联合索引是指在多个字段联合组建的。 - 当通过索引即可查询到所有记录，不需要回表到聚簇索引时，这类索引称为覆盖索引。 - 主键查询是天然的覆盖索引，联合索引也可以是覆盖索引。

从功能逻辑上说，主要分为：

  • 普通索引（NORMAL）：不附加任何限制条件，可以创建在任何数据类型中。
  • 唯一性索引（UNIQUE）：使用UNIQUE参数设置为唯一性索引，限制该索引必须是唯一的，允许空值。
  • 全文索引（FULLTEXT）：对于长文本查询，可以创建该索引以提高查询效率。
  • 主键索引：特殊的唯一性索引，NOT NULL + UNIQUE，一个表只能由一个主键索引。

覆盖索引

如果执行的语句为select ID from T where k between 3 and 5，这时只需要查ID的值，而ID的值已经在k索引树上了，因此不需要回表，也就是，索引k已经覆盖了我们的我们的查询请求，这被称为覆盖索引。

由于覆盖索引可以减少树的搜索次数，显著提升查询性能，所以使用覆盖索引是一个常用的性能优化手段。

索引维护

B+树在插入新值的时候必须做必要的维护，如果添加新值的时候，所在数据页已经满了，这时需要申请一个新的数据页，然后挪动部分数据过去，这个过程称为页分裂。如果删除数据，可能导致页的合并。

最左前缀原则

B+树这种索引结构，可以利用索引的最左前缀，来定位记录。

问题：在建立联合索引的时候，如何安排索引内的字段顺序？

  • 第一原则是，如果通过调整顺序，可以少维护一个索引，那么这个顺序往往是需要优先考虑采用的。

如果有一个联合索引(a,b)，查询条件里面如果只有b的语句，是无法使用这个联合索引的。

这时候需要考虑的原则就是空间。

索引下推

以联合索引(name, age)为例，如果查找"名字第一个字是张，年龄是10岁的所有男孩"，SQL语句如下：

select * from user where name like '张%' and age = 10 and ismale = 1;

根据最左前缀原则，找到第一个满足第一个字是张的记录之后，判断其他条件是否满足。

在MySQL 5.6之前，只能从该记录开始一个个回表，到主键索引树上找到指定数据行，进行字段值比对。

在MySQL5.6引入索引下推优化，可以在索引遍历的过程中，对索引中包含的字段先进行判断，直接过滤掉不满足条件的记录，减少回表次数。

索引代价

  • 空间上的代价：每一个索引都会建立一颗B+ Tree，每个节点则是一个数据页，默认页大小为16KB，添加索引的同时也要考虑到空间消耗。
  • 时间上的消耗：数据进行增删改操作，都需要去维护索引，包括页面分裂、页面回收等操作。

隐藏索引

从MySQL8.x开始支持隐藏索引（invisible indexes），将待删除的索引设置为隐藏索引，使查询优化器不再使用这个索引，确定隐藏索引后系统不受任何相应，就可以彻底删除索引。（软删除）

显式删除存在的问题：删除索引后出现错误，又需要重新将索引创建回来，性能消耗非常大。

索引设计原则

创建索引规范

  • 命名规范
  • 单张表索引数量不超过5个，单个索引的字段不超过5个
  • 禁止冗余索引，重复索引，索引维护需要成本，新增索引时优先考虑基于现有索引进行rebuild
  • JOIN连接的场景
    • 连接表的数量尽量不要超过三张
    • 对WHERE条件创建索引
    • 对连接的字段创建索引，连接字段的类型必须一致
  • 选择区分度大的列（最好唯一性）建立索引
  • 对过长的VARCHAR段建立索引，优先考虑前缀索引，例如index(address(10))，取前10字符建立前缀索引。
  • 频繁作为WHERE查询条件的字段
  • 经常GROUP BY和ORDER BY的列
  • UPDATE、DELETE 的 WHERE 条件列，一般也需要创建索引
  • DISTINCT 字段需要创建索引
  • 不在低基数列创建索引（性别）
  • 避免对经常更新的表创建过多的索引
  • 不建议使用无序的值作为索引
  • 删除很少使用的索引

索引失效情况

  • 计算、函数、类型转换、不等于（!=）导致索引失效
  • 在WHERE子句中，OR的前后存在非索引列，索引失效
  • like查询以通配符%开头的索引失效
  • IS NULL可以使用索引，IS NOT NULL无法使用索引
MySQL
#MySQL
深入MySQL索引细节
https://l1n.wang/2020/MySQL/MySQL索引细节/
作者
Lin Wang
发布于
2020年5月1日
许可协议