MySQL索引

什么是索引

索引是一种数据结构，可以帮助我们快速查找数据 MySQL官方对索引的定义为:索引(index)是帮助MySQL高效获取数据的数据结构(有序)。在数据之外，数据 库系统还维护者满足特定查找算法的数据结构，这些数据结构以某种方式引用(指向)数据， 这样就可以在这些数 据结构上实现高级查找算法，这种数据结构就是索引。

索引都有哪些数据结构

索引可能有三种数据结构哈希表、有序数组和N叉树。MySQL索引使用的是B+树（InnoDB存储引擎）

索引的原理

索引的原理 一般来说，索引本身也很大，不可能全部存储在内存中，因此索引往往以索引文件的形式存储的磁盘上。这样的话，索引查找过程中就要产生磁盘I/O消耗，相对于内存存取，I/O存取的消耗要高几个数量级，所以评价一个数据结构作为索引的优劣最重要的指标就是在查找过程中磁盘I/O操作次数的渐进复杂度。 换句话说，索引的结构组织要尽量减少查找过程中磁盘I/O的存取次数。

索引底层是怎么实现的

Hash索引

哈希索引是采用一定的哈希算法，将键值换算成新的哈希值，映射到对应的槽位上，然后存储在hash表中。 如果两个或多个键值，映射到一个相同的槽位上，他们就会产生Hash冲突，也叫Hash碰撞，可以通过链表来解决。 Hash索引特点

优点： 查询效率高，在没有产生hash冲突的情况下，通常只需要一次检索就可以了，效率通常要高于B+树索引。 缺点： 1.Hash索引只能用于对等比较(=，in)，不支持范围查询(between，>，<,...），即无法进行大小比较 2.无法利用索引完成排序操作（Hash索引是无序排列的） 存储引擎支持 在MySQL中，支持hash索引的是Memory引擎，而InnoDB中具有自适应hash功能（利用方法将b+树索引转化为hash索引），hash索引是存储引擎根据B+Tree索引在指定条件下自动构建的。

二叉树索引

二叉树索引分为左子树，右子树，根节点，左子树要比根节点小，右子树要比根节点大

二叉树缺点：顺序插入时，会形成一个链表（如右图），查询性能大大降低。很多数据量的情况下，层次较深，检索速度慢。

平衡二叉树

特点： 它的左子树和右子树都是平衡二叉树 左子树比中间小，右子树比中间值大 左子树和右子树的深度之差的绝对值不超过1 缺点

缺点： a、插入操作需要旋转 b、支持范围查询，但回旋查询效率较低，比如要查找大于8的，会回旋到父节点7、10。 c、如果存放几百条数据的情况下，树高度越高，查询效率会越慢

B树（多路平衡查找树）

B树：叶子节点和非叶子节点都存储数据，数据结构为有序数组+平衡多叉树，也叫b-树。 m为树的叉数 每个节点最多有m-1个关键字(可以存有的键值对)。 根节点最少可以只有1个关键字。 非根节点至少有m/2个关键字。 每个节点中的关键字都按照从小到大的顺序排列，每个关键字的左子树中的所有关键字都小于它，而右子树中的所有关键字都大于它。 所有叶子节点都位于同一层，或者说根节点到每个叶子节点的长度都相同。每个节点都存有索引和数据，也就是对应的key和value。

b树优点： 二叉平衡树的基础上，使加载一次节点，可以加载更多路径数据，同时把查询范围缩减到更小 树的每一个节点都包含key和value。 所以，经常访问的元素可能离根节点更近，把频繁访问的数据放在靠近根节点的地方将会大大提高热点数据的查询效率。

缺点： 业务数据的大小可能远远超过了索引数据的大小，每次为了查找对比计算，需要把数据加载到内存以及 CPU 高速缓存中时，都要把索引数据和无关的业务数据全部查出来。本来一次就可以把所有索引数据加载进来，现在却要多次才能加载完。如果所对比的节点不是所查的数据，那么这些加载进内存的业务数据就毫无用处，全部抛弃。

B+树

以m阶B+树为例 一个m阶的B+树具有如下几个特征： 有k个子树的中间节点包含有k个元素（B树中是k-1个元素），每个元素不保存数据，只用来索引，所有数据都保存在叶子节点。 所有的叶子结点中包含了全部元素的信息，及指向含这些元素记录的指针，且叶子结点本身依关键字的大小自小而大顺序链接。 所有的中间节点元素都同时存在于子节点，在子节点元素中是最大（或最小）元素。

B+树只有叶子节点存储数据(B+数中有两个头指针：一个指向根节点，另一个指向关键字最小的叶节点)，叶子节点包含了这棵树的所有数据，所有的叶子结点使用链表相连，便于区间查找和遍历，所有非叶节点起到索引作用

B+树优于B树原因

b+树的中间节点不保存数据，可以容纳更多的节点元素 所有的叶子结点使用链表相连，有助于区间查找和遍历 B+树的内部节点只存放键，不存放值，因此，一次读取，可以在内存页中获取更多的键，有利于更快地缩小查找范围。 B+树的叶节点由一条链相连，因此，当需要进行一次全数据遍历的时候，B+树只需要使用O(logN)时间找到最小的一个节点，然后通过链进行O(N)的顺序遍历即可。而B树则需要对树的每一层进行遍历，这会需要更多的内存置换次数，因此也就需要花费更多的时间

B树的话，就需要进行每一层的递归遍历 相邻的元素可能在内存中不相邻，所以缓存命中性没有B+树好

什么是覆盖索引

索引是高效找到行的一个方法，但是一般数据库也能使用索引找到一个列的数据，因此它不必读取整个行。b+索引叶子节点存储了它们索引的数据；当能通过读取索引就可以得到想要的数据，那就不需要读取行了。一个索引包含了（或覆盖了）满足查询结果的数据就叫做覆盖索引。

1.覆盖索引是一种数据查询方式，不是索引类型 2.在索引数据结构中，通过索引值可以直接找到要查询字段的值，而不需要通过主键值回表查询，那么就叫覆盖索引 3.查询的字段被使用到的索引树全部覆盖到

举个栗子：

在上图中，id为主键索引，name为唯一索引 假如你执行命令

select id,name from eclass where id=1;

此时由于id和name字段都在索引树中，所以这就是覆盖索引查询

什么是聚簇索引

聚簇索引是物理索引，数据表就是按顺序存储的，物理上是连续的。 一般情况下主键会默认创建聚簇索引 将索引与数据放在一起，当你找到索引后，也就找到对应的数据了。每张表只能建立一个聚簇索引，但是该索引可以包含多个列（一般使用的是主键等不经常更新的列）

非聚簇索引：数据储存于索引分开，叶节点指向了对应的数据行。辅助索引访问数据时需要二次查找。辅助索引存储的不是行的物理位置，而是主键的值。而通过辅助索引首先找到的就是主键的值，再通过主键的值找到数据行对应的数据页，最后才能找到对应行。

联合索引

我们都知道索引的底层是一颗B+树，那么联合索引当然还是一颗B+树，只不过联合索引的健值数量不是一个，而是多个。构建一颗B+树只能根据一个值来构建，因此数据库依据联合索引最左的字段来构建B+树。使用联合索引，如果想要命中索引，需要按照建立索引时的字段顺序挨个使用，否则无法命中索引。。

最左匹配原则

顾名思义：最左优先，以最左边的为起点任何连续的索引都能匹配上。同时遇到范围查询(>、<、between、like)就会停⽌匹配。 mysql创建复合索引的规则是⾸先对复合索引最左边的字段的数据进⾏排序，在此基础上，再对后⾯的字段进⾏排序，这样第⼀个字段是绝对有序的，后⾯的字段就是⽆序的了，⼀般情况下第⼆个字段进⾏条件判断是⽤不到索引的，可能出现type是index类型的，这就是mysql 最左前缀的原因。 举个栗子：假设创建了顺序为（a，b，c）的索引 1.当查询条件为a=1 and b=1 或b=1 and a=1（查询优化器会调换a与b的位置），这时候都可以走索引。 当查询条件为a=1 and b>1 and c=1 时 ，由于是范围查找，a和b走索引，c不走索引

创建索引的原则

创建索引，肯定是有利于我们的查询效率的，如果无效地创建索引，只会浪费我们的内存和执行程序的效率，因此创建索引是有原则的

首先应考虑对where 和 order by 涉及到的列上建立索引 对一个存在大量更新操作的表，所建索引的数目一般不超过3个，最多不超过5个，索引虽说提高了访问速度，但太多索引会影响数据的更新操作,并且索引本身会占用存储空间。 建立唯一索引。唯一索引能够更快速地帮助我们进行数据定位； 为经常需要进行查询操作的字段建立索引； 更新频繁的列不宜设置索引，索引列不能参与计算 数据量小的表不要使用索引 重复数据多的字段不宜设置索引，如性别男和女。 在建立索引的时候，要考虑索引的最左匹配原则（在使用SQL语句时，如果where部分的条件不符合最左匹配原则，可能导致索引失效，或者不能完全发挥建立的索引的功效）； 如果建立的单个索引查询数据很多，查询得到的数据的区分度不大，则考虑建立合适的联合索引； 尽量考虑字段值长度较短的字段建立索引，如果字段值太长，会降低索引的效率

创建索引的优缺点

优点

1. 大大加快数据的查询速度
2. 使用分组和排序进行数据查询时，可以显著减少查询时分组和排序的时间
3. 创建唯一索引，能够保证数据库表中每一行数据的唯一性
4. 在实现数据的参考完整性方面，可以加速表和表之间的连接
5. 通过使用索引，可以在查询的过程中，使用优化隐藏器，提高系统的性能。

缺点

1. 创建索引和维护索引需要消耗时间并且随着数据量的增加，时间也会增加
2. 索引需要占据磁盘空间
3. 对数据表中的数据进行增加，修改，删除时，索引也要动态的维护，降低了维护的速度