MySQL-索引

B+ Tree

B Tree 指的是 Balance Tree，也就是平衡树，平衡树是一颗查找树，并且所有叶子节点位于同一层

B+ Tree 是 B 树的一种变形，它是基于 B Tree 和叶子节点顺序访问指针进行实现，通常用于数据库和操作系统的文件系统中。

B+ 树有两种类型的节点：内部节点（也称索引节点）和叶子节点，内部节点就是非叶子节点，内部节点不存储数据，只存储索引，数据都存在叶子节点。

内部节点中的 key 都按照从小到大的顺序排列，对于内部节点中的一个 key，左子树中的所有 key 都小于它，右子树中的 key 都大于等于它，叶子节点的记录也是按照从小到大排列的。每个叶子节点都存有相邻叶子节点的指针。

B + 树与 B 树的比较

B+ 树的磁盘 IO 更低

B+ 树的内部节点并没有指向关键字具体信息的指针。因此其内部节点相对 B 树更小。如果把所有同一内部结点的关键字存放在同一盘块中，那么盘块所能容纳的关键字数量也越多。一次性读入内存中的需要查找的关键字也就越多。相对来说IO读写次数也就降低了。

B+ 树的查询效率更加稳定

由于非叶子结点并不是最终指向文件内容的结点，而只是叶子结点中关键字的索引。所以任何关键字的查找必须走一条从根结点到叶子结点的路。所有关键字查询的路径长度相同，导致每一个数据的查询效率相当。

B+ 树元素遍历效率高

B 树在提高了磁盘IO性能的同时并没有解决元素遍历的效率低下的问题。正是为了解决这个问题，B+树应运而生。B+树只要遍历叶子节点就可以实现整棵树的遍历。而且在数据库中基于范围的查询是非常频繁的，而 B 树不支持这样的操作（或者说效率太低）。

操作
B+树的查找	查找以典型的方式进行，类似于二叉查找树。起始于根节点，自顶向下遍历树，选择其分离值在要查找值的任意一边的子指针。在节点内部典型的使用是二分查找来确定这个位置。
B+树的插入	二叉树插入
B+树的删除	类似插入，只不过是自下而上的合并操作

索引

索引（index）是帮助sql 高效获取数据的有序数据结构。在数据之外，数据库系统还维护着满足特定查找算法的数据结构，这些数据结构以某种方式引用（指向）数据，这样就可以在这些数据结构上实现高级查找算法，这种数据结构就是索引。

语法
创建索引	CREATE [UNIQUE | FULLTEXT] INDEX index_name ON table_name (col0,col1,...);
查看索引	SHOW INDEX FROM table_name;
删除索引	DROP INDEX index_name ON table_name;

优点	缺点
提高数据库检索的效率，降低数据库的IO成本	索引列也是需要占用空间的
通过索引列对数据进行排序，降低数据排序的成本，降低CPU的消耗。	索引大大提高了查询效率，同时也降低更新表的速度，如果对表进行INSERT，UPDATE，DELETE时，效率降低

sql 的索引实在存储引擎层实现的，不同的存储引擎有不同的结构，主要包含以下几种：

索引结构	描述
B+Tree索引	最常见的索引类型，大部分引擎都支持B+树索引
Hash索引	底层数据结构是hash表实现的，只有精确匹配索引列的查询才有效，不支持范围查询
R-Tree(空间索引)	空间索引是MyISAM 引擎的一个特殊索引类型，主要用于地理空间数据类型，通常使用较少
Full-Text(全文索引)	是一种通过建立倒排索引，快速匹配文档的方式。类似于Lucene，Solr，ES

索引	InnoDB	MyISAM	Memory
B+Tree 索引	支持	支持	支持
Hash 索引	不支持	不支持	支持
R-Tree 索引	不支持	支持	不支持
Full-text	5.6版本之后支持	支持	不支持

B+Tree 索引

InnoDB 的 B+Tree 索引分为主索引和辅助索引。

聚簇索引

主索引的叶子节点 data 域记录着完整的数据记录，这种索引方式被称为聚簇索引。

因为无法把数据行存放在两个不同的地方，所以一个表只能有一个聚簇索引。

每个InnoDB表都有一个聚簇索引 ，聚簇索引使用B+树构建，叶子节点存储的数据是整行记录。一般情况下，聚簇索引等同于主键索引，当一个表没有创建主键索引时，InnoDB会自动创建一个ROWID字段来构建聚簇索引。InnoDB创建索引的具体规则如下：

1. 在表上定义主键PRIMARY KEY，InnoDB将主键索引用作聚簇索引。
2. 如果表没有定义主键，InnoDB会选择第一个不为NULL的唯一索引列用作聚簇索引。
3. 如果以上两个都没有，InnoDB 会使用一个6 字节长整型的隐式字段 ROWID字段构建聚簇索引。该ROWID字段会在插入新行时自动递增。

非聚簇索引

InnoDB辅助索引中的叶子节点存储的数据是该行的主键值。在检索时，InnoDB使用此主键值在聚簇索引中搜索行记录。

因此在使用辅助索引进行查找时，需要先查找到主键值，然后再到主索引中进行查找，这个过程也被称作回表

哈希索引

哈希索引能以 O(1) 时间进行查找，但是失去了有序性：

• 无法用于排序与分组；
• 只支持精确查找，无法用于部分查找和范围查找。

InnoDB 存储引擎有一个特殊的功能叫“自适应哈希索引”，当某个索引值被使用的非常频繁时，会在 B+Tree 索引之上再创建一个哈希索引，这样就让 B+Tree 索引具有哈希索引的一些优点，比如快速的哈希查找。

全文索引

MyISAM 存储引擎支持全文索引，用于查找文本中的关键词，而不是直接比较是否相等。

查找条件使用 MATCH AGAINST，而不是普通的 WHERE。

全文索引使用倒排索引实现，它记录着关键词到其所在文档的映射。

InnoDB 存储引擎在 sql 5.6.4 版本中也开始支持全文索引。

只能在文本类型CHAR,VARCHAR,TEXT类型字段上创建全文索引。字段长度比较大时，如果创建普通索引，在进行like模糊查询时效率比较低，这时可以创建全文索引。

空间数据索引

MyISAM 5.7之后存储引擎支持空间数据索引（R-Tree），可以用于地理数据存储。

空间数据索引从所有维度来索引数据，可以有效地使用任意维度来进行组合查询。

• 必须使用 GIS 相关的函数来维护数据。

索引失效场景

• 当我们使用左或者左右模糊匹配的时候，也就是 like %xx 或者 like %xx% 这两种方式都会造成索引失效；
• 当我们在查询条件中对索引列使用函数，就会导致索引失效。
• 当我们在查询条件中对索引列进行表达式计算，也是无法走索引的。
• sql 在遇到字符串和数字比较的时候，会自动把字符串转为数字，然后再进行比较。如果字符串是索引列，而条件语句中的输入参数是数字的话，那么索引列会发生隐式类型转换，由于隐式类型转换是通过 CAST 函数实现的，等同于对索引列使用了函数，所以就会导致索引失效。
• 联合索引要能正确使用需要遵循最左匹配原则，也就是按照最左优先的方式进行索引的匹配，否则就会导致索引失效。
• 在 WHERE 子句中，如果在 OR 前的条件列是索引列，而在 OR 后的条件列不是索引列，那么索引会失效。

索引设计原则

1. 针对于数据量比较大，查询比较频繁的表
2. 针对于常作为查询条件，排序，分组操作的字段建立索引。
3. 尽量选择分区度高的列作为索引，尽量做唯一索引，区分度越高，效率越高。
4. 如果是字符串且字符串长度较长，可以针对字段的特点，建立前缀索引。
5. 尽量使用联合索引，减少单列索引，查询时联合索引喝多时候可以覆盖索引，节省存储空间避免回表。
6. 索引越多，维护表结构的代价越大，影响增删改的效率。
7. 如果所有列不能为空时，创建表时使用NOT NULL约束，当优化器知道每列包含NULL 值时，可以更好的确定哪个索引最有效地用于查询。

索引优化细则

多列索引

在需要使用多个列作为条件进行查询时，使用多列索引比使用多个单列索引性能更好

索引列顺序

让选择性最强的索引列放在前面。

索引的选择性是指：不重复的索引值和记录总数的比值。最大值为 1，此时每个记录都有唯一的索引与其对应。

选择性越高，每个记录的区分度越高，查询效率也越高

前缀索引

表结构当中经常会出现文本类型的字段，当字段类型为字符串（varchar,text）时，有时候需要索引很长的字符串，这会让索引变得很大，查询时浪费大量的磁盘IO，影响查询效率，此时可以将字符串的一部分前缀建立索引，这样可以大大节约索引空间，从而提高索引效率。

create index idx_xxx on table (column(N));

前缀长度

可以根据索引的选择性来决定，而选择性是指不重复的索引值（基数）和表记录的总数的比值，索引选择性越高，查询效率越高。唯一索引的选择性是1，这是做好的索引选择性，性能也是最好的。

-- 查询截取前N个字符的不重复的记录 / 所有记录树 为该字段的选择性
SELECT count(DISTINCT(substring(NAME, 1, N ))) / count(*) FROM TABLE

对于 BLOB、TEXT 和 VARCHAR 类型的列，必须使用前缀索引，只索引开始的部分字符。

前缀长度的选取需要根据索引选择性来确定。

覆盖索引

使用覆盖索引（查询使用了索引，并且需要返回的列，在该索引已经全部能够找到），减少select * 。

在Explain SQL时关注Extra 列出现using index condition或者NULL 说明查找使用了索引，但是需要回表查询数据。

using where;using index说明查找使用了索引，但是需要的数据都在索引列种能够找到，所以不需要回表查询。

当查询的字段不在索引种能够找到，从而查询聚集索引拿到数据，这样的操作称作回表。

索引包含所有需要查询的字段的值。

具有以下优点：

• 索引通常远小于数据行的大小，只读取索引能大大减少数据访问量。
• 一些存储引擎（例如 MyISAM）在内存中只缓存索引，而数据依赖于操作系统来缓存。因此，只访问索引可以不使用系统调用（通常比较费时）。
• 对于 InnoDB 引擎，若辅助索引能够覆盖查询，则无需访问主索引。

索引下推(ICP)

执行查询explain看见Extra中显示了Using index condition，表示出现了索引下推(代表可以使用，但是不一定真实使用)

某种场景下ICP通过联合索引中本来就有的数据直接过滤，不需要再查到一堆无用的数据去Server层进行过滤，这样的话减少了回表的次数和返回的数据，IO次数减少了，对性能有很好的提升。

1. 首先，ICP适用于range、ref、eq_ref和ref_or_null的场景下
2. InnoDB和MyISAM都支持ICP，sql partition分表的话也可以使用
3. 对于InndoDB而言，ICP只支持二级索引，因为主键索引它用不上
4. 子查询不支持

sql5.6以上的版本，默认就是开启ICP

关闭命令SET optimizer_switch = 'index_condition_pushdown=off';

SQL 提示

SQL提示是优化数据库的一个重要手段，简单来说，在SQL语句种加入一些人为的提示来达到优化操作的目的。比如： 一个联合索引（name,id_card,status）和普通索引（name）到底用哪个索引呢？

use index

-- 使用某个索引
explain select * from emp use index(idx_name_gen_add) where name = '韦一笑'

ignore index

-- 忽略某个索引
explain select * from emp ignore index(idx_name_gen_add) where name = '韦一笑'

force index

-- 强制使用某个索引
explain select * from emp force index(idx_name_gen_add) where name = '韦一笑'

索引选择性分析

通过如下 SQL 得到全列选择性：

SELECT COUNT(DISTINCT column_name) / COUNT(*) FROM table_name;

通过如下 SQL 得到某一长度前缀的选择性：

SELECT COUNT(DISTINCT LEFT(column_name, prefix_length)) / COUNT(*) FROM table_name;

总结

• 主键索引名为 pk_字段名；唯一索引名为 uk_字段名；普通索引名则为 idx_字段名。
• 数据量超过 300 的表应该有索引。
• 经常与其他表进行连接的表，在连接字段上应该建立索引。
• 经常出现在 WHERE 子句中的字段，特别是大表的字段，应该建立索引。
• 索引应该建在选择性高的字段上。
• 索引应该建在小字段上，对于大的文本字段甚至超长字段，不要建索引。
• 复合索引的建立需要进行仔细分析，尽量考虑用单字段索引代替。
• 正确选择复合索引中的主列字段，一般是选择性较好的字段。
• 经常同时以 AND 方式出现在 WHERE 子句中，则可以建立复合索引；否则考虑单字段索引。
• 如果复合索引中包含的字段经常单独出现在 WHERE 子句中，则分解为多个单字段索引。
• 如果复合索引所包含的字段超过 3 个，那么仔细考虑其必要性，考虑减少复合的字段。
• 如果既有单字段索引，又有这几个字段上的复合索引，一般可以删除复合索引。
• 频繁进行数据操作的表，不要建立太多的索引。
• 删除无用的索引，避免对执行计划造成负面影响。
• 表上建立的每个索引都会增加存储开销，索引对于插入、删除、更新操作也会增加处理上的开销。
• 尽量不要对数据库中某个含有大量重复的值的字段建立索引。

References

• MySQL全文索引和中文场景的应用
• mysql8全文检索应用之二：Mybatis-Plus