MySQL索引

摘要

索引是辅助存储引擎高效获取数据的一种数据结构。形象的说索引就是数据的目录，便于存储引擎快速的定位数据。

索引的分类

从数据结构角度

B+tree
Hash
Full-text

从物理存储角度

聚簇索引
二级索引（辅助索引）

从索引字段特性角度

主键索引
唯一索引
普通索引
前缀索引

从组成索引的字段个数角度

单列索引
联合索引（复合索引）

MySQL常见的存储引擎

	InnoDB	MyISAM	Memory
B+tree 索引	YES	YES	YES
Hash 索引	NO	NO	YES
Full-text 索引	YES	YES	NO

在实际使用中，InnoDB 作为 MySQL 建表时默认的存储引擎；B+tree 是 MySQL 中被存储引擎采用最多的索引类型。

B+tree和B-tree

1970 年，R.Bayer 和 E.Mccreight 提出了一种适用于外查找的平衡多叉树——B-树，磁盘管理系统中的目录管理，以及数据库系统中的索引组织多数采用 B-Tree 这种数据结构。–数据结构 C 语言版第二版严蔚敏

B+tree 只在叶子节点存储数据，而 B-tree 非叶子节点也存储数据。

在线测试

B-tree : https://www.cs.usfca.edu/~galles/visualization/BTree.html
B+tree : https://www.cs.usfca.edu/~galles/visualization/BPlusTree.html

B+tree和红黑树

对于有 N 个叶子节点的 B+tree，搜索复杂度为 「O(logdN) ,d 是指 degree 是指 B+tree 的度」，表示节点允许的最大子节点个数为 d 个，在实际的运用中 d 值是大于 100 的，即使数据达到千万级别时候 B+tree 的高度依然维持在 3-4 左右，保证了 3-4 次磁盘 I/O 就能查到目标数据。

红黑树是二叉树，节点的子节点个数最多为 2 个，意味着其搜索复杂度为 「O(logN)」，比 B+ 树高出不少，因此红黑树检索到目标数据所需经理的磁盘 I/O 次数更多。

B+tree 索引与 Hash 索引

如果是等价查询，则哈希索引显然具有绝对优势，因为只需一种算法即可找到相应的键值；当然，前提是键值是唯一的,如果存在hash冲突就必须链表遍历了。

哈希索引不支持范围查询(不过改造之后可以,Java中的LinkedHashMap通过链表保存了节点的插入顺序,那么也可以使用链表将数据的大小顺序保存起来)。

哈希索引无法使用索引排序以及模糊匹配；
哈希索引也不支持多列联合索引的最左边匹配规则；
键值大量冲突的情况下,Hash索引效率极低。

InnoDB

InnoDB 表要求必须有聚簇索引，默认在主键字段上建立聚簇索引，在没有主键字段的情况下，表的第一个 NOT NULL 的唯一索引将被建立为聚簇索引，在前两者都没有的情况下，InnoDB 将自动生成一个隐式自增 id 列并在此列上创建聚簇索引。

二级索引的叶子节点并不存储一行完整的表数据，而是存储了聚簇索引所在列的值。

说了聚簇索引和二级索引肯定要提到「回表查询」。

1	alter table workers add index index_name(name);

由于二级索引的叶子节点不存储完整的表数据，所以当通过二级索引查询到聚簇索引的列值后，还需要回到局促索引也就是表数据本身进一步获取数据。

需要注意的是通过二级索引查询时，回表不是必须的过程，当 Query 的所有字段在二级索引中就能找到时，就不需要回表，MySQL 称此时的二级索引为覆盖索引或称触发了「索引覆盖」。

1	select id,name from workers where name='吕归尘';

这句 SQL 只查询了 id，和 name，二级索引就已经包含了 Query 所以需要的所有字段，就无需回表查询。

1	explain select id,name from workers where name='吕归尘';

执行计划的 Extra 字段中出现了 Using where;Using index 表明查询触发了索引 index_name 的索引覆盖，且对索引做了 where 筛选，这里不需要回表。

Extra 为 Using Index Condition 表示会先条件过滤索引，过滤完索引后找到所有符合索引条件的数据行，随后用 WHERE 子句中的其他条件去过滤这些数据行。Index Condition Pushdown (ICP)是 MySQL 5.6 以上版本中的新特性，是一种在存储引擎层使用索引过滤数据的一种优化方式。ICP 开启时的执行计划含有 Using index condition 标示，表示优化器使用了 ICP 对数据访问进行优化。

不考虑 ICP 对数据访问的优化，当关闭 ICP 时，Index 仅仅是 data access 的一种访问方式，存储引擎通过索引回表获取的数据会传递到 MySQL Server 层进行 WHERE 条件过滤。

Extra 为 Using where 只是提醒我们 MySQL 将用 where 子句来过滤结果集。这个一般发生在 MySQL 服务器，而不是存储引擎层。一般发生在不能走索引扫描的情况下或者走索引扫描，但是有些查询条件不在索引当中的情况下。

这里表明没有触发索引覆盖，进行回表查询。

MyISAM

以 MyISAM 存储引擎存储的表不存在聚簇索引。MyISAM 表中的主键索引和非主键索引的结构是一样的。他们的叶子节点是不存储表数据的，节点中存放的是表数据的地址，所以 MyISAM 表可以没有主键。MyISAM 表的数据和索引是分开的，是单独存放的。

MyISAM 表中的主键索引和非主键索引的区别仅在于主键索引 B+tree 上的 key 必须符合主键的限制，非主键索引 B+tree 上的 key 只要符合相应字段的特性就可以了。

主键索引

建立在主键字段上的索引
一张表最多有一个主键索引
索引列值不允许为null
通常在创建表的时候一起创建

唯一索引

建立在 UNIQUE 字段上的索引就是唯一索引
一张表可以有多个唯一索引，索引列值允许为 null

普通索引

建立在普通字段上的索引叫做普通索引，没有主键限制

前缀索引

前缀索引是指对字符串的前几个字符或对二进制类型字段的前几个bytes建立的索引，而不是在整个字段上建索引。
前缀索引可以建立在类型为：char、varchar、binary、verbinary的列上，可以大大减少索引占用的存储空间，也能提升索引的查询效率。

联合索引

联合索引是一个索引结构，这两个条目表示的是组合索引中字段的具体信息，按建立索引时的书写顺序排序。
组合索引的非叶子节点保存了两个字段的值作为 B+tree 的 key 值，当 B+tree 上插入数据时，先按字段 id 比较，在 id 相同的情况下按 name 字段比较。

查看索引命令

1	show index from tableName