MySQL Index

老马啸西风2018年7月30日大约 26 分钟

SQL Index

概念

数据库索引是一种数据结构，它以额外的写入和存储空间来维护索引数据结构为代价，提高了数据库表上数据检索操作的速度。

作用

索引用于快速定位数据，而无需在每次访问数据库表时搜索数据库表中的每一行。可以使用数据库表的一个或多个列创建索引，为快速随机查找和有效访问有序记录提供基础。

索引是从表中选择的数据列的副本，可以非常有效地搜索，还包括一个低级磁盘块地址或到复制的完整数据行的直接链接。有些数据库允许开发人员在函数或表达式上创建索引，从而扩展了索引的功能。

MySQL 索引的使用

索引用于快速查找具有特定列值的行。没有索引，MySQL必须从第一行开始，然后通读整个表以找到相关的行。

table 越大，花费就越多。如果表中有相关列的索引，MySQL可以快速确定要在数据文件中间查找的位置，而无需查看所有数据。这比按顺序读每一行要快得多。

个人经验

唯一主键约束

用来保证数据的唯一性

唯一联合主键约束

和上面功能类似。

提升查询速度

在 WHERE 经常 hit 到的字段，添加索引。

使用场景

以快速找到匹配WHERE子句的行。
从考虑中消除行。如果要在多个索引之间进行选择，MySQL通常使用查找最小行数的索引(最具选择性的索引)。
如果表具有多列索引，那么优化器可以使用索引的任何最左边的前缀来查找行。

例如，如果您对(col1、col2、col3)有三列索引，那么您就对(col1)、(col1、col2)和(col1、col2、col3)有索引搜索功能。

在执行连接时从其他表检索行。

MySQL可以更有效地使用列上的索引，如果它们声明为相同的类型和大小。

在此上下文中，如果将VARCHAR和CHAR声明为相同大小，则认为它们是相同的。例如，VARCHAR(10)和CHAR(10)大小相同，但VARCHAR(10)和CHAR(15)大小不同。

对于非二进制字符串列之间的比较，两列都应该使用相同的字符集。

如果不进行转换就不能直接比较值，那么比较不同的列(例如，将字符串列与时态或数字列进行比较)可能会阻止使用索引。对于数值列中的1这样的给定值，它可能等于字符串列中的任意数量的值，例如“1”、“1”、“00001”或“01.e1”。这就排除了字符串列的任何索引的使用。

查找特定索引列key_col的MIN()或MAX()值。

这是由一个预处理器优化的，它检查您是否使用 WHERE key_part_N = constant 来处理索引中 key_col 之前的所有关键部分。

在本例中，MySQL为每个MIN()或MAX()表达式执行一个键查找，并用常量替换它。如果将所有表达式替换为常量，则查询立即返回。

例如:

SELECT MIN(key_part2),MAX(key_part2)
  FROM tbl_name WHERE key_part1=10;

如果对一个可用索引的最左边的前缀进行排序或分组，则对表进行排序或分组(例如，按key_part1、key_part2排序)。

如果所有关键部件后面都跟着DESC，则按相反顺序读取关键部件。(或者，如果索引是降序索引，则按前进顺序读取键。)

SELECT key_part3 FROM tbl_name
  WHERE key_part1=1

设计思考

为什么设计成树

hash 从速度上来说，不应该是最快的吗？

加速查找速度的数据结构，常见的有两类：

(1)哈希，例如HashMap，查询/插入/修改/删除的平均时间复杂度都是O(1)；

(2)树，例如平衡二叉搜索树，查询/插入/修改/删除的平均时间复杂度都是O(lg(n))；

不管是读请求，还是写请求，哈希类型的索引，都要比树型的索引更快一些，那为什么，索引结构要设计成树型呢？

单行访问

select * from t where name="ryo";

确实是哈希索引更快，因为每次都只查询一条记录。

排序查询

分组：group by

排序：order by

比较：``

哈希型的索引，时间复杂度会退化为O(n)，而树型的“有序”特性，依然能够保持O(log(n)) 的高效率。

为什么是 B+ 树

二叉搜索树

(1)当数据量大的时候，树的高度会比较高，数据量大的时候，查询会比较慢；

(2)每个节点只存储一个记录，可能导致一次查询有很多次磁盘IO；

B 树

它的特点是：

(1)不再是二叉搜索，而是m叉搜索；

(2)叶子节点，非叶子节点，都存储数据；

(3)中序遍历，可以获得所有节点；

B树被作为实现索引的数据结构被创造出来，是因为它能够完美的利用局部性原理。

为何适合做索引

(1)由于是m分叉的，高度能够大大降低；

(2)每个节点可以存储j个记录，如果将节点大小设置为页大小，例如4K，能够充分的利用预读的特性，极大减少磁盘IO；

B+ 树

B+树，如上图，仍是m叉搜索树，在B树的基础上，做了一些改进：

(1)非叶子节点不再存储数据，数据只存储在同一层的叶子节点上；

画外音：B+树中根到每一个节点的路径长度一样，而B树不是这样。

(2)叶子之间，增加了链表，获取所有节点，不再需要中序遍历；

优势

这些改进让B+树比B树有更优的特性：

(1)范围查找，定位min与max之后，中间叶子节点，就是结果集，不用中序回溯；

画外音：范围查询在SQL中用得很多，这是B+树比B树最大的优势。

(2)叶子节点存储实际记录行，记录行相对比较紧密的存储，适合大数据量磁盘存储；非叶子节点存储记录的PK，用于查询加速，适合内存存储；

(3)非叶子节点，不存储实际记录，而只存储记录的KEY的话，那么在相同内存的情况下，B+树能够存储更多索引；

量化对比

最后，量化说下，为什么m叉的B+树比二叉搜索树的高度大大大大降低？

大概计算一下：

(1)局部性原理，将一个节点的大小设为一页，一页4K，假设一个KEY有8字节，一个节点可以存储500个KEY，即j=500

(2)m叉树，大概m/2、>=、` 运算符的相等比较(但速度非常快)。

它们不用于查找值范围的比较运算符(如 explain select * from subject where iid 就表示这个是临时表，后边的N就是执行计划中的id，表示结果来自于这个查询产生。
如果是尖括号括起来的 ，与 类似，也是一个临时表，表示这个结果来自于union查询的id为M,N的结果集。

type

依次从好到差：system，const，eq_ref，ref，fulltext，ref_or_null，unique_subquery，index_subquery，range，index_merge，index，ALL，
除了all之外，其他的type都可以使用到索引，除了index_merge之外，其他的type只可以用到一个索引

A：system：表中只有一行数据或者是空表，且只能用于myisam和memory表。如果是Innodb引擎表，type列在这个情况通常都是all或者index

B：const：使用唯一索引或者主键，返回记录一定是1行记录的等值where条件时，通常type是const。其他数据库也叫做唯一索引扫描

C：eq_ref：出现在要连接过个表的查询计划中，驱动表只返回一行数据，且这行数据是第二个表的主键或者唯一索引，且必须为not null，唯一索引和主键是多列时，只有所有的列都用作比
较时才会出现eq_ref

D：ref：不像eq_ref那样要求连接顺序，也没有主键和唯一索引的要求，只要使用相等条件检索时就可能出现，常见与辅助索引的等值查找。或者多列主键、唯一索引中，使用第一个列之外的
列作为等值查找也会出现，总之，返回数据不唯一的等值查找就可能出现。

E：fulltext：全文索引检索，要注意，全文索引的优先级很高，若全文索引和普通索引同时存在时，mysql不管代价，优先选择使用全文索引

F：ref_or_null：与ref方法类似，只是增加了null值的比较。实际用的不多。

G：unique_subquery：用于where中的in形式子查询，子查询返回不重复值唯一值

H：index_subquery：用于in形式子查询使用到了辅助索引或者in常数列表，子查询可能返回重复值，可以使用索引将子查询去重。

I：range：索引范围扫描，常见于使用>,`

负向条件查询不能使用索引

实例

select * from order where status!=0 and stauts!=1

not in/not exists都不是好习惯

建议优化为：

select * from order where status in(2,3)

在属性上进行计算不能命中索引

select * from order where YEAR(date) < = '2017'

即使date上建立了索引，也会全表扫描，可优化为值计算：

select * from order where date < = CURDATE()

或者：

select * from order where date < = '2017-01-01'

使用聚合函数

表关联的时候。只有当主键和外键具有相同的类型才会生效。

LIKE, REGEX 只有当第一个不是通配符才会生效。

like '%abc'   ×
like 'abc%'   √

ORDER BY

只有当条件不是表达式时会生效。多表的时候效果不好。

相同的字段太多

比如全是 0/1

实例

select * from user where sex=1

性别大部分只有男女，索引效果不佳。

经验上，能过滤80%数据时就可以使用索引。对于订单状态，如果状态值很少，不宜使用索引，如果状态值很多，能够过滤大量数据，则应该建立索引。

拓展知识

局部性原理

局部性原理的逻辑是这样的：

(1)内存读写块，磁盘读写慢，而且慢很多；

(2)磁盘预读：磁盘读写并不是按需读取，而是按页预读，一次会读一页的数据，每次加载更多的数据，如果未来要读取的数据就在这一页中，可以避免未来的磁盘IO，提高效率；

画外音：通常，一页数据是4K。

(3)局部性原理：软件设计要尽量遵循“数据读取集中”与“使用到一个数据，大概率会使用其附近的数据”，这样磁盘预读能充分提高磁盘IO；

非聚集索引

但是如果你没有带着你书上的DDS#来图书馆，那么你需要第二个索引来帮助你。

在过去的日子里，你会在图书馆的前面发现一个奇妙的抽屉柜，被称为“卡片目录”。

里面有成千上万张3x5的卡片——每本书一张，按字母顺序排列(也许是按书名)。这对应于“非聚集索引”。这些卡片目录被组织成一个层次结构，这样每个抽屉都会贴上它所包含的卡片的范围(例如Ka - Kl;即。“中间节点”)。

再一次，你会钻到你找到你的书，但在这种情况下，一旦你找到了它(我。e，“叶节点”)，您没有书本身，但只有一张带有索引号(DDS#)的卡片，您可以用它在聚集索引中找到实际的书。

当然，没有什么能阻止图书管理员复印所有的卡片，并在单独的卡片目录中按照不同的顺序进行分类。(通常至少有两个这样的目录:一个按作者姓名排序，另一个按标题排序。)原则上，您可以拥有任意数量的“非集群”索引。

聚集索引

如果你走进公共图书馆，你会发现所有的书都按照特定的顺序排列(很可能是杜威十进制系统，或DDS)。

这对应于书籍的“聚集索引”。如果您想要的书的DDS#是005.7565 F736s，那么您可以从定位一排标着001-099之类的书架开始。
(堆栈末尾的endcap符号对应于索引中的“中间节点”。)最后，您将深入到标签为005.7450 - 005.7600的特定书架，然后扫描，直到找到指定的DDS#的书，这时您已经找到了您的书。