一、索引是什么
1，索引图解
数据库索引，是数据库管理系统(DBMS)中的一个排序的数据结构，以协助快速查询、更新数据库表中数据。----维基百科
数据是以文件的形式存放在磁盘上面，每一行数据都有它的磁盘地址。如果没有索引的话，我们要检索一条数据，只能依次遍历这张表的全部数据，直到找到这条数据。
有了索引之后，只需要地索引中检索这条数据就行了，因为它是一种特殊的专门用来快速检索的数据结构，找到数据存放的磁盘地址之后，就可以拿到数据了。
2，索引类型
在InnoDB中，索引有三种，普通索引、唯一索引(主键索引是特殊的唯一索引)、全文索引。
- 普通(Normal)：也叫非唯一索引，是普通的索引，没有任何限制。
- 唯一(Unique)：唯一索引要求键值不能重复，主健索引是一种特殊的唯一索引，它多了一个限制条件，要求健值不能为空。主健索引用primay key创建。
- 全文(Fulltext)：针对比较大的数据，比如存放消息内容、文章，有几KB数据的情况下要解决like查询在全文匹配效率低的问题，可以创建全文索引。只有文本类型的字段才能创建全文索引，比如char、varchar、text。
create table 'fulltext_test'(
'content' varchar(50) default null,
fulltext key 'content'('content')
);
语法：
select * from fulltext_test where match(content) against('简书' in natural language mode);
MyISAM和InnoDB支持全文索引。
二，索引存储模型
索引的可视化演示：
https://www.cs.usfca.edu/~galles/visualization/Algorithms.html
1，二分查找
二分查找，又叫折半查找。如果数据经过排序的话，这种方式效率比较高。可考虑使用有序数组作为索引的数据结构。
有序数组的等值查询和比较查询效率非常高，但是更新的时候要挪动大量的数据(改变index)，只适合存储静态的数据。
为支持频繁的修改，比如插入数据，需要使用链表。链表的话，如果是单链表，查询效率不够高。
支持二分查找的链表，BST（Binary Search Tree）即二叉查找树诞生了。
2，二叉树（BST Binary Search Tree）
二叉查找树的特点：左子树的所有节点都小于父节点，右子数所有节点都大于父节点。投影到平面就是一个有序的线性表。
二叉查找树既能实现快速查找，又能实现快速插入。它的查找耗时是和树的深度有关，在最坏的情况下会退化成O(n)，此时变成了链表，又称斜树。
左右子树深度差太大，不平衡。有没有左右子树深度相差不那么大，更加平衡的树呢？
这就是平衡二叉树，叫做Balanced binary serach tress，或者AVL树。
3，平衡二叉对(AVL Tree)（左旋、右旋）
平衡二叉树，AVL Trees(Balanced binary search trees)：左右子树的深度差绝对值不超过1。
在平衡二叉树中，一个节点，它的大小是固定的单位，作为索引应该存储什么内容？
索引要存你建立索引的字段的值，叫做健值，比如id的值，还要完整记录在磁盘上的地址。由于AVL树是二叉树，还要存储左右子树的指针。
AVL树存储索引数据，索引的数据，是放在硬盘上的。查看数据和索引的大小。
select concat(round(sum(data_length/1024/1024),2),'MB') as data_len,
concat(round(sum(index_length/1024/1024),2),'MB') as index_len
from information_schema.tables
where table.schema='dbname' and table_name='tablename';
当用树的结构来存储索引的时候，访问一个节点要跟磁盘发生一次IO操作。InnoDB操作磁盘的最小单位是一页，大小是16KB。如果一个节点只存一个健值+数据地址+引用，可能只用十几个字节或者几十个字节，远不到16KB的容量，如果一个节点只存1个这样的数据，就需要读更多的节点，发生更多的I/O操作。
要解决这个问题，1，让每个节点存储更多的数据。2，节点上的关键字的数量越多，指针也越多，意味着有更多的分叉。分叉越多，树的深度会减少。这时的树不再是二叉树，而是多路。
4，多路平衡查找树(B Tree) （分裂、合并）
Balanced Tree，即多路平衡查找树，叫做B Tree。
跟AVL树一样，B树在枝节点和叶子节点存储健值、数据地址、节点引用。
分叉数永远比关键字数多1.
B Tree是怎么实现一个节点存储多个关键字的，还保持平衡的呢？和AVL有什么区别？
如果执行节点的删除，会执行合并的操作。这里的分裂和合并和AVL的左旋和右旋是不一样的。
在更新索引的时候，会有大量的索引的结构的调整，所以不要在频繁更新的列上建索引，或者不要更新主健。
节点的分裂和合并，其实就是InnoDB页的分裂和合并。
如果索引无序，存储过程造成大量的磁盘碎片，带来频繁的page的分裂和合并。
5，B+树(加强版多路平衡查找树)
MySQL中B+Tree的特点：
1，它的关键字的数量是跟路数相等的。
2，B+ Tree的根节点和枝节点中都不会存储数据，只有叶子节点才存储数据。
3，B+ Tree的每个叶子节点增加了一个指向相邻叶子节点的指针，它的最后一个数据会指向下一个叶子节点的第一个数据，形成一个有序链表的结构。
B+ Tree的数据搜寻过程：
1，在根节点找到键值，由于不是叶子节点，在继续往下搜寻，直到在叶子节点上找到数据。
2，如果是范围查询，当找到一个数据后，只需要顺着节点和指针顺序就可以一次性访问到所有的数据节点，极大地提高了区间查询效率。
InnoDB中的B+ Tree的优势：
1，它是B Tree的变种，B Tree能解决的问题，它都能解决。B Tree解决的问题(每个节点存储更多的关键字；路数更多)
2，扫库、扫表能力更强(如果要进行全表扫描，只需要遍历叶子节点就可以了，不需要遍历整棵B+ Tree拿到所有的数据)
3，B+ Tree的磁盘读写能力相对于B Tree更强(根节点和枝节点不保存数据，所以一个节点可以保存更多的关键字，一次磁盘加载的关键字更多)
4，排序能力更强(叶子节点上有下一个数据区的指针，数据形成了链表)
5，效率更加稳定(B+ Tree永远在叶子节点拿到数据，所以IO次数是稳定的)
一张千万级的表，查询数据只需要访问3次磁盘。InnoDB中B+ Tree的深度一般为1-3层。
6，为什么不用红黑树
红黑树也是BST树，但不是严格平衡的，通过变色和旋转来保持平衡。
满足5个约束：
- 节点为红色或者黑色。
- 根节点必须为黑色的。
- 叶子节点都是黑色的NULL节点。
- 红色节点的两个子节点都是黑色(不允许两个相邻的红色节点)。
-
从任意节点出发，到其每个叶子节点的路径中包含相同数据的黑色节点。
红黑树
可推导出，从根节点到叶子节点的最长路径(红黑相间的路径)不大于最短路径(全是黑色节点)的2倍。
为什么不用红黑树？ 1，只有两路； 2，不够平衡。
红黑树一般放在内存中使用。如Java的TreeMap，可以实现一致性哈希。
7，索引方式：真的用的B+ Tree吗？
navicat工具中，创建索引，索引方式有两种。
Hash: 以KV的形式检索数据，会根据索引字段生成哈希码和指针，指针指向数据
哈希索引的特点：
1，时间复杂度为O(1)，查询速度比较快。哈希索引不是按顺序存储的，不能用于排序。
2，查询时根据键值计算哈希码，只支持等值查询(= in)，不支持范围查询(> < >= between and)。
3，字段重复比较多的时候，会有大量的哈希冲突，效率会降低。
在InnoDB中，不能显式地创建一个哈希索引(所谓的支持哈希索引指的是AHI，自适应哈希，它是InnoDB自动为buffer pool中的热点页创建的索引)。memory存储引擎可以使用Hash索引。
三、B+ Tree的落地形式
1，MySQL架构
MySQL是一个支持插件式存储引擎的数据结构。在MySQL中每个表在创建的时候都能指定它所使用的存储引擎。
2，MySQL数据存储文件
MySQL的数据都是文件的形式存放在磁盘中的，查看数据目录的地址：
show variables like 'datadir';
每个数据库有一个目录，有一个自己的文件夹。每个表有一些跟表名对应的文件。InnoDB的表有两个文件(.frm和.ibd)，MyISAM的表有三个文件(.frm、.MYD、.MYI)。.frm是MySQL里表结构定义的文件。
MyISAM
一个是.MYD文件，D代表Data，是MyISAM的数据文件，存放数据记录。
一个是.MYI文件，I代表Index，是MyISAM的索引文件，存放索引，比如在id上创建一个主键索引，主健索引就在这个索引文件中。一个索引会有一个B+ Tree。所有的B+ Tree都在myi文件里面。
在MyISAM里，索引和数据是两个独立的文件。
怎么根据索引找到数据？
MyISAM的B+ Tree里面，叶子节点存储的是数据文件对应的磁盘地址。所以从索引文件.MYI中找到健值后，会到数据文件.MYD中获取对应的数据记录。
InnoDB
在InnoDB的某个索引的叶子节点上，它直接存储了我们的数据。在InnoDB中索引即数据，数据即索引。
一张InnoDB表可能有多个索引，数据肯定只有一份，数据在哪个索引的叶子节点上呢？
聚集索引，就是索引键值和逻辑顺序跟表数据行的物理存储顺序是一致的。InnoDB组织数据的方式就是聚集索引组织表(clustered index organize table)。如果一张表创建了主健索引，那主健索引就是聚集索引，决定数据行的物理存储顺序。
主建索引之外的索引，不会在叶子节点上存放完整的记录。
InnoDB中，主健索引和辅助索引有主次之分。如果有主健索引，那么主健索引就是聚集索引。其它索引统一叫做“二级索引”(secondary idnex)。
二级索引存储的是二级索引的健值，二级索引的叶子节点存的是这条记录对应的主健的值。
二级索引检索流程：在二级索引的叶子节点上拿到主健值，然后再到主健索引的叶子节点拿到数据。不存地址而存健值 ，是因为地址会变化。
如果表没有主健怎么办？完整记录放在哪个叶子节点？或者表根本没有索引，数据放在哪？
1，如果我们定义了主健(primary key)，那么InnoDB会选择主健作为聚集索引。
2，如果没有显示主健，则InnoDB会选择第一个不包含有NULL值的唯一索引作为主健索引
3，如果也没有唯一索引，则InnoDB会选择内置6字节长的ROWID作为隐藏的聚集索引，它会随着行记录的写入而主健递增。
四，索引的使用原则
索引使用误区：索引越多越好。
1，列的离散度
列的离散度的公式： count(distinct(column_name)):count(*)，列的全部不同值和所有数据行的比例。数据行相同的情况下，分子越大，离散度越高。如果列的重复值越多，离散度就越低，重复值越少，离散度就越高。不建议在离散度低的字段上建立索引。如果在B+ Tree里面的重复值太多，MySQL的优化器发现走索引跟使用全表扫描差不多的时候，就算建了索引，也不一定会走索引。
2，联合索引最左匹配
联合索引在B+ Tree中是复合的数据结构，它是按照从左到右的顺序来建立搜索树的。在建立联合索引的时候，把最常用的列放在最左边。使用右边的字段，无法使用索引。
比如创建三个字段的索引index(a,b,c)，相当于创建了三个索引：
index(a), index(a,b), index(a,b,c)。
3，覆盖索引
回表：非主健索引，我们先通过索引找到主健索引的健值，再通过主健值查出索引里面没有的数据，它比主健索引的查询多描述了一颗索引树，这个过程就叫回表。
在二级索引里面，不管是单列索引还是联合索引，如果select的数据只用从索引中就能取得，不必从数据区中读取，这时候使用的索引就叫做覆盖索引，这样就避免的回表。
-- 创建联合索引
ALERT TABLE USER DROP INDEX cominx_name_phone;
ALERT TABLE USER add INDEX 'cominx_name_phone'('name','phone');
这三个查询语句属于覆盖索引：
EXPLAIN select name,phone from user where name ='简书' and phone='13000000000';
EXPLAIN select name from user where name ='简书' and phone='130000000';
EXPLAIN select phone from user where name ='简书' and phone='130000000';
select *，不是覆盖索引。如果改成只用where phone= 查询呢，按之前的分析是使用不到索引的，实际上可以用到覆盖索引，优化器觉得用索引更快，还是用到了索引。
覆盖索引减少了IO次数，减少了数据的访问量，可以大大地提升查询效率。
4，索引条件下推(ICP)
索引条件下推(Index Condition Pushdown)，5.6以后完善的功能。只适合用于二级索引。ICP的目标是减少访问表完整行的读数据从而减少I/O操作。
这里说的下推，意思是把过滤的动作在存储引擎做完，而不需要到Server层过滤。
比如查询：
select * from employees whrere last_name = 'wang' and first_name like '%zi';
因为字符是从左往右排序的，当把%放在前面的时候，是不能基于索引去比较的，只有last_name这个字段能够用于索引比较和过滤。
查询过程是这样的：
1，根据联合索引查出所有的姓的二级索引数据。
2，回表，到主健索引上查询全部符合条件的数据
3，把这几条数据返回给server层，在server层过滤出名字以zi结尾的员工。
索引的比较是在存储引擎进行的，数据记录的比较，是在server层进行的。当条件不能用于索引过滤时，server层不会把条件传递给存储引擎，所以取了没有必要的记录。
所以过滤动作能不能在存储引擎完成呢？
1，根据索引查出所有姓的二级索引数据。
2，然后从二级索引中筛选出以zi结尾的索引
3，然后回表，到主健索引上查询符合条件的数据，返回给server
ICP默认是开启的，也就是针对二级索引，只要能够把条件下推给存储引擎，就会下推，不需要我们干预：
set optimizer_switch='index_condition_pushdown=on';
此时的执行计划，using index condition：
关闭ICP:
set optimizer_switch='index_condition_pushdown=off';
查看参数：
show variable like 'optimizer_switch';
执行sql，using where：
Using where 代表从存储引擎取回的数据不全部满足条件，需要在server层过滤。
五，索引的创建和使用
1，索引的创建
- 在用于where 判断 order 排序和join 的 on，group by 的字段上创建索引
- 索引的个数不要过多---浪费空间，更新变慢
- 过长的字段，建立前缀索引
create table 'pre_test'(
'content' varchar(20) default null,
key 'pre_idx'('conent'(6))
) engine = innodb defualut charset=utf8m4;
- 区分度低的字段，不要建索引---离散度太低，扫描的行数过多
- 频繁更新的值，不要作为主健或索引----页分裂
- 随机无序的值，不建议作为索引，如身份证、UUID---无序、分裂
- 组合索引把散列性高的值放在前面
- 创建复合索引，而不是修改单列索引
2，什么时候用不到索引
- 索引列表上使用函数(replace，substr，concat, sum,count,avg)，表达式，计算(+ - * /)
- 字符串不加引号，出现隐式转换
- like 条件前面带 %
- 负向查询， not like 不能， !- <> 和not in 在某些情况下可以。
用不用索引，最终都是优化器说了算。优化器是基于什么的优化器？
基于cost开销(Cost Base Optimizer)，它不是基于规则(Rule-Based Optimizer)，也不是基于语义。怎么开销小怎么来。
