在海量数据中查询某一条数据很常见，可以提高效率

数据库存储在磁盘中，每一次数据库查询就是一次IO操作，一次查询出4KB的数据，如果没有查到就继续轮询。
创建索引就是创建目录，相当于指明数据在磁盘中的位置,索引使用B+树

(1) 主键索引：主键自带索引效果，也就意味着通过主键来查询表中的记录，性能是非常好的
(2) 普通索引：为普通列创建的索引
创建索引的命令：
create index 索引名称 on 表名（列名）
(3) 唯一索引：就像是唯一列，列中的数据是唯一的，比普通索引的性能要好
命令：
create unique index 索引名称 on 表名(列名)
(4) 联合索引（组合索引）：一次性为表中的多个字段一起创建索引，最左前缀法制，注意：一个联合索引建议不要超过5个列
命令
create index 索引名称 on 表(列1,列2,...)
(5) 全文索引
进行查询的时候，数据源可能来自于不同的字段或者不同的表，MyISAM存储引擎支持全文索引。在实际生产环境中，并不会使用MySQL提供的MyISAM存储引擎的全文索引功能来实现全文查找，而是会使用第三方的中间件，比如ElasticSearch、solr

（1）线性顺序表：相邻两个数据的逻辑关系和物理位置是相同的
（2）线性链式表：相邻两个数据的逻辑关系和物理存放位置没有关系，数据有先后的逻辑关系，但是数据的物理存储位置并不连续。
单向链式表：能够通过当前结点找到下一个结点的位置，以此来维护链表的逻辑关系，结点结构：数据内容+下一个数据的指针
（3）双向链式表：能够通过当前结点找到上一个结点和下一个结点，结点结构：数据内容+上一个数据的指针+下一个数据的指针
（4）顺序表和链式表的区别：
数组：进行数据的查询性能（可以通过数组的索引/下标，数组的查询性能很好，时间复杂度：O(1) ，数组的增删性能非常差
链表：查询的性能差增删性能好

(1) 栈：先进后出，有顺序栈、链式栈
(2) 队列：先进先出，有顺序队列、链式队列
(3) 串：String定长串、StringBuffer/Stringbuilder动态串
(4) 广义表：更加灵活的多维数组，可以在不同的元素中创建不同维度的数组

一个结点最多只有两个子结点
二叉查找树：二叉树的根节点的数值比所有左子树的结点的数值大，比右子树的结点的数值小，这样的规律满足于他的所有子树

左子树和右子树的深度差不能超过1，二叉树中每棵子树都要求是平衡二叉树
如果平衡二叉树不满足这个点，二叉树会旋转。

在自旋造成的系统开销和减少查询次数之间做了权衡，因此红黑树有时候并不是一颗平衡二叉树

红黑树在每一层上存放的数据内容是有限的，导致数据量一大，树的深度就变得非常大，于是查询非常差，因此索引没有使用红黑树。

B树允许一个结点存放多个数据，这样可以使更小的树的深度来存放更多的数据

通过计算，B树一个结点可以存储15个数据，不能满足存储海量数据的要求

B+树的特点
非叶子结点冗余了叶子结点的数据
叶子结点是从小到大、从左到右排列的
叶子结点之间提供了指针，提高了区间访问的性能
只有叶子结点存放数据，非叶子节点不存放数据，只存放键

使用哈希表来存取数据的性能是最快的，O(1)，但是不支持范围查找，因为哈希表的数据不连续

InnoDB和MyISAM都是MySQL的搜索引擎
索引在MyISAM中存储在两个文件中：.MYI存放索引的键，.MYD存放数据。 .MYI存放数据的地址，找到地址后，进行一次IO操作才能拿到数据
索引在InnoDB中存储在.ibd：索引和数据存储在一个文件里，通过找到索引后就能直接在索引树的叶子结点上获得完整数据

在使用一个索引来实现多个表中字段的索引效果

最左前缀法则是表示一条sql语句在联合索引中有没有走索引（命中索引/不会全表扫描）

#创建联合索引
create index idx_a_b_c on table(a,b,c);
#sql语句有没有命中索引
select * from table1 where a =10;  #走a的索引
select * from table1 where a = 10 and b =20;  #走（a,b)的索引
select * from table1 where a = 10 and b = 30 and c =30;  #走(a,b,c)的索引
select * from table1 where b = 10;  #不走索引
select * from table1 where b = 10 and c = 30;  #不走索引
select * from table1 where a = 10 and c = 30;  #走a的所有
select * from table1 where c = 30;  #不走索引
select * from table1 where a = 10 and c = 30 and b = 20; # (a,b,c)全走，mysql有一个内部优化器，会做一次内部优化

SQL优化的目的是为了SQL语句能够具备优秀的查询性能，途径：
（1）工程优化：数据库标准、表的结构标准、字段的标准、创建索引
（2）SQL语句的优化：当前SQL语句有没有命中索引

参考数据库设计规范

首先得知道当前系统里有哪些SQL是慢SQL(查询性能超过1s的sql),然后再通过Explain工具可以对当前SQL语句的性能进行判断
要知道哪些SQL是慢SQL,有两种方式，一种是开启本地MySQL的慢查询日志，另一种是阿里云提供的RDS(第三方部署的MySQL服务器)，提供了查询慢SQL的功能
通过在SQL语句前面加上Explain关键来执行，就可以看出当前SQL语句的执行性能
explain SELECT * from employees where name like "customer100%"并不会真正地执行，而是通过explain工具来分析这条语句执行的性能

在SQL查询开始之前，MySQL的内部优化器会进行一次自我优化，让这一次的查询性能尽可能好

关闭MySQL对衍生表的合并优化：
set session optimizer_switch='derived_merge=off'
该列描述查询的类型
simple： 不包含子查询的简单查询
primary：外部的主查询
derived: 在from后面进行的子查询，会产生衍生表
subquery: 在from的前面进行的子查询
union：使用union的联合查询

这一列表示sql正在访问哪一张表，也可以看出正在访问的衍生表

type列可以直观的判断出当前sql语句的性能。type里的取值和性能的优劣顺序如下：
null > system > const > eq_ref > ref > range > index > all
对于SQL优化来说，要尽量保证type列的值是属于range及以上级别
（1）null：性能是最好的，一般在使用了聚合函数操作索引列，结果直接从索引获取即可，因此是性能最好的
system：很少见，直接和一条记录进行匹配
（2）const: 使用主键索引或唯一索引和常量进行比较，这种性能比较好
eq_ref: 在进行多表连接查询时，如果查询条件是使用了主键进行比较，那么当前查询类型是eq_ref
（3）ref：i.简单查询：explain select * from tb_book where name='book1'
如果查询列是普通列索引，那么查询类型是ref
ii.复杂查询：explain select book_id from tb_book left join tb_book_author on tb_book.id = tb_book_author_book_id
如果查询条件是普通列索引，那么类型是ref
（4）range：在索引列上使用范围查找，性能是ok的
explain select * from tb_author where id > 1
（5）index: 在查询表中的所有记录，但是所有的记录可以直接从索引树上获取，因此这种sql的查询类型就是index

（6）ALL: 全表扫描，就是从头到尾对数据扫描一遍

在多个select中，id越大越先执行，id相同谁在上面谁先执行

这一次的查询中可能用到的索引。mysql的内部优化器会进行判断，如果这一次查询走索引的性能比全表扫描的性能要差，那么内部优化器就会让此次查询进行全表扫描，这样的判断依据可以通过trace工具来查看

实际该sql语句使用的索引

可能查询出的条数

键的长度，通过这一列可以让我们知道当前命中了联合索引中的哪几列

计算规则：

提供一些额外信息，帮助我们判断当前sql是否使用覆盖索引、文件排序、使用索引进行查询条件等
（1）Using index：使用了覆盖索引，也就是说当前查询的所有数据字段都是索引列，这就意味着可以直接从索引列中获取数据，不用进行查表
（2）Using where：where的条件没有使用索引列，这种性能是不OK的，如果条件允许可以给列设置索引，也同样尽可能的使用覆盖索引
（3）Using index condition：查询的列没有完全被索引覆盖，并且where条件中使用普通索引
（4）Using temporary：创建临时表来查询，比如在非索引列上进行去重操作
（5）Using filesort：对数据进行排序，使用文件排序：会使用磁盘+内存的方式进行文件排序，会涉及两个概念：单路排序、双路排序
（6）select tables optimized away：直接在索引列上进行聚合函数的操作

（1）不能在索引上做计算、函数、类型转换
（2）日期查找如何处理：转换成范围查找
（3）尽量使用覆盖索引：不使用*
（4）使用不等于（!= 或者 <>）会导致全表扫描：在业务层面进行处理
（5）使用is null、is not null会导致全表扫描
（6）使用like以通配符开头（%abc…）会导致全表扫描：用搜索引擎处理
（7）字符串不加单引号会导致全表扫描
（8）少用or或in，MySQL内部优化器可能不走索引：select * from employees where name in (100000条数据) 解决方案：对100000条数据进行拆分，一次查1000条，要进行100次的查询，使用多线程然后将结果整合。
（9）范围查询优化：例如

优化成：

explain select * from employees where age >= 1 and age <= 1000;
explain select * from employees where age >= 1001 and age <= 2000;

在执行计划中我们发现有的sql会走索引，有的sql即使明确使用了索引也不会走索引，这是因为mysql的内部优化器任务走索引的性能比不走索引全表扫描的性能要差，因此mysql内部使用了全表扫描。使用trace进行分析