索引到底是什么

索引是帮助Mysql高效获取数据的一种数据结构

索引储存在哪里

和数据一样，索引以文件形式储存在硬盘上，在MyISAM储存引擎中，数据和索引文件试试分开储存的。

MyISAM文件储存示意图

在InnoDB中，数据和索引文件是合起来储存的，注意下图中没有了I（index）结尾的文件。

InnoDB文件储存示意图
后面会进一步分析为什么会这样

索引的数据结构

想想JDK8的Hashmap中，当链表长度大于一定限度时，为了能够高效的检索数据，引入了红黑树。索引的思想也是这样，通过一种数据结构高效的数据结构来加速数据检索的过程。
想想以下这几种常用的数据结构可否用于索引呢？
1. BST
2. 红黑树
3. Hash

BST在节点有序的情况下会变成一种线性结构，复杂度退化到O(n)，显然是不行的。
红黑树解决了平衡的问题，但是在数据量比较大的情况下，红黑树的高度太高，导致磁盘IO次数过多，也不够合理。
Hash似乎解决了磁盘IO的问题，但是Hash有大量冲突的时候还是线性遍历，最关键的是限制太多，例如无法支持范围查询，也不支持部分索引匹配。

B+树

B-树 B+树

比起红黑树，上面两种数据结构都更加矮胖。他们两之间一个很大的不同是B+树的节点上不储存value，只储存key，而叶子节点上储存了所有kv集合，并且节点之间都是有序的。

这样的好处是每一次磁盘IO能够读取的节点更多，也就是树的度可以设置的更大一些，因为每次磁盘IO读取的磁盘页数是一定的，例如每次磁盘IO能够读取1页=4kb，那么省去value的情况下同样一页数据能够读取更多的key，这样就大大减少了磁盘的IO次数。

此外，B+树是排序好的数据结构，数据库中><或者order by等都可以直接依赖这一特性。

MyISAM索引实现（非聚集索引）

MyISAM中索引和数据是分开储存的，并且主键索引和辅助索引（二级索引）的储存方式是一样的。

主键索引 辅助索引

InnoDB索引实现（聚集索引）

InnoDB中索引文件和数据文件是同一个文件。并且主键索引和二级索引储存方式有所不同，如图所示，二级索引的叶子节点不储存数据，仅储存主键ID。

主键索引 辅助索引

这里思考两个问题

1. InnoDB表中必然有主键，为什么最好一定是有序自增id？
2. 为什么二级索引叶子节点储存的是主键值？

问题一：如果id是无序的，那么很有可能新插入的值会导致当前节点分裂，此时MySQL不得不为了将新记录插到合适位置而移动数据，甚至目标页面可能已经被回写到磁盘上而从缓存中清掉，此时又要从磁盘上读回来，这增加了很多开销，同时频繁的移动、分页操作造成了大量的碎片，得到了不够紧凑的索引结构，后续不得不通过OPTIMIZE TABLE来重建表并优化填充页面。
反之，如果每次插入有序，那就会在当前页后面连续写入，写不下就会重新分配一个节点，内存都是连续的，这样效率自然也就最高了。

问题二：如果二级索引储存的也是数据，那么每次插入mysql都不得不更新每棵索引树，这样就加剧了新增编辑时的性能损耗，并且这样一来空间利用率也不高，产生了大量冗余数据。

联合索引

联合索引底层数据结构长什么样？

联合索引示意

比较相等时，先比较第一列的值，如果相等，再继续比较第二列，以此类推。

最左前缀原理

使用联合索引时，索引列的定义顺序将会影响到最终查询时索引的使用情况。例如联合索引（a,b,c），mysql会从最左边的列优先匹配，如果最左边的带头大哥没有使用到，在未使用覆盖索引的情况下，就只能全表扫描。
联合底层数据结构思考，mysql会优先以联合索引第一列匹配，此后才会匹配下一列，如果不指定第一列匹配的值，也就无法得知下一步查询哪个节点。
另外还有一种情况，如果遇到 > < between等这样的范围查询，那B+树中也就无法对下一列进行等值匹配了。