学会MySQL的索引有这一篇文章就够啦！(MySQL索引原理和使用原则)
目录
3. 索引存储模型推演（索引数据结构 : B+树 (MySQL优化后的独特B+树结构)）
1.何为索引
数据库索引是数据库管理系统中排序的数据结构，用来协助快速查询，更新数据库表中的数据。
首先数据是以文件的形式存放在磁盘上面的，每一行数据都有它的磁盘地址。如果没有索引的话，要从500万行数据里面检索一条数据，只能依次遍历这张表的全部数据，直到找到这条数据。
但是有了索引之后，只需要在索引里面去检索这条数据就行了，因为它是一种特殊的专门用来快速检索的数据结构，我们找到数据存放的磁盘地址以后，就可以拿到数据了。
就像我们从一本500页的书里面去找特定的一小节的内容，肯定不可能从第一页开始翻。那么这本书有专门的目录，它可能只有几页的内容，它是按页码来组织的，可以根据拼音或者偏旁部首来查找，只要确定内容对应的页码，就能很快地找到我们想要的内容。
2. 索引分类
在InnoDB 里面，索引类型有三种，普通索引、唯一索引（主键索引是特殊的唯一索引）、全文索引。
普通（Normal）：也叫非唯一索引，是最普通的索引，没有任何的限制。
唯一（Unique）：唯一索引要求键值不能重复。另外需要注意的是，主键索引是一种特殊的唯一索引，它还多了一个限制条件，要求键值不能为空。主键索引用primaykey创建。
全文（Fulltext）：针对比较大的数据，比如我们存放的是消息内容，有几KB的数据的这种情况，如果要解决like查询效率低的问题，可以创建全文索引。只有文本类型的字段才可以创建全文索引，比如char、varchar、text。
3. 索引存储模型推演（索引数据结构 : B+树 (MySQL优化后的独特B+树结构)）
3.1二分查找
二分查找的一种思想，也叫折半查找，每一次，我们都把候选数据缩小了一半。如果数据已经排过序的话，这种方式效率比较高。所以第一个，我们可以考虑用有序数组作为索引的数据结构。有序数组的等值查询和比较查询效率非常高，但是更新数据的时候会出现一个问题，可能要挪动大量的数据（改变index，所以只适合存储静态的数据。
为了支持频繁的修改，比如插入数据，我们需要采用链表。链表的话，如果是单链表，它的查找效率还是不够高。
所以，有没有可以使用二分查找的链表呢？为了解决这个问题，BST（Binary SearchTree）也就是我们所说的二叉查找树诞生了。
3.2二叉查找树
二叉查找树的特点是什么？
左子树所有的节点都小于父节点，右子树所有的节点都大于父节点。投影到平面以后，就是一个有序的线性表。
二叉查找树既能够实现快速查找，又能够实现快速插入。
但是二叉查找树有一个问题：
就是它的查找耗时是和这棵树的深度相关的，在最坏的情况下时间复杂度会退化成O(n)。
还是刚才的这一批数字，如果我们插入的数据刚好是有序的，2、6、11、13、17。这个时候我们的二叉查找树变成了什么样了呢？
它会变成链表（我们把这种树叫做“斜树”），这种情况下不能达到加快检索速度的目的，和顺序查找效率是没有区别的。
造成它倾斜的原因是什么呢？
因为左右子树深度差太大，这棵树的左子树根本没有节点——也就是它不够平衡。所以，我们有没有左右子树深度相差不是那么大，更加平衡的树呢？
这个就是平衡二叉树，叫做Balanced binary search trees，或者AVL树（AVL 是发明这个数据结构的人的名字）。
3.3平衡二叉树
平衡二叉树的定义：左右子树深度差绝对值不能超过1。
是什么意思呢？比如左子树的深度是2，右子树的深度只能是1或者3。这个时候我们再按顺序插入1、2、3、4、5、6，一定是这样，不会变成一棵“斜树” 。
那它的平衡是怎么做到的呢？怎么保证左右子树的深度差不能超过1呢？
插入1、2、3。
我们注意看：当我们插入了1、2之后，如果按照二叉查找树的定义，3肯定是要在2的右边的，这个时候根节点1的右节点深度会变成2，但是左节点的深度是0，因为它没有子节点，所以就会违反平衡二叉树的定义。
那应该怎么办呢？因为它是右节点下面接一个右节点，右-右型，所以这个时候我们
要把2提上去，这个操作叫做左旋。
同理，右旋就是在插入7、6、5的时候，发生右旋。
所以为了保持平衡，AVL树在插入和更新数据的时候执行了一系列的计算和调整的操作。
平衡的问题我们解决了，那么平衡二叉树作为索引怎么查询数据？
在平衡二叉树中，一个节点，它的大小是一个固定的单位，作为索引应该存储什么内容？
它应该存储三块的内容：
第一个是索引的键值。比如我们在id上面创建了一个索引，我在用whereid=1的
条件查询的时候就会找到索引里面的id的这个键值。
第二个是数据的磁盘地址，因为索引的作用就是去查找数据的存放的地址。
第三个，因为是二叉树，它必须还要有左子节点和右子节点的引用，这样我们才能
找到下一个节点。比如大于26的时候，走右边，到下一个树的节点，继续判断。
但是如果这样存储，会有什么问题呢？
3.4InnoDB逻辑存储结构
MySQL的存储结构分为5级：表空间、段、簇、页、行、
重点分析页(Page):为了高效管理物理空间，对簇进一步细分，就得到了页。簇是由连续的页（Page）组成的空间，一个簇中有64个连续的页。 （1MB／16KB=64）。这些页面在物理上和逻辑上都是连续的。
跟大多数数据库一样，InnoDB也有页的概念（也可以称为块），每个页默认16KB。页是InnoDB存储引擎磁盘管理的最小单位，通过innodb_page_size设置。一个表空间最多拥有2^32个页，默认情况下一个页的大小为16KB，也就是说一个表空间最多存储64TB的数据。
注意，文件系统中，也有页的概念。操作系统和内存打交道，最小的单位是页Page。文件系统的内存页通常是4K。
假设一行数据大小是1K，那么一个数据页可以放16行这样的数据。
举例：一个页放3行数据。
往表中插入数据时，如果一个页面已经写完，产生一个新的叶页面。如果一个簇的所有的页面都被用完，会从当前页面所在段新分配一个簇。如果数据不是连续的，往已经写满的页中插入数据，会导致叶页面分裂.
3.5平衡二叉树用于存储数据问题
当我们用树的结构来存储索引的时候，访问一个节点就要跟磁盘之间发生一次IO。
InnoDB操作磁盘的最小的单位是一页（或者叫一个磁盘块），大小是16K(16384字节)。那么，一个树的节点就是16K的大小。
如果我们一个节点只存一个键值+数据+引用，例如整形的字段，可能只用了十几个或者几十个字节，它远远达不到16K的容量，所以访问一个树节点，进行一次IO的时候，浪费了大量的空间。
所以如果每个节点存储的数据太少，从索引中找到我们需要的数据，就要访问更多的节点，意味着跟磁盘交互次数就会过多。
如果是机械硬盘时代，每次从磁盘读取数据需要10ms左右的寻址时间，交互次数越多，消耗的时间就越多
3.6多路平衡查找树(B Tree)(分裂，合并)
Balanced Tree
这个就是我们的多路平衡查找树，叫做B Tree（B代表平衡）。跟AVL树一样，B树在枝节点和叶子节点存储键值、数据地址、节点引用。
它有一个特点：分叉数（路数）永远比关键字数多1。比如我们画的这棵树，每个节点存储两个关键字，那么就会有三个指针指向三个子节点。
B Tree的查找规则是什么样的呢？
比如我们要在这张表里面查找15。
因为15小于17，走左边。
因为15大于12，走右边。
在磁盘块7里面就找到了15，只用了3次IO。
这个是不是比AVL 树效率更高呢？
那BTree又是怎么实现一个节点存储多个关键字，还保持平衡的呢？跟AVL树有什么区别？
比如MaxDegree（路数）是3的时候，我们插入数据1、2、3，在插入3的时候，本来应该在第一个磁盘块，但是如果一个节点有三个关键字的时候，意味着有4个指针，子节点会变成4 路，所以这个时候必须进行分裂。把中间的数据2提上去，把1和3变成2的子节点。
如果删除节点，会有相反的合并的操作。
注意这里是分裂和合并，跟AVL树的左旋和右旋是不一样的。我们继续插入4和5，B Tree又会出现分裂和合并的操作。
从这个里面我们也能看到，在更新索引的时候会有大量的索引的结构的调整，所以解释了为什么我们不要在频繁更新的列上建索引，或者为什么不要更新主键。节点的分裂和合并，其实就是InnoDB页的分裂和合并。
3.7B+树
B Tree 的效率已经很高了，为什么 MySQL 还要对 B Tree 进行改良，最终使用了B+Tree呢？
总体上来说，这个B树的改良版本解决的问题比B Tree更全面。我们来看一下InnoDB里面的B+树的存储结构。
MySQL中的B+Tree有几个特点：
1、它的关键字的数量是跟路数相等的；
2、B+Tree的根节点和枝节点中都不会存储数据，只有叶子节点才存储数据。搜索到关键字不会直接返回，会到最后一层的叶子节点。比如我们搜索 id=28，虽然在第一层直接命中了，但是全部的数据在叶子节点上面，所以我还要继续往下搜索，一直到叶子节点。
3、B+Tree的每个叶子节点增加了一个指向相邻叶子节点的指针，它的最后一个数据会指向下一个叶子节点的第一个数据，形成了一个有序链表的结构。
4、它是根据左闭右开的区间 [ )来检索数据。总结一下，InnoDB中的B+Tree的特点：
1)它是BTree的变种，BTree能解决的问题，它都能解决。BTree解决的两大问题是什么？（每个节点存储更多关键字；路数更多）
2)扫库、扫表能力更强（如果我们要对表进行全表扫描，只需要遍历叶子节点就可以
了，不需要遍历整棵B+Tree拿到所有的数据）
3)B+Tree的磁盘读写能力相对于BTree来说更强（根节点和枝节点不保存数据区，
所以一个节点可以保存更多的关键字，一次磁盘加载的关键字更多）
4)排序能力更强（因为叶子节点上有下一个数据区的指针，数据形成了链表）
5)效率更加稳定（B+Tree永远是在叶子节点拿到数据，所以IO次数是稳定的）
4.B+Tree落地形式
MySQL创建表的时候，会按照要求设定对应的存储引擎，在我们创建表以后，会生成对应的表文件，在这里我们能看到，每张InnoDB 的表有两个文件（.frm和.ibd），MyISAM的表有三个文件（.frm、.MYD、.MYI）。
有一个是相同的文件，.frm。 .frm是MySQL里面表结构定义的文件，不管你建表的时候选用任何一个存储引擎都会生成。
4.1MySAM
在MyISAM里面，另外有两个文件：一个是.MYD文件，D代表Data，是MyISAM的数据文件，存放数据记录，比如我们的user_myisam表的所有的表数据。一个是.MYI文件，I代表Index，是MyISAM的索引文件，存放索引，比如我们在id字段上面创建了一个主键索引，那么主键索引就是在这个索引文件里面。也就是说，在MyISAM里面，索引和数据是两个独立的文件。那我们怎么根据索引找到数据呢？MyISAM的B+Tree 里面，叶子节点存储的是数据文件对应的磁盘地址。所以从索引文件.MYI中找到键值后，会到数据文件.MYD中获取相应的数据记录。
这里是主键索引，如果是辅助索引，有什么不一样呢？
在MyISAM里面，辅助索引也在这个.MYI文件里面。辅助索引跟主键索引存储和检索数据的方式是没有任何区别的，一样是在索引文件里面找到磁盘地址，然后到数据文件里面获取数据
4.2InnoDB
InnoDB只有一个文件（.ibd文件），那索引放在哪里呢？
在InnoDB 里面，它是以主键为索引来组织数据的存储的，所以索引文件和数据文件是同一个文件，都在.ibd文件里面。
在InnoDB的主键索引的叶子节点上，它直接存储了我们的数据。
什么叫做聚集索引（聚簇索引）？
就是索引键值的逻辑顺序跟表数据行的物理存储顺序是一致的。（比如字典的目录是按拼音排序的，内容也是按拼音排序的，按拼音排序的这种目录就叫聚集索引）。
在InnoDB里面，它组织数据的方式叫做叫做（聚集）索引组织表（clusteredindexorganize table），所以主键索引是聚集索引，非主键都是非聚集索引。
如果InnoDB里面主键是这样存储的，那主键之外的索引，比如我们在name字段上面建的普通索引，又是怎么存储和检索数据的呢？
InnoDB中，主键索引和辅助索引是有一个主次之分的。
辅助索引存储的是辅助索引和主键值。如果使用辅助索引查询，会根据主键值在主键索引中查询，最终取得数据。
为什么在辅助索引里面存储的是主键值而不是主键的磁盘地址呢？如果主键的数据类型比较大，是不是比存地址更消耗空间呢？
我们前面说到B Tree是怎么实现一个节点存储多个关键字，还保持平衡的呢？是因为有分叉和合并的操作，这个时候键值的地址会发生变化，所以在辅助索引里面不能存储地址。
另一个问题，如果一张表没有主键怎么办？
1、如果我们定义了主键(PRIMARY KEY)，那么InnoDB会选择主键作为聚集索引。
2、如果没有显式定义主键，则InnoDB会选择第一个不包含有NULL值的唯一索引作为主键索引。
3、如果也没有这样的唯一索引，则InnoDB会选择内置6字节长的ROWID作为隐藏的聚集索引，它会随着行记录的写入而主键递增。
5.索引的使用原则
5.1 列的离散度
第一个叫做列的离散度，我们先来看一下列的离散度的公式：count(distinct(column_name)) : count(*)，列的全部不同值和所有数据行的比例。
数据行数相同的情况下，分子越大，列的离散度就越高。
简单来说，如果列的重复值越多，离散度就越低，重复值越少，离散度就越高。
如果在B+Tree里面的重复值太多，MySQL的优化器发现走索引跟使用全表扫描差不了多少的时候，就算建了索引，也不一定会走索引。
这个给我们的启发是什么？建立索引，要使用离散度（选择度）更高的字段。
5.2联合索引的最左匹配
前面我们说的都是针对单列创建的索引，但有的时候我们的多条件查询的时候，也会建立联合索引。单列索引可以看成是特殊的联合索引。
比如我们在user表上面，给name和phone建立了一个联合索引。
联合索引在B+Tree中是复合的数据结构，它是按照从左到右的顺序来建立搜索树的（name在左边，phone在右边）。
从这张图可以看出来，name是有序的，phone是无序的。当name相等的时候，phone才是有序的。这个时候我们使用where name='张三' and phone = '124XXXX'去查询数据的时候，B+Tree 会优先比较 name 来确定下一步应该搜索的方向，往左还是往右。如果 name相同的时候再比较phone。但是如果查询条件没有name，就不知道第一步应该查哪个节点，因为建立搜索树的时候name是第一个比较因子，所以用不到索引。
5.3覆盖索引
在了解覆盖索引的时候首先要明确几个概念。
回表：
非主键索引，我们先通过索引找到主键索引的键值，再通过主键值查出索引里面没有的数据，它比基于主键索引的查询多扫描了一棵索引树，这个过程就叫回表。
在辅助索引里面，不管是单列索引还是联合索引，如果select的数据列只用从索引中就能够取得，不必从数据区中读取，这时候使用的索引就叫做覆盖索引，这样就避免了回表。
6.索引的创建和使用
因为索引对于改善查询性能的作用是巨大的，所以我们的目标是尽量使用索引。
6.1索引的创建
1、在用于where判断order排序和join的（on）字段上创建索引
2、索引的个数不要过多。——浪费空间，更新变慢。
3、区分度低的字段，例如性别，不要建索引。——离散度太低，导致扫描行数过多。
4、频繁更新的值，不要作为主键或者索引。——页分裂
5、组合索引把散列性高（区分度高）的值放在前面。
6、创建复合索引，而不是修改单列索引。
9、无序的值不建议作为索引
6.2什么时候用不到索引
1、索引列上使用函数（replace\SUBSTR\CONCAT\sum count avg）、表达式、
计算（+ - * /）：
2、字符串不加引号，出现隐式转换
3、like条件中前面带%
4、负向查询 NOT LIKE 不能：!= （<>）和NOT IN 在某些情况下可以：
注意：一个SQL语句是否使用索引，跟数据库版本、数据量、数据选择度都有关系。