在这里先抛出几个问题：
表的索引越全越好，对吗？
为什么不要在性别字段上建索引？
为什么不建议使用身份证做主键？
模糊匹配like abc% , like %abc% , like %888都用不到索引，对吗？
不要使用select *，要写明具体查询字段，为什么？
一个简单的加索引查找测试：
先准备一张user表，在其中插入五百万条记录，执行查询：
select name from `user` where name="Jesses"；
执行SQL消耗时间12s。
在name字段上创建索引：
alter table `user` add index idx_name(`name`);
再次执行：
select name from `user` where name="Jesses"；
执行SQL消耗时间0.081s。
从demo中可以看出索引对于查找性能的显著提升。
维基百科对数据库索引的定义：
数据库索引，是数据库管理系统（DBMS）中一个排序的数据结构，以协助快速查询、 更新数据库表中数据。
怎么理解这个定义呢？
形象描述就如一本书的目录，一本字典的索引。
我们说索引是一种数据结构，那么它到底应该选择一种什么数据结构，才能实现数据的高效检索呢？
双十一过去之后，你女朋友跟你玩了一个猜数字的游戏。 猜猜我昨天买了多少钱，给你五次机会。 10000？低了。30000？高了。接下来你会猜多少？ 20000。为什么你不猜 11000，也不猜 29000 呢？
其实这个就是二分查找的一种思想，也叫折半查找。
每一次，我们都把候选数据缩小了一半。如果数据已经排过序的话，这种方式效率比较高。
所以我们可以考虑用有序数组作为索引的数据结构。
有序数组 的等值查询和比较查询效率非常高，但是更新数据的时候会出现一个问题，
可能要挪动大量的数据（改变数据的index），所以只适合存储静态的数据。
为了支持频繁的修改，如插入数据，我们需要采用 链表 。但如果是单链表，它的查找效率还是不够高。
有没有可以使用二分查找的链表呢？
为了解决这个问题，BST（Binary Search Tree）也就是我们所说的二叉查找树诞生了。
二叉查找树的特点是什么？
左子树所有的节点都小于父节点，右子树所有的节点都大于父节点。投影到平面以
后，就是一个有序的线性表。
二叉查找树既能够实现快速查找，又能够实现快速插入。
但是二叉查找树有一个问题：
就是它的查找耗时是和这棵树的深度相关的，在最坏的情况下时间复杂度会退化成 O(n)。
如下图，最坏的情况，当数据有序的时候：
link：https://www.cs.usfca.edu/~galles/visualization/BST.html
当数据是有序的时候，它会变成链表（这种树又叫做“斜树”）， 这种情况下不能达到加快检索速度的目的，和顺序查找效率是没有区别的。
造成它倾斜的原因是什么呢？ 因为左右子树深度差太大，这棵树的左子树根本没有节点——也就是它不够平衡。 我们有没有左右子树深度相差不是那么大，更加平衡的树呢？ 这个就是平衡二叉树，叫做 Balanced binary search trees，或者 AVL 树。
平衡二叉树的定义：左右子树深度差绝对值不能超过 1。
比如左子树的深度是 2，右子树的深度只能是 1 或者 3。
这个时候我们再按顺序插入 1、2、3、4、5、6，一定是这样，不会变成一棵“斜树”。
右型-左旋
当我们插入了 1、2 、3 时，3肯定是要在 2 的右边的，
这个时候根节点 1 的右节点深度会变成 2，但是左节点的深度是 0，
因为它 没有子节点，所以就会违反平衡二叉树的定义。
那应该怎么办呢？因为它是右节点下面接一个右节点，右-右型，所以这个时候我们
要把 2 提上去，这个操作叫做左旋。
同样的，如果我们插入 7、6、5，这个时候会变成左左型，就会发生右旋操作，把 6
提上去
平衡的问题就解决了。
在平衡二叉树中，一个节点，它的大小是一个固定的单位，作为索引应该存储什么 内容？
它应该存储三块的内容：
1）索引的键值。比如在 id 上面创建了一个索引，在用 where id =1 的条件查询时，
就会找到索引里面的 id =1的这个键值。
2）数据的磁盘地址，因为索引的作用就是去查找数据的存放的地址。
3）因为是二叉树，它必须还要有左子节点和右子节点的引用，
这样才能找到下一个节点。比如大于 26 的时候，走右边，到下一个树的节点，继续判断。
如图，如果使用AVL-Tree这样存储数据，又会有什么问题呢？
在说明问题前，先来了解InnoDB的逻辑存储结构。
https://dev.mysql.com/doc/refman/5.7/en/innodb-disk-management.html
https://dev.mysql.com/doc/refman/5.7/en/innodb-file-space.html
MySQL 的存储结构分为 5 级：表空间、段、簇、页、行
表空间 Table Space
表空间可以看做是 InnoDB 存储引擎逻辑结构的最高层，所有的数据都存放在表空间中。
分为：系统表空间、独占表空间、通用表空间、 临时表空间、Undo 表空间。
段 Segment
表空间是由各个段组成的，常见的段有数据段、索引段、回滚段等，段是一个逻辑的概念。
一个 ibd 文件（独立表空间文件）里面会由很多个段组成。
创建一个索引会创建两个段，一个是索引段：leaf node segment，一个是数据段： non-leaf node segment。
索引段管理非叶子节点的数据。数据段管理叶子节点的数据。
也就是说，一个表的段数，就是索引的个数乘以 2。
簇 Extent
一个段（Segment）又由很多的簇（也可以叫区）组成，每个区的大小是 1MB（64 个连续的页）。
每一个段至少会有一个簇，一个段所管理的空间大小是无限的，可以一直扩展下去，
但是扩展的最小单位就是簇。
页 Page
为了高效管理物理空间，对簇进一步细分，就得到了页。
簇是由连续的页（Page）组成的空间，一个簇中有 64 个连续的页（1MB／16KB=64）。
这些页面在物理上和逻辑上都是连续的。
跟大多数数据库一样，InnoDB 也有页的概念（也可以称为块），每个页默认 16KB。
页是 InnoDB 存储引擎磁盘管理的最小单位，通过 innodb_page_size 设置。
一个表空间最多拥有 2^32 个页，默认情况下一个页的大小为 16KB，也就是说一个
表空间最多存储 64TB 的数据。
1）浪费空间
当我们用树的结构来存储索引的时候，访问一个节点就要跟磁盘之间发生一次 IO。
InnoDB 操作磁盘的最小的单位是一页（或者叫一个磁盘块），大小是 16K(16384 字节)。
那么， 一个树的节点就是 16K 的大小 。
如果我们一个节点只存一个键值+数据+引用，例如整形的字段，可能只用了十几个
或者几十个字节，它远远达不到 16K 的容量，所以 访问一个树节点 ， 进行一次 IO 的时候，
浪费了大量的空间。
2）IO次数多
如果每个节点存储的数据太少，从索引中找到我们需要的数据，就要访问更多 的节点，
这就意味着跟磁盘交互次数就会过多。
如果是机械硬盘时代，每次从磁盘读取数据需要 10ms 左右的寻址时间，
交互次数越多，消耗的时间就越多。
如上面这张图，我们一张表里面有 6 条数据，当我们查询 id=37 的时候，
要查询两个子节点，就需要跟磁盘交互 3 次，如果有几百万的数据这个时间更加难以估计。
试想解决方案，可以让每个节点存放更多的数据。 我们的指针数也越多，也就是意味着可以有更多的分叉（我们把它叫做“路数”） 因为分叉数越多，树的深度就会减少（根节点是 0） 这样最终形成的树就不再是瘦高的型状，而是矮胖的型状。 这样树也就不再是二叉树，而是多叉树（多路）;
和 AVL 树一样，B 树在枝节点和叶子节点存储键值、数据地址、节点引用。
它有一个特点： 分叉数（路数）永远比关键字数多 1。
如下图，每个节点存储两个关键字，那么就会有三个指针指向三个子节点。
B Tree 的查找规则是什么样的呢？
比如要在这张表里面查找 15。
因为 15 小于 17，走左边。
因为 15 大于 12，走右边。
在磁盘块 7 里面就找到了 15，只用了 3 次 IO。
so，B Tree 比 AVL 树效率更高。
B Tree 又是怎么实现一个节点存储多个关键字，还保持平衡的呢？
分裂操作
比如 Max Degree（度数）是 3 的时候，我们插入数据 1、2、3，在插入 3 的时候。
本来应该在第一个磁盘块放3，但是如果一个节点有三个关键字的时候，意味着有 4 个指针，
子节点会变成 4 路，所以这个时候必须进行分裂。把中间的数据 2 提上去，把 1 和 3 变
成 2 的子节点。
如果删除节点，则会有相反的合并的操作。
注意这里是分裂和合并，跟 AVL 树的左旋和右旋是不一样的。
可以看出，
在更新索引的时候会有大量的索引的结构的调整，
所以也解释了为什么 不要在频繁更新的列上建索引 ，或者为什么不要更新主键。
节点的分裂和合并，其实就是 InnoDB 页的分裂和合并。
B Tree 的效率已经很高了，但 MySQL 还又对 B Tree 进行改良，最终使用了B+Tree 。
B+树的存储结构：
MySQL 中的 B+Tree 有几个特点 ： 1、它的关键字的数量是跟路数相等的； 2、B+Tree 的根节点和枝节点中都不会存储数据，只有叶子节点才存储数据。 搜索到关键字不会直接返回，会到最后一层的叶子节点。 比如我们搜 id=28，虽然在第一层直接命中了。
但全部的数据都在叶子节点上面，所以我还要继续往下搜索，一直到叶子节点。
举个例子：假设一条记录是1K，一个叶子节点（一页）可以存储 16 条记录。非叶子节点可以存储多少个指针？ 假设索引字段是 bigint 类型，长度为 8 字节。 指针大小在 InnoDB 源码中设置为 6 字节，这样一共 14 字节。 非叶子节点（一页）可以存储 16384/14=1170 个这样的 单元（键值+指针），代表有 1170 个指针。 树 深 度 为 2 的 时 候 ，有 1170^2 个 叶 子 节 点 ，可 以 存 储 的 数 据 为 1170*1170*16=21902400。
在查找数据时一次页的查找代表一次 IO，也就是说，一张 2000 万左右的表，查询
数据最多需要访问 3 次磁盘。
所以在 InnoDB 中 B+ 树深度一般为 1-3 层，它就能满足千万级的数据存储。
总结一下，InnoDB 中的 B+Tree 的特点 ：
1)它是 B Tree 的变种，B Tree 能解决的问题，它都能解决。
B Tree 解决的两大问题是什么？（每个节点存储更多关键字；路数更多）
2)扫库、扫表能力更强
（如果我们要对表进行全表扫描，只需要遍历叶子节点就可以了，不需要遍历整棵 B+Tree 拿到所有的数据）
3) B+Tree 的磁盘读写能力相对于 B Tree 来说更强
（根节点和枝节点不保存数据区，所以一个节点可以保存更多的关键字，一次磁盘加载的关键字更多）
4)排序能力更强（因为叶子节点上有下一个数据区的指针，数据形成了链表）
5)效率更加稳定（B+Tree 永远是在叶子节点拿到数据，所以 IO 次数是稳定的）
MySQL 是一个支持插件式存储引擎的数据库，每个表在创建时都可以指定它所使用的存储引擎。
主要关注一下最常用的两个存储引擎，MyISAM 和 InnoDB 的索引的实现。
新建两张分别使用MyISAM和InnoDB作为存储引擎的表：
MySQL 的数据都是文件的形式存在磁盘中的，使用如下sql可以查看文件存储位置：
show VARIABLES LIKE 'datadir';
可以看到每张 InnoDB 的表有两个文件（.frm 和.ibd），MyISAM 的表 有三个文件（.frm、.MYD、.MYI）
相同的是.frm文件 .frm 是 MySQL 里面表结构定义的文件，建表的时候用任何一个存储引擎都会生成。
MyISAM中，另有两个文件：
.MYD 文件，D 代表 Data，是 MyISAM 的数据文件，存放数据记录。
.MYI 文件， I 代表 Index，是 MyISAM 的索引文件，存放索引。
如我们在 id 字段上面创建了一个主键索引，那么主键索引就是在这个.MYI索引文件里面。
也就是说，在 MyISAM 里面，索引和数据是两个独立的文件。
那我们怎么根据索引找到数据呢？
MyISAM的 B+Tree 里面，叶子节点存储的是数据文件对应的磁盘地址。
所以从索引文件.MYI 中找到键-值后，会到数据文件.MYD 中获取相应的数据记录。
如果是辅助索引（非主键索引），也一样在.MYI 索引文件里面找到磁盘地址，然后再到.MYD数据文件里面获取数据。
和MyISAM不同的是，InnoDB 只有一个.ibd 文件。 在InnoDB 里面，InnoDB 是以主键为索引来组织数据的存储的， 索引文件和数据文件是同一个文件，都在.ibd 文件里面。 在 InnoDB 的主键索引的叶子节点上，它直接存储了数据记录：
什么叫做聚集索引（聚簇索引）？
就是 索引键值 的逻辑顺序跟 表数据行 的物理存储顺序是一致的。
（比如字典的目录是按拼音排序的，内容也是按拼音排序的，按拼音排序的这种目录就叫聚集索引）。
在 InnoDB 里面，它组织数据的方式叫做叫做（聚集）索引组织表。
所以主键索引是聚集索引，非主键都是非聚集索引。
如果 InnoDB 里面主键是这样存储的，那主键之外的索引，
比如在 name 字段上面建的普通索引，又是怎么存储和检索数据的呢？
InnoDB 中，主键索引和辅助索引是有一个主次之分的。
辅助索引存储的是辅助索引和主键值。如果使用辅助索引查询，会根据主键值在主键索引中查询，最终取得数据。
比如我们用 name 索引查询 name= 'NameA'，它会在叶子节点找到主键值，也就是id=1，然后再到主键索引的叶子节点拿到数据。
Q: 为什么在辅助索引里面存储的是主键值而不是主键的磁盘地址呢？
如果主键的数据类型比较大，是不是比存地址更消耗空间呢？
A: 前面说到 B Tree 是怎么实现一个节点存储多个关键字，还保持平衡的呢。
是因为有分叉和合并的操作，这个时候键值的地址会发生变化，所以在辅助索引里面不能存储地址。
Q: 另一个问题，如果一张表没有主键怎么办？
A: 1、如果我们定义了主键(PRIMARY KEY)，那么 InnoDB 会选择主键作为聚集索引。
2、如果没有显式定义主键，则 InnoDB 会选择第一个不包含有 NULL 值的唯一索引 作为主键索引。
3、如果也没有这样的唯一索引，则 InnoDB 会选择内置 6 字节长的 ROWID 作为隐藏的聚集索引，它会随着行记录的写入而主键递增。
问题：在经常使用的查询条件上都加上索引，越多越好，是吗？
列的离散度指：列的全部不同值和所有数据行的比例。
数据行数相同的情况下，分子越大，列的离散度就越高。
也就是列的重复值越多，离散度越低。列的重复值越少，离散度越高。
例如表中有手机号和性别（gender）两列，分别给手机号和性别建立索引。
以性别为条件查询的sql，用explain查看执行计划，可以看到要扫描的rows有近五万行：
就是因为性别列的离散度低，列的重复值多，查询时扫描的行数多，
其效率比起不用索引也高不了多少，反而建立的索引浪费空间。
如果在 B+Tree 里面的重复值太多，MySQL 的优化器发现走索引跟使用全表扫描差
不了多少的时候，就算建了索引，也不一定会走索引。
因此，建立索引，要尽量使用离散度高的字段。
在多条件查询的时候，常会建立联合索引。
如在 user 表上面，给 name 和 phone 建立了一个联合索引。
ALTER TABLE user_innodb add INDEX comidx_name_phone (name,phone);
联合索引的规则
联合索引在b+tree中会按从左到右的顺序建立索引
如图，name 是有序的，phone 是无序的。当 name 相等的时候， phone 才是有序的。
where name= 'xx' and phone = 'xx '去查询数据的时，
B+Tree 会优先比较 name 来确定下一步应该搜索的方向，往左还是往右。
name 相同的时候再比较 phone。
where phone = 'xx '
如果查询条件没有 name，因为建立搜索树的时候 name 是第一个比较条件，
就不知道第一步应该查哪个节点，就用不到索引。
什么时候能用到联合索引
使用两个字段， 可以 用到联合索引：
EXPLAIN SELECT * FROM user_innodb WHERE name= 'Tom ' AND phone = '18883028611' ;
只使用左边的 name 字段， 可以 用到联合索引:
EXPLAIN SELECT * FROM user_innodb WHERE name= 'Tom ' ;
使用右边的 phone 字段， 无法 使用索引，全表扫描：
EXPLAIN SELECT * FROM user_innodb WHERE phone = '18883028611' ;
联合索引创建包含多个索引
如果我们创建三个字段的索引 index(a,b,c)，相当于创建了三个索引：
index(a) ，
index(a,b)，
index(a,b,c)
当创建了联合索引时，会从左匹配自动创建多个索引。
如果需要使用a的单列索引，不需要再去单独创建了。
回表：
非主键索引，会通过索引找到主键索引的键值，再通过主键值查出索引里面没有的数据。
它比以主键索引的查询多扫描了一棵索引树，这个过程就叫回表。
对于辅助索引，不管是单列索引还是联合索引，如果 select 的数据列只从索引中就能够取得，
就不必从数据区中读取，这时候使用的索引就叫做覆盖索引，就避免了回表。
-- 创建联合索引
ALTER TABLE user_innodb add INDEX `comixd_name_phone` ( `name` , `phone` );
这三个查询语句都用到了覆盖索引：
EXPLAIN SELECT name,phone FROM user_innodb WHERE name= ' tom ' AND phone = ' 139xxx ' ;
EXPLAIN SELECT name FROM user_innodb WHERE name= ' tom ' AND phone = ' 139xxx ' ;
EXPLAIN SELECT phone FROM user_innodb WHERE name= ' tom ' AND phone = ' 139xxx ' ;
查看执行计划， Extra 列值为“Using index”代表使用了覆盖索引。
SELECT * FROM user_innodb WHERE name= ' tom ' AND phone = ' 139xxx ' ;
就使用不到覆盖索引，因为在辅助索引的树中没有只有辅助索引该列的值，需要再去主键索引的树中找整行数据。 使用到覆盖索引，减少了回表，也就减少了IO次数，提高了查询效率。
对一张employees 建立联合索引：
alter table employees add index idx_lastname_firstname(last_name,first_name);
关闭 ICP（索引条件下推） ：
set optimizer_switch= 'index_condition_pushdown=off' ;
查看参数：
show variables like 'optimizer_switch' ;
要查询所有姓 wang，并且名字最后一个字是 zi 的员工:
select * from employees where last_name= 'wang' and first_name LIKE '%zi' ;
这条 SQL 有两种执行方式：
1、根据联合索引查出所有姓 wang 的二级索引数据，
然后回表，到主键索引上查询全部符合条件的数据（3 条数据）。
然后返回给 Server 层，在 Server 层过滤出名字以 zi 结尾的员工。
2、根据联合索引查出所有姓 wang 的二级索引数据（3 个索引），
然后从二级索引中筛选出 first_name 以 zi 结尾的索引（1 个索引）；
然后再回表，到主键索引上查询全部符合条件的数据（1 条数据），返回给 Server.
很明显，第二种方式到主键索引上查询的数据更少。
注意， 索引的比较是在存储引擎进行的，数据记录的比较，是在 Server 层进行的 。
而当 first_name 的条件不能用于索引过滤时，Server 层不会把 first_name 的条件传递
给存储引擎，所以读取了两条没有必要的记录。
这时候，如果满足 last_name='wang'的记录有 100000 条，就会有 99999 条没有
必要读取的记录。
查看执行计划： explain select * from employees where last_name= 'wang' and first_name LIKE '%zi' ;
Using Where 代表从存储引擎取回的数据不全部满足条件，需要在 Server 层过滤。
先用 last_name 条件进行索引范围扫描，读取数据表记录，然后进行比较，检查是
否符合 first_name LIKE '%zi' 的条件。此时 3 条中只有 1 条符合条件。
开启 ICP：
set optimizer_switch= 'index_condition_pushdown=on' ;
再查看执行计划，此时的执行计划，Using index condition：
把 first_name LIKE '%zi'下推给存储引擎后，只会从数据表读取所需的 1 条记录。
索引条件下推（Index Condition Pushdown），5.6 以后完善的功能。只适用于 二级索引 。
ICP 的目标是减少访问表的完整行的读数量从而减少 I/O 操作
1、在用于 where 判断 order 排序和 join 的（on）字段上创建索引
2、索引的个数不要过多。
——浪费空间，更新变慢。
3、区分度低的字段，例如性别，不要建索引。
——离散度太低，导致扫描行数过多。
4、频繁更新的值，不要作为主键或者索引。
——页分裂
5、组合索引把散列性高（区分度高）的值放在前面。
6、创建复合索引，而不是修改单列索引。
7、过长的字段，怎么建立索引？
8、为什么不建议用无序的值（例如身份证、UUID ）作为索引？
什么时候用不到索引？
1、索引列上使用函数（replace\SUBSTR\CONCAT\sum count avg）、表达式、
计算（+ - * /）：
explain SELECT * FROM `t2` where id+ 1 = 4 ;
2、字符串不加引号，出现隐式转换
ALTER TABLE user_innodb DROP INDEX comidx_name_phone;
ALTER TABLE user_innodb add INDEX comidx_name_phone (name,phone);
explain SELECT * FROM `user_innodb` where name = 136 ;
explain SELECT * FROM `user_innodb` where name = '136' ;
3、like 条件中前面带%
where 条件中 like abc%，like %2673%，like %888 都用不到索引吗？为什么？
explain select * from user_innodb where name like 'wang%' ;
explain select * from user_innodb where name like '%wang' ;
过滤的开销太大，所以无法使用索引。这个时候会用全文索引。
4、负向查询
NOT LIKE 不能：
explain select * from employees where last_name not like 'wang'
!= （<>）和 NOT IN 在某些情况下可以：
explain select * from employees where emp_no not in ( 1 )
explain select * from employees where emp_no <> 1
注意一个 SQL 语句是否使用索引，跟数据库版本、数据量、数据选择度都有关系。
其实，用不用索引，最终都是 优化器 说了算。
Q1 : AVL树（平衡二叉树）、B树（多路平衡查找树）、B+树分别解决了什么问题？
Q2 : 为什么推荐使用递增的ID作为主键索引？
Q3 : 对于长度较长的字段，怎么创建索引？