1. 索引
1.1. 二叉索引
B+tree是由二叉树》平衡二叉树》B-tree演化而来。
二叉树每个节点最多两个子节点，左子树键值永远小于右子树，并小于根键值。
1.2. 平衡二叉树结构
平衡二叉树在二叉树结构基础上提高，必须满足左右两个子树的高度差的绝对值不超过1，且左子树和右子树都是一颗平衡二叉树，，随时要保证插入后的整棵二叉树是平衡的，通郭左旋或右旋使不平衡的树变平衡。
1.3. B-tree结构
B-tree又称Btree，每个节点最多4个子节点，除了根节点和叶子节点，其他节点最少2个子节点。所有叶子节点在同一层，叶子节点不包括任何关键字信息。
1.4. B+tree
B+tree使Btree的变体，是一种多路搜索树，所有关键字和数据都保存在叶子节点中，并且包含关键字记录的指针。
总结：B+tree索引是双向链表结构，检索比B-tree快，访问关键字的顺序是连续性的，不用再访问上一个节点，且叶子节点包含所有的数据信息。
1.4.1. 聚集索引和普通索引
B+tree分为两大类，一类叫聚集索引，一类叫非聚集索引（普通索引）。
InnoDB存储引擎是索引组织表，聚集索引是一种索引组织表形式，索引键值的逻辑顺序决定了表数据行的物理存储顺序。
聚集索引叶子节点存放表中所有行数据记录的信息，即数据即索引、索引即数据。创建表时建主键（聚集索引），如不建主键则InnoDB会选择第一个不包含由Null值得唯一索引作为主键，如果唯一索引没有，则默认为该表生成一个6字节得rowid为主键。
普通索引在叶子节点不包含所有行得数据记录，只在叶子节点存有自己本身键值和主键得值。检索数据，通过普通索引叶子节点上主键来获取想要查找的行数据记录。
普通索创建语法：
alter table tab_name add index index_name(col1);
或：
create index inde_name on tab_name(col1);
查看表中有哪些索引；
show index from tab_name;
索引创建实验
l 创建测试库
mysql> create database test;
l 创建测试表
DROP TABLE IF EXISTS `t`;
CREATE TABLE `t` (
`id` int(11) NOT NULL AUTO_INCREMENT,
`name` varchar(20) NOT NULL,
`address` varchar(20) NOT NULL,
PRIMARY KEY (`id`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4;
l 查看表结构
[test]>desc t;
+---------+-------------+------+-----+---------+----------------+
| Field | Type | Null | Key | Default | Extra |
+---------+-------------+------+-----+---------+----------------+
| id | int(11) | NO | PRI | NULL | auto_increment |
| name | varchar(20) | NO | | NULL | |
| address | varchar(20) | NO | | NULL | |
+---------+-------------+------+-----+---------+----------------+
l 创建存储过程
DELIMITER $$
DROP PROCEDURE IF EXISTS `proc_auto_insertdata`$$
CREATE PROCEDURE `proc_auto_insertdata`()
BEGIN
DECLARE init_data INTEGER DEFAULT 1;
WHILE init_data <= 60000 DO
INSERT INTO test.t VALUES(CONCAT('name', init_data), init_data + 10);
SET init_data = init_data + 1;
END WHILE;
END$$
DELIMITER ;
l 调用存储过程插入数据
CALL proc_auto_insertdata();
数据插入完成，看数据文件10M
l 查看执行计划
test> explain select * from t where name='name11';
l 创建索引
create index idx_tname on t(name);
l 再次查看执行计划
优化方法
l 执行计划查看方法：
1. 看查询类型type，如出现all，代表全表扫描；
2. 看key列，看是否使用l 索引。null表示没有使用索引；
3. 看rows列，SQL执行过程中被扫描的行数；
4. 看extra列，观察是否有Using filesort或Using temporary，这些影响性能。
5. 看filtered列，（5.7增加，5.6用explain extended增加此列），代表返回结果的行占需要读取行的百分比。
l SQL优化思路：
1. 查看表的数据类型是否设计的合理，是否遵守选区数据类型越简单越小的原则。
2. 表中碎片是否整理。
3. 表的统计信息是否收集。
4. 查看执行计划如没用到索引，需创建。
5. 创建索引前，查看索引的选择性，判断字段是否合适创建索引。选择性指不重复的索引值（基数，cardinality）和记录总数的比值，比值越高越好。
6. 创建索引后，再看执行计划，比对前后。
l 合理创建索引：
1. 经常被查询的列。
2. 经常用于表连接的列。
3. 经常排序分组的类。
1.4.2. ICP、MRR和BKA
ICP(Index Condition Pushdown) 是mysql使用索引从表重检索行数据的一种优化方式。5.6开始支持。之前存储引擎取所有数据给server使用索引过滤处理。使用ICP之后，可以使用索引的话，存储引擎过滤完数据再给server层。ICP能减少引擎层访问基表的次数和server层访问存储引擎的次数。
通过optimizer_switch参数中的index_condition_pushdow来控制，默认开启。
[mysql]>show variables like '%pushdown%';
关闭：
set optimizer_switch=”index_condition_pushdown=on|off”;
使用ICP优化时，执行计划extra列会显示Using index condition。
5.7中optimizer_switch参数默认值：
|index_merge=on,index_merge_union=on,index_merge_sort_union=on,index_merge_intersection=on,engine_condition_pushdown=on,index_condition_pushdown=on,mrr=on,mrr_cost_based=on,block_nested_loop=on,batched_key_access=off,materialization=on,semijoin=on,loosescan=on,firstmatch=on,duplicateweedout=on,subquery_materialization_cost_based=on,use_index_extensions=on,condition_fanout_filter=on,derived_merge=on |
MBR(Multi-Range Read Optimization) ,5.6后增加。通过optimizer_switch参数中两个选项控制，参数默认开启。
mrr_cost_basd：通过基于成本的算法来确定开启mrr特性，on自动，off强制开启。
MBR作用：把普通索引上的叶子节点上找到的主键值的集合存储到read_rnd_buffer中，然后再该buffer中对主键值排序，然后用排序号的主键值集合去访问表中的数据，将随机IO编程顺序IO，降低查询过程IO开销。
使用MBR优化时，执行计划extra列会显示Using MBR。
BKA（Batched Key Access）,提高表join性能的算法，作用是读取被join表的记录时候使用顺序IO。
BKA原理：多表join语句，使用索引访问第二个join表时，使用一个join buffer来收集第一个操作对象生成的相关列值，BKA构建好key后，批量传给引擎层做索引查找，key通过MBR接口提交给引擎。
通过optimizer_switch参数的batched_key_access选项控制，默认关闭。
要开启该参数，必须强制使用MBR才行。
SET global optimizer_switch=’mrr=on,mrr_cost_based=off’;
SET global optimizer_switch=’batched_key_access=on’;
当BKA使用时，执行计划extra列会显示Using join buffer(Batched Key Access)。
1.4.3. 主键索引和唯一索引
主键索引就是聚集索引，每表只能有一个。必须满足三个条件：
l 主键值必须唯一。
l 不能包含null值。
l 一定要保证该值是自增属性。可以保证写入数据的顺序也是自增的，提高存取效率。
创建主键语法：
alter table tab_name add primary key(col);
唯一索引，不允许有重复值，但允许空值，可以有多个唯一索引。
语法：
alter table tab_name add unique(col);
1.4.4. 覆盖索引
数据在索引中，查到索引不必再回表查询数据。执行计划extra列中会出现Using index。
如使用覆盖索引，一定要让select列出所需要的列，坚决不能直接写出select *
1.4.5. 前缀索引
对于BLOB、TEXT或很长的varchar类型的列，为他们前几个字符建立的索引，就是前缀索引。不能再ORDER BY 或GROUP BY中使用前缀索引，也不能用作覆盖索引。
alter table tab_name add key(col_name(prefix_length));
注意：最关键的参数prefix_length，这个值需要根据实际表的内容来得到合适的索引选择性。
1.4.6. 联合索引
联合索引又叫复合索引，是表中两个或两个以上的列创建的索引。
create index idx_c1_c2 on t(c1,c2);
选择性高的列放前面。
1.5. 哈希索引
哈希索引采用哈希算法，把键值换算成新的哈希值。哈希索引只能进行等值查询，不能进行排序、模糊查找、范围查询等。检索时不需要像B+tree那样从根节点到叶子节点逐级查找，只需一次哈希算法即可立即定位到相应的位置。
1.6. 索引总结
索引优点
l 提高数据检索效率
l 提高据合函数效率
l 提高排序效率
l 使用覆盖索引可以避免回表
索引创建四个不要
l 选择性低的字段不要创建索引
l 很少查询的列不要创建索引
l 大数据类型字段不要创建索引
l 尽量避免不要使用NULL，应指定列为NOT NULL。
使用不到索引的情况
l 通过索引扫描的行记录数超过全表30%，优化器不会走索引，而走全表扫描。
l 联合索引中，第一个查询条件不是最左侧列。
l 联合索引中，第一个索引列使用范围查询，只能使用到部分索引，有ICP出现。
l 联合索引中，第一个查询条件不是最左前缀列。
l 模糊查询条件列最左以通配符%开始。
l 两个单列索引，一个用于检索，一个用户排序。只能使用到一个索引，因为查询语句最多只能使用一个索引，考虑建立联合索引。
l 查询字段上有索引，但使用了函数运算。
