官方定义是： 索引（Index）是帮助MySQL高效获取数据的数据结构，简单来说，索引是一种数据结构。以协助快速查询、 更新数据库表中数据。
索引的基本原理：
数据是以文件的形式存放在磁盘上面的，每一行数据都有它的磁盘地址,如果没有索引的话，我们要从千万行数据里面检索一条数据，只能依次遍历这张表的全部数据, 直到找到这条数据。但是我们有了索引之后，只需要在索引里面去检索这条数据就行了，因为它是 特殊的专门用来快速检索的数据结构，我们找到数据存放的磁盘地址以后，就可以拿到数据了。
生活中随处可见索引的例子，如火车站的车次表、图书的目录等。它们的原理都是一样的，通过不断的缩小想要获得数据的范围来筛选出最终想要的结果，同时把随机的事件变成顺序的事件，也就是我们总是通过同一种查找方式来锁定数据。
一：索引类型
1.1逻辑维度
1.2数据结构维度
1.3物理存储维度
聚集索引与非聚集索引 都是B+树结构
聚集索引：聚集索引就是以主键创建的索引，在叶子节点存储的是表中的数据。
非聚集索引：非聚集索引就是以非主键创建的索引，在叶子节点存储的是主键和索引列。
二：索引存储模型推演
2.1、二分查找
二分查找的一种思想，也叫折半查找，每一次，我们都把候选数据缩小了一半。如果数据已经排过序的话，这种方式效率比较高。 所以第一个,我们可以考虑用有序数组作为索引的数据结构。
2.2、模型推演
1、有序数组，它用于等值查询和比较查询效率非常高，但是更新数据的时候会出现一个问题, 可能要挪动大量的数据(改变index),所以只适合存储静态的数据。
2、哈希结构，类似k-v结构，也就是，key和value是一对一关系。它用于等值查询还可以，但是范围查询它是无能为力的。
3、为了支持频繁的修改，比如插入数据，我们需要采用链表。链表的话，如果是单链 表，它的查找效率还是不够高，所以，有没有可以使用二分査找的链表呢？为了解决这个问题，BST (Binary Search Tree)也就是我们所说的二叉査找树诞生
4、二叉查找树的特点是什么？
投影到平面以后，就是一个有序的线性表。二叉查找树既能够实现快速查找，又能够实现快速插入。
但是二叉查找树有一个问题，就是它的查找耗时是和这棵树的深度相关的，二叉树在最坏的情况下会退化成一个链表，在最坏的情况下时间复杂度会退化成O(n)，相当于全表扫描。因此，一般二叉树不适合作为索引结构。
5、造成它倾斜的原因是什么呢？
因为左右子树深度差太大，这棵树的左子树根本没有节点——也就是它不够平衡。
所以，我们有没有左右子树深度相差不是那么大，更加平衡的树呢，这个就是平衡二叉树，叫做Balanced binary search trees,或者AVL树
平衡二叉树特点：它也是一颗二叉查找树，任何节点的两个子树高度最大差为1。所以就不会出现特殊化一个链表的情况
6、AVL树用于存储索引数据
首先，索引的数据，是放在硬盘上的。查看数据和索引的大小，当我们用树的结构来存储索引的时候，访问一个节点就要跟磁盘之间发生一次10操作。InnoDB操作磁盘的最小的单位是一页(或者叫一个磁盘块)，大小是16K(16384 字节)。那么，一个树的节点必须设计成16K的大小，不然就会出现读不完或者读不够的情况。
如果我们一个节点只存一个键值+数据+引用，例如整形的字段，可能只用了十几个或者几十个字节，它远远达不到16K的容量。
想象一下，我们基于索引査找数据的时候，肯定是希望一次从磁盘加载很多的数据 到内存中进行比较，这样就可以尽快拿到完整的数据。如果一个节点只存1个这样的单 元，就需要读更多的节点，发生更多的I/O操作。如果是机械硬盘时代，每次从磁盘读取数据需要10ms左右的寻址时间，交互次数 越多，消耗的时间就越多
所以AVL树就会有下面的问题：
7、怎么解决这个问题？
这样，我们的树是不是从原来的高瘦高瘦的样子，变成了矮胖矮胖的，这个时候，我们的树就不再是二叉了，而是多叉，或者叫做多路。
8、多路平衡查找树（Balanced Tree）
这个就是B树，B树在枝节点和叶子节点存储键值、数据地址、节点引用。
特点：
比如：我们画的这棵树，每个节 点存储两个关键字，那么就会有三个分叉指向三个子节点（当然肯定不只存3个这么少）
9、那B树又是怎么实现一个节点存储多个关键字，还保持平衡的呢？跟AVL树有什 么区别？
B Tree在做检索时，检索效率非常高，但是在做数据插入和删除时，会破坏B Three本身的平衡，所以为了保持B Tree的平衡，需要对节点进行分裂、合并、转移等操作，跟AVL树的左旋和右旋是不一样的，而这个操作在节点数量较多的情况下性能影响较大。，所以 解释了为什么我们不要在频繁更新的列上建索引，或者为什么不要更新主键。
节点的分裂和合并，其实就是InnoDB页的分裂和合并。如果索引键值有序，写满一页接着开辟一个新的页，如果索引键值无序，存储过程造成大量磁盘碎片，带来频繁的page分裂和合并。
B树相对于平衡二叉树，就可以存储更多的数据，高度更低。但是最后会选择B+树呢？因为B+树是B树的升级版
10、B+Tree
总结一下，InnoDB中的B+Tree索引带来的优势：
它是BTree的变种，BTree能解决的问题，它都能解决
B Tree解决的两大问题 ：每个节点存储更多关键字；路数更多
扫库、扫表能力更强
如果我们要对表进行全表扫描，只需要遍历叶子节点就可以 了，不需要遍历整棵B+Tree拿到所有的数据
B+Tree的磁盘读写能力相对于B Tree来说更强
根节点和枝节点不保存数据区, 所以一个节点可以保存更多的关键字，一次磁盘加载的关键字更多
排序能力更强
因为叶子节点上有下一个数据区的指针，数据形成了链表
效率更加稳定
永远是在叶子节点拿到数据，所以I0次数是稳定的
同样索引带来的问题或者缺点？
三：为什么不用红黑树?
红黑树也是BST树，但是不是严格平衡的，不需要像AVL树那样严格平衡，通过变色和旋转来保持平衡。
为什么不用红黑树？
红黑树一般只放在内存里面用。例如Java的Map,它可以用来实现一致性哈希。
四：B+Tree作为索引的数据结构带来的好处
由于在B+ Tree中，每个节点不存存储数据区，只需要存储键值+指针，使得B+ Tree在每个节点存储的路数更多。
假设索引字段+指针大小一共是16个字节，那么一个Page页（一个节点）能存储1000个这样的单元（键值+指针）。假设一条记录是16bytes，一个叶子节点（一页）可以存储10条记录！
当数的深度是3的时候，就有1000^2个叶子节点，可存储的数据为1000 x1000 x 10 =10000000（千万）
也就是说，在InnoDB中B+树的深度在3层左右，就能满足千万级别的数据存储。
4.1、InnoDB 索引存储：每张InnoDB的表有两个文件（.frm和.ibd）
在InnoDB的某个索引的叶子节点上，它直接存储了我们的数据。 所以，为什么说在InnoDB中索引即数据，数据即索引，就是这个原因。
但是这里会有一个问题，一张InnoDB的表可能有很多个多索弓|,数据肯定是只有—份的那数据在哪个索引的叶子节点上呢？
这里的就是聚集索引（聚簇索引），就是索引键值的逻辑顺序跟表数据行的物理存储顺序是一致的。InnoDB组织数据的方式就是（聚集）索引组织表（clustered index organize table）如果说一张表创建了主键索引，那么这个主键索引就是聚集索引，决定数据行的物理存储顺序。
那主键索引之外的索引，会不会也把完整记录在叶子节点放一份呢？
并不会，因为这会带来额外的存储空间浪费和计算消耗。刚才已经讲了，如果有主键索引，那么主键索引就是聚集索引。其他的索引统一叫做"二级索引”（secondary index）。二级索引存储的是二级索引的键值，例如在name上建立索引，节点上存的是name 的值（很明显，它的键值逻辑顺序跟物理行的顺序不一致）。而二级索引的叶子节点存的是这条记录对应的主键的值。
二级索引检索数据的流程是这样的
当我们用name索引查询一条记录，它会在二级索引的叶子节点找到，然后拿到主键值，然后再到主键索引的叶子节点拿到数据。
为什么不存地址而是存键值？因为地址会变化。
从这个角度来说，因为主键索引比二级索引少扫描了一棵B+Tree （避免了回表）， 它的速度相对会快一些。
如果一张表没有主键怎么办？
那完整的记录放在哪个索引的叶子节点？或者, 这张表根本没有索引呢？数据放在哪里？
1、 如果我们定义了主键(PRIMARY KEY),那么InnoDB会选择主键作为聚集索弘
2、 如果没有显式定义主键，则InnoDB会选择第一个不包含有NULL值的唯一索引 作为主键索引。
3、 如果也没有这样的唯一索引，则InnoDB会选择内置6字节长的ROWID作为隐 藏的聚集索引，它会随着行记录的写入而主键递增。
五：B+树 索引搜索过程
###表结构
CREATE TABLE `user` (
`id` int(11) NOT NULL,
`name` varchar(255) DEFAULT NULL,
`age` int(11) DEFAULT NULL,
`sex` int(1) DEFAULT NULL,
PRIMARY KEY (`id`),
KEY `idx_age` (`age`) USING BTREE
) ENGINE=InnoDB DEFAULT CHARSET=utf8;
insert into user values(100,'1',43,'0');
insert into user values(200,'2',48,'0');
insert into user values(300,'3',36,'1');
insert into user values(400,'4',32,'0');
insert into user values(500,'5',37,'1');
insert into user values(600,'6',49,'0');
insert into user values(700,'7',28,'1');
select * from user where age=32;
id主键索引，聚族索引结构图
什么是回表？拿到主键再回到主键索引查询的过程，就叫做「回表」
六：覆盖索引
覆盖索引：在查询的数据列里面，不需要回表去查，直接从索引列就能取到想要的结果。换句话说，你SQL用到的索引列数据，覆盖了查询结果的列，就算上覆盖索引了。
这就是项目中不要select *, 而是要使用具体的字段 select id,age 的原因
七：索引下推
可以在索引遍历过程中，对索引中包含的字段先做判断，直接过滤掉不满足条件的记录，减少回表次数。
八：联合索引之最左前缀原则
九：索引创建建议
1、在用于where判断order排序和join的（on）、group by的字段上创建索引
2、索引的个数不要过多——浪费空间，更新变慢。
3、过长的字段，建立前缀索引。
4、区分度低的字段，例如性别，不要建索引——离散度太低，导致扫描行数过多。
5、频繁更新的值，不要作为主键或者索引——B+树的平衡导致 页分裂 ，影响效率
6、随机无序的值，不建议作为索引，例如身份证、UUID、MD5——无序，分裂
7、组合索引把散列性高（区分度高）的值放在前面
8、创建复合索引，而不是修改单列索引
9、查询不涉及的列、重复值较多的列、text、blob数据类型不要建立索引
9.1、大表添加索引
可以参考以下方法：
1.先创建一张跟原表A数据结构相同的新表B。
2.在新表B添加需要加上的新索引。
3.把原表A数据导到新表B
4.rename新表B为原表的表名A，原表A换别的表名；
十：索引失效
1、查询条件包含or，可能导致索引失效
2、如果字段类型是字符串，where时一定用引号括起来，否则索引失效
3、like条件中前面带%
4、联合索引，查询时的条件列不是联合索引中的第一个列，索引失效。
5、在索引列上使用mysql的内置函数，列运算（如，+、-、*、/），索引失效。
6、字符串不加引号，出现隐式的类型转化
7、负向查询：索引字段上使用（！= 或者 < >，not in，not like）时，可能会导致索引失效。
8、索引字段上使用is null， is not null，可能导致索引失效。
9、左连接查询或者右连接查询查询关联的字段编码格式不一样，可能导致索引失效。
10、mysql估计使用全表扫描要比使用索引快,则不使用索引