基本概念

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

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

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

有两种基本的索引类型：

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

InnoDB的索引模型

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

上图中页面号为20的页面是根页面，根页面存储了，pageno存储指向叶子节点的页面号。叶子节点存放的是，真正存放哪些数据还是取决于B+ Tree是聚簇索引还是辅助索引。

分类

在 MySQL InnoDB 中索引通常可以分为两大类：主键索引（即聚簇索引）和辅助索引（非聚簇索引） 。

• 聚簇索引：表示表中的数据按照主键顺序存储，是索引组织表，在InnoDB中就是按照主键顺序构建B+ Tree，叶子节点就是行记录，数据行和主键值存储在一起。只能创建一个。
• 辅助索引（二级索引）：根据索引列构建B+ Tree，B+ Tree每一个叶子节点存索引列，加速回表操作。

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

对于没有指定主键的表，InnoDB会自己选择合适的字段作为主键，选择顺序如下：

1. 显式主键
2. 第一个唯一索引
3. 内置的6字节ROWID

根据索引列个数和功能描述不同索引也可以分为：联合索引和覆盖索引。

• 联合索引是指在多个字段联合组建的。
• 当通过索引即可查询到所有记录，不需要回表到聚簇索引时，这类索引称为覆盖索引。
• 主键查询是天然的覆盖索引，联合索引也可以是覆盖索引。

覆盖索引

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

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

索引使用技巧

创建索引规范

• 命名规范
• 单张表索引数量不超过5个，单个索引的字段不超过5个
• 禁止冗余索引，重复索引，索引维护需要成本，新增索引时优先考虑基于现有索引进行rebuild
• 联表查询，JOIN列的数据类型必须相同，并且要建立索引
• 不在低基数列创建索引（性别列）
• 选择区分度大的列（最好唯一性）建立索引
• 对过长的VARCHAR段建立索引，优先考虑前缀索引
• 频繁作为WHERE查询条件的字段
• 经常GROUP BY和ORDER BY的列
• UPDATE、DELETE 的 WHERE 条件列，一般也需要创建索引
• DISTINCT 字段需要创建索引

索引失效的情况：

• 索引进行表达式计算
• 索引字段使用函数
• 在WHERE子句中，如果在OR前面的条件列进行了索引，后面的没有进行索引，那么索引会失效
• 当我们使用 LIKE 进行模糊查询的时候，前面不能是 %
• 索引列与 NULL 或者 NOT NULL 进行判断的时候也会失效。

索引维护

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

最左前缀原则

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

如果你创建了一个三列的联合索引包含(col1, col2, col3), 你的索引会生效于(col1), (col1, col2), 以及(col1, col2, col3)。

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

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

如果有一个联合索引(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

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

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树的查找方式类似于平衡二叉树，在此不多赘述。

B+ Tree

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

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

其基本结构如下图所示：

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

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

Hash索引

与B+ Tree的区别：

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