一、索引是什么？
索引是帮助mysql高效获取数据排序好的数据结构。
索引存储在文件里面。
磁盘存取原理：
1.寻道时间(速度慢，费时)
2.旋转时间(速度较快)
数据文件存储在磁盘的磁道划分出的扇区里面。磁盘指针先去找到数据存储在哪一个磁道（寻道时间），然后逆时针旋转找打扇区（旋转时间）。现在都在优化减少寻道时间。
二、常见的数据结构介绍。
（一）二叉树。
定义：二叉树（binary tree）是指树中节点的度不大于2的有序树，它是一种最简单且最重要的树。二叉树的递归定义为：二叉树是一棵空树，或者是一棵由一个根节点和两棵互不相交的，分别称作根的左子树和右子树组成的非空树；左子树和右子树又同样都是二叉树。
二叉树主要的问题：树的高度无法控制，如果数据是递增插入的，在查找最新的数据时，基本上是全表遍历，速度比较慢。
（二）红黑树。
定义：红黑树是一种特化的AVL树（平衡二叉树），都是在进行插入和删除操作时通过特定操作保持二叉查找树的平衡，从而获得较高的查找性能。
红黑树存在的主要问题：数据量比较大时，红黑树的高度仍然是不可控制的。相比较二叉树，红黑树已经采取旋转的措施来控制树的高度了。
（三）HASH树。
hash树存在的问题：hash树存储的是数据的hash值，针对某个数据能很快找到对应的值，但是hash树无法进行范围查询。
（四）B Tree（其他叫法：B树，也叫B-Tree。没有B减树） 。
定义：是一种平衡的多叉树，称为B树（或B-树、B_树）。
特点：
1.度(Degree)-节点的数据存储个数；
2.叶节点具有相同的深度；
3.叶节点的指针为空；
4.节点中的数据key从左到右递增排列。
B树优缺点：B树在每一个节点增加了存储数据的个数，大大减小了树的高度。但是由于每一个节点的度不能无限增加。此外，b树的每一个节点都存储了索引和数据。
备注：内存从硬盘里面读取数据，每次I/O的最小单位是页（4K）,每次I/O是页的整数倍(有上限)。
（五）B+ Tree(B-Tree的变种)
特点：
1.非叶子节点不存储data，只存储key，可以增大度；
2.叶子节点不存储指针；
3.顺序访问指针，提高区间访问的性能。
B+Tree索引的性能分析：
一般使用磁盘I/O次数评价索引结构的优劣。
1.预读：磁盘一般会顺序向后读取一定长度的数据(页的整数倍)放入内存。
2.局部性原理：当一个数据被用到时，其附近的数据也通常会马上被使用。
3.B+Tree节点的大小设为等于一个页，每次新建节点直接申请一个页的空间，这样就保证一个节点物理上也存储在一个页里，就实现了一个节点的载入只需一次I/O。
4.B+Tree的度d一般会超过100，因此h非常小(一般为3到5之间)。
B+Tree的优缺点：B+Tree是通过将数据存在叶子节点，索引存在非叶子节点，这样增大了节点的度。虽然会存在索引的冗余，但这毕竟很小，所占的磁盘空间几乎不予考虑。叶子节点之间还有指针，可以提升范围查询的效率，是目前Mysql数据库索引存储所采取的数据结构。
数据结构教学网站：https://www.cs.usfca.edu/~galles/visualization/Algorithms.html。一定要点进去看一看，如果你不知道这个网站，先百度了解一下，你看过之后会回来感谢我的。
三、重点内容：
针对Mysql数据库进行索引分析,Mysql数据库索引是使用B+Tree数据结构进行存储。
Mysql的存储引擎有两种：InnoDB 和 MyISAM。
这两种引擎都是设置在表级别，不是设置在数据库级别的。
（一）MyISAM索引实现（非聚集）
使用MyISAM存储引擎，索引文件和数据文件是分离开的，索引的B+Tree叶子节点里面存的是索引和文件指针。在查找数据时，会先去.MYI文件里面找到索引，然后根据文件指针去.MYD文件里面找数据。
表数据和表索引的分开存储的，所以说，MyISAM索引是非聚集的。
（二）InnoDB索引实现(聚集)
使用InnoDB存储引擎，索引文件和数据文件是存储在一起的。在查找数据时，直接去.ibd文件里面查找索引和数据，比MyISAM引擎会快，所以Mysql默认采用InnoDB存储引擎。
1.数据文件本身就是索引文件
2.表数据文件本身就是按B+Tree组织的一个索引结构文件
3.聚集索引-叶节点包含了完整的数据记录
为什么InnoDB表必须有主键，并且推荐使用整型的自增主键？
答：因为InnoDB表索引及数据采用B+Tree数据结构进行存储。一个B+树的节点可以存储key、地址、行数据(仅叶子节点)，key 就是不重复的值且可以比较，主键的值不可重复，也不可为空，正好符合B+树key的要求。
聚簇索引默认是主键，如果表中没有定义主键，InnoDB 会选择一个唯一的非空索引（确切说会选择一个唯一非空的列作为主键）代替。如果没有这样的索引，InnoDB 会隐式定义一个主键来作为聚簇索引。
InnoDB 只聚集在同一个页面中的记录。包含相邻健值的页面可能相距甚远。
如果你已经设置了主键为聚簇索引，必须先删除主键，然后添加我们想要的聚簇索引，最后恢复设置主键即可
聚簇索引性能最好而且具有唯一性，所以非常珍贵，必须慎重设置。一般要根据这个表最常用的SQL查询方式来进行选择，某个字段作为聚簇索引，或组合聚簇索引，这个要看实际情况
聚簇索引的顺序和磁盘中数据的存储顺序是一致的，如果主键不是自增id，那么可以想象，它会干些什么，不断地调整数据的物理地址、分页，当然也有其他一些措施来减少这些操作，但却无法彻底避免。但，如果是自增的，那就简单了，它只需要一 页一页地写，索引结构相对紧凑，磁盘碎片少，效率也高。
为什么非主键索引结构叶子节点存储的是主键值？(一致性和节省存储空间)
答：因为数据内容会经常进行变动（update语句），主键是不变的。不然一个数据变动了，所有的索引结构均需要变动，存在数据一致性问题。同时，也节省了磁盘空间。
联合索引的底层存储结构长什么样？
答：
什么是索引最左前缀原理？
答：
就是要考虑查询字段的字段顺序，只有遵守这个原则才能最大的提高使用效率。
mysql会从左到右匹配，直到遇到范围查询（>,<,between, like）就停止匹配，比如联合索引（a,b,c,d）匹配a=1 and b=2 and c>2 and d=1,此时d字段是使用不到索引的功能的，如果这时索引的字段顺序是（abdc），此时d就会应用联合索引
如果判断条件“=”，那么不会强调字段的顺序，mysql的查询优化器会自动识别形式：a=1 and c=2 and b=2字段顺序a,b,c不做区别。
联合索引提高查询效率的原理。
MySQL会为InnoDB的每个表简建立聚集索引，如果表有索引会建立二级索引。聚集索引以主键建立索引，如果没有主键，以表中的唯一键建立，唯一键也会以隐式的创建一个字增的列来建立，聚集索引和二级索引都是一个B+树，B+树是数据按照一定顺序存在叶子节点且每页数据相连。
