索引

查找一条数据的过程

先看下InnoDB的逻辑存储结构：

1. 表空间：可以看做是InnoDB存储引擎逻辑结构的最高层，所有的数据都存放在表空间中。默认有个共享表空间ibdata1。如果启用innodb_file_per_table参数，需要注意每张表的表空间内存放的只是数据、索引和插入缓冲Bitmap页，其他类的数据，如回滚信息、插入缓冲索引页、系统事务信息、二次写缓冲等还是存放在原来共享表空间中。

2. 段：
   表空间是由各个段组成，常见的段有数据段、索引段、回滚段等。数据段即为B+树叶子节点(Leaf node segment)，索引段即为B+树非叶子节点(Non-leaf node segment)
   区

3. 区：是由连续页组成的空间，在任何情况下每个区大小都为1MB。默认情况下，存储引擎页的大小为16KB，即一个区中一共有连续64个连续的页。而为保证页的连续性，InnoDB存储引擎一次从磁盘申请4-5个区。

4. 页：
   页(也可以称块)，是InnoDB磁盘管理的最小单位。默认每个页大小16KB。1.2x版本后也可以通过参数innodb_page_size设置为4k、8k、16k

如查一条数据：select * from user where id=5;

这里id是主键,我们通过这棵B+树来查找，首先会去找到根页，每张表的根页位置在表空间文件中是固定的；找到根页后通过二分查找法，定位到id=5的数据应该在指针P5指向的页中，那么进一步去page number=5的页中查找，同样通过二分查询法即可找到id=5的记录：

计算一棵B+树可以存放多少行数据

也可以通过命令查看InnoDB每页默认16KB：

show variables like \’innodb_page_size\’;

先计算非叶子节点， 假设主键ID为bigint类型，长度为8字节，而指针大小在InnoDB源码中设置为6字节，这样一共14字节

而一个页中能存放多少这样的单元，其实就代表有多少指针，即16384/14=1170。

那么可以算出一棵高度为2的B+树，能存放1170*16=18720条这样的数据记录。

根据同样的原理我们可以算出一个高度为3的B+树可以存放：1170117016=21902400条这样的记录。

所以在InnoDB中B+树高度一般为1-3层，它就能满足千万级的数据存储。

索引一些概念

1. 聚簇索引(clustered index): 就是将索引和数据放到一起，找到索引也就找到了数据；如下图叶子节点存放一行所有数据。

2. 辅助索引(Secondary Index或非聚簇索引): 就是将数据和索引分开，查找时需要先查找到索引，然后通过索引回表找到相应的数据。
   回表：先通过数据库索引扫描出数据所在的行，再通过行主键id取出索引中未提供的数据，即基于非主键索引的查询需要多扫描一棵索引树。

如下图，辅助索引查找后，会再回表到聚簇索引，最后找到数据。

InnoDB有且只有一个聚簇索引，而MyISAM中都是非聚簇索引。

3. 联合索引：指对表上多个列进行索引。

联合索引的最左前缀匹配原则： 对多个字段同时建立的组合索引(有顺序，ABC，ACB是完全不同的两种联合索引) 以联合索引(a,b,c)为例，建立这样的索引相当于建立了索引a、ab、abc三个索引。另外组合索引实际还是一个索引，并非真的创建了多个索引，只是产生的效果等价于产生多个索引。

4. 覆盖索引: 即从辅助索引中就可以得到查询的记录，而不需要查询聚簇索引中的记录。

使用覆盖好处：

• 辅助索引不包含整行记录的所有信息，故其大小要远小于聚簇索引，减少大量IO操作。
• 对某些统计(如count(id))并不会通过查询聚簇索引来进行统计，减少IO操作

5. 唯一索引：以唯一列生成的索引，该列不允许有重复值，但允许有空值(NULL)

6. 索引下推：MySQL 5.6引入了索引下推优化，可以在索引遍历过程中，对索引中包含的字段先做判断，过滤掉不符合条件的记录，减少回表字数。

为什么选B+树，而不是B树

B树不管叶子节点还是非叶子节点，都会保存数据，这样导致在非叶子节点中能保存的指针数量变少

指针少的情况下要保存大量数据，只能增加树的高度，导致IO操作变多，查询性能变低；

为什么InnoDB只有一个聚簇索引，而不将所有索引都使用聚簇索引？

因为聚簇索引是将索引和数据都存放在叶子节点中，如果所有的索引都用聚簇索引，则每一个索引都将保存一份数据，会造成数据的冗余，在数据量很大的情况下，这种数据冗余是很消耗资源的。

什么情况下会发生明明创建了索引，但是执行的时候并没有通过索引呢？

查询优化器。

一条SQL语句的查询，可以有不同的执行方案，至于最终选择哪种方案，需要通过优化器进行选择，选择执行成本最低的方案。

优化过程大致如下：

• 1、根据搜索条件，找出所有可能使用的索引
• 2、计算全表扫描的代价
• 3、计算使用不同索引执行查询的代价
• 4、对比各种执行方案的代价，找出成本最低的那一个 。

索引的优缺点

索引的优点如下：

• 1、唯一索引可以保证每一行数据的唯一性
• 2、提高查询速度
• 3、加速表与表的连接
• 4、显著的减少查询中分组和排序的时间
• 5、通过使用索引，可以在查询的过程中，使用优化隐藏器，提高系统的性能。

索引的缺点如下：

• 创建索引时，需要对表加锁，在锁表的同时，可能会影响到其他的数据操作
• 虽然索引大大提高了查询速度，同时却会降低更新表的速度，如对表进行 INSERT、UPDATE 和 DELETE。因为更新表时，MySQL 不仅要保存数据，还要保存索引文件。
• 建立索引会占用磁盘空间的索引文件。一般情况这个问题不算严重，但如果你在一个大表上创建了多种组合索引，且伴随大量数据量插入，索引文件大小也会快速膨胀。
• 如果某个数据列包含许多重复的内容，为它建立索引就没有太大的实际效果。
• 对于非常小的表，大部分情况下简单的全表扫描更高效。

使用索引时的注意事项

原则：
不应该

1、索引不是越多越好。索引太多，维护索引需要时间跟空间
2、 频繁更新的数据，不宜建索引。
3、数据量小的表没必要建立索引。

应该

1、重复率小的列建议生成索引。因为重复数据少，索引树查询更有效率，等价基数越大越好。
2、数据具有唯一性，建议生成唯一性索引。在数据库的层面，保证数据正确性
3、频繁group by、order by的列建议生成索引。可以大幅提高分组和排序效率
4、经常用于查询条件的字段建议生成索引。通过索引查询，速度更快

索引失效的场景

1、模糊搜索：左模糊或全模糊都会导致索引失效，比如\’%a\’和\’%a%\’。但是右模糊是可以利用索引的，比如\’a%\’
2、隐式类型转换：比如select * from t where name = xxx , name是字符串类型，但是没有加引号，所以是由MySQL隐式转换的，所以会让索引失效
3、当语句中带有or的时候：比如select * from t where name=‘sw’ or age=14
4、不符合联合索引的最左前缀匹配：(A,B,C)的联合索引，你只where了C或B或只有B,C

其他注意事项：

1. 索引不会包含有 null 值的列，只要列中包含有 null值都将不会被包含在索引中。
2. 使用短索引。短索引不仅可以提高查询速度而且可以节省磁盘空间和 I/O 操作
3. 索引列排序。查询只使用一个索引，因此如果 where 子句中已经使用了索引的话，那么 order by 中的列是不会使用索引的。因此数据库默认排序可以符合要求的情况下不要使用排序操作；尽量不要包含多个列的排序，如果需要最好给这些列创建复合索引。
4. 不要在列上进行运算，这将导致索引失效而进行全表扫描
5. 不使用 not in 和 <> 操作，这不属于支持的范围查询条件，不会使用索引。

《MySQL技术内幕》
https://mp.weixin.qq.com/s/6j64s9W6ogs5Y8BbhhkgnA
https://mp.weixin.qq.com/s/KB73550tKpNccW-WKxT7-A
https://mp.weixin.qq.com/s/ovMx9Dv9NCFxSsFM98uYFw