三、数据库索引

1、索引介绍

索引是一种用于快速查询和检索数据的数据结构，其本质可以看成是一种排序好的数据结构。

常见的索引结构有：B数，B+树，Hash和红黑树等。在MySQL中，无论是 InnoDB还是MyISAM，都使用了B+树作为索引结构。

索引的优缺点是什么？

优点：

• 使用索引可以大大加快数据的检索速度（减少检索量）
• 通过创建唯一索引，可以保证数据库表中每一行数据的唯一性

缺点：

• 创建索引和维护索引需要耗费时间
• 索引需要使用物理文件存储，会耗费一定的空间
• 大部分情况下，索引查询都是比全表扫描要快的，但是如果数据库的数据量不大，那么使用索引也不一定能够带来很大提升

2、索引底层数据结构选型

Hash表

哈希表是键值对的集合，通过键（key）即可快速取出对应的值（value），因此哈希表可以快速检索数据。

为何能通过key快速取出value？这是因为哈希算法，通过哈希算法，我们可以快速找到key对应的index，找到了桶的位置也就找到了对应的value。

但是哈希算法有Hash冲突的问题，多个不同的key经过哈希算法可能得到的index相同，这就产生哈希碰撞，常用的解决方法是链地址法，通过将数组的每一个元素作为一个链表，将哈希冲突数据存储在链表。

MySQL的InnoDB存储引擎不直接支持常规的哈希索引，但是InnDB中存在一种特殊的“自适应哈希索引”，自适应哈希索引并不是传统意义上的纯哈希索引，而是结合了B+ Tree 和哈希索引的特点，以便更好地适应实际应用中的数据访问模式和性能需求。即哈希数组中每个哈希桶实际是一个小型的B+Tree结构，这个B+Tree结构可以存储多个键值对，而不仅仅是一个键，这有助于减少哈希冲突链的长度，提高索引的效率

既然哈希表检索数据这么快，为什么MySQL没有使用它作为索引的数据结构呢？主要因为Hash索引不支持顺序和范围查询 。例如，对于查询 id<500的数据，这种范围查询，如果是用二叉树，直接遍历比500小的叶子节点就可以，但是Hash索引是根据Hash算法来定位，需要对1-499的数据都进行一次hash计算，来获取每个位置的value

二叉查找树

二叉查找树是一种基于二叉树的数据结构：

• 左子树所有节点的值均小于根节点的值
• 右子树所有节点的值均大于根节点的值’
• 左右子树也分别为二叉查找树

当二叉查找树是平衡的时候，查询的时间复杂度为O（log2（N）），具有比较高的效率；但是如果二叉查找树不平衡时，最坏的情况就是当有序插入节点，树就退化成了线性链表，查询效率急剧下降，时间复杂度退化为O（N）

二叉查找树的性能非常依赖于它的平衡程度，这就导致其不适合作为MySQL底层索引的数据结构

AVL树

自平衡二叉查找树。AVL树的特点是保证任何节点的左右子树高度之差不超过1 ，因此也被称为高度平衡二叉树，它的查找、插入和删除在平均和最坏情况下的时候复杂度都是O（log n）

AVL树采用了旋转操作来保持平衡，主要有4种旋转操作：LL旋转，RR旋转，LR旋转，RL旋转。由于AVL树需要频繁地进行旋转操作来保持平衡，因此会有较大的计算开销进而降低了查询性能。并且，在使用AVL树时，每个树节点仅存储一个数据，而每次进行磁盘IO时只能读取一个节点的数据，如果需要查询的数据分布在多个节点上，就意味着要进行多次磁盘IO，而磁盘IO是一项耗时的操作。

由于旋转的耗时，AVL树在删除数据时效率很低，在删除操作较多时，维护平衡所需的代价可能高于其带来的好处，所以实际情况AVL树使用的并不多

红黑树

红黑树是一种自平衡二叉查找树，通过在插入和删除节点时进行颜色变换和旋转操作，使树始终保持平衡状态：

• 每个节点非红即黑
• 根节点总是黑色的
• 每个叶子节点都是黑色的空节点
• 如果节点是红色的，则它的字节点必须是黑色
• 从根节点到叶节点的每条路径，必须包含相同数目的黑色节点（即相同的黑色高度）

和AVL树不同的是，红黑树并不追求严格的平衡，而是大致的平衡。红黑树的查询效率稍有下降，因为红黑树的平衡性相对较弱，可能会导致树的高度较高，这可能会导致一些数据需要进行多次磁盘IO操作才能查询到，这也是MySQL没有选择红黑树的原因 。红黑树的插入和删除操作效率大大提高了，因为红黑树在插入和删除节点时只需进行O（1）次数的旋转和变色操作，即可保持基本平衡状态。

红黑树的应用很广泛：TreeMap，HashMap等底层都使用到了红黑树，对于数据在内存 这种情况来说，红黑树的表现还是非常优异的；但是对于数据在磁盘等辅助存储设备中的情况 ，红黑树并不好用，因为红黑树长得还是太高了，当数据在磁盘时，磁盘IO会成为最大的性能瓶颈，设计的目标应该是尽量减少IO此时，而树的高度越高，增删改查所需要的IO次数越多，会严重性能

B树&B+树

B树

B树全称为多路平衡查找树 ，B+树是B树的一种变体。

定义B树最重要的概念是阶数，对于一颗m阶B树，需要满足以下条件：

• 每个节点最多包含m个子节点
• 如果根节点包含子节点，则至少包含2个子节点；除根节点外，每个非叶节点至少包含m/2个子节点
• 拥有k个子节点的非叶子节点将包含k-1条记录
• 所有叶节点都在同一层

B树的优势除了树的高度小，还有对访问局部性原理的利用。所谓局部性原理，是指当一个数据被使用时，其附近的数据有较大概率在短时间内被使用。B树将键相近的数据存储在同一个节点，当访问其中某个数据时，数据库会将该整个节点读到缓存中 ；当它临近的数据紧接着被访问时，可以直接在缓存中读取，无需进行磁盘IO，B树的缓存命中率更高

MongoDB的索引使用的就是B树。

B树和B+树的区别

• B树的所有节点既存放键也存放数据，而B+树只有叶子节点会存放键和数据，其他节点只存放key

• B树的叶子节点是独立的；B+树的叶子节点有一条引用链指向与它相邻的叶子节点

• B树的检索的过程相当于对范围内的每个节点的关键字做二分查找，可能还没到达叶子节点，检索就结束了；B+树的检索效率很稳定，任何查找都是从根节点到叶子节点的过程

• B树中进行范围查询时，首先找到要查找的下限，然后对B树进行中序遍历，直到找到查找的上限；而B+树的范围查询，只需要对链表进行遍历即可

• B树：一个节点中可以有很多个元素，元素是有序的

• B+树：一个节点中可以有很多个元素；有序的；叶子节点之间有指针指向相邻的叶子节点；非叶子节点的元素都会冗余一份在叶子节点；

在MySQL官网中，是这么介绍的：

将节点比作是page（事实上也确实是以页为单位），root page point to the leaf pages ; leaf pages can also point to each other ，根节点会指向叶子节点，叶子节点之间也会有指针指向彼此（双向的指针 ）

B+树与B树相比，具备更少的IO次数，更稳定的查询效率和更适合范围查询这些优势

为什么B+树索引能加快访问的速度？

因为存储引擎不再需要进行全表扫描来获取需要的数据，取而代之的是从索引的根节点开始进行搜索，根节点的槽中存放指向子节点的指针，存储引擎根据这些指针向下层查找。

什么时候用B+树索引？

B+树索引适用于全键值、键值范围或者键前缀查找 。其中键前缀查找只适用于最左前缀的查找。

B+树索引和哈希索引的明显区别是？

如果是等值索引，那么哈希索引明显有绝对优势，因为只需要经过一次哈希算法即可找到相应的键值；前提是键值都是唯一的，如果键值不是唯一，需要先找到该键所在位置，然后根据链表往后扫描，直到找到相应的数据

如果是范围索引，哈希索引就没有用了。因为原先是有序的键值，经过哈希算法后，有可能变成不连续的了，就没办法再利用索引完成范围查询检索；

哈希索引也没办法利用索引完成排序，以及like‘xxx%’这样的部分模糊查询（这本质上其实也是范围查询）

B+树索引的关键字检索效率比较平均，在有大量重复键值情况下，哈希索引的效率也是很低的，因为有哈希碰撞的问题。

在MySQL中，只有 HEAP / MEMORY 引擎表才能显式的支持哈希索引，在HEAP表中，如果存储的数据重复度很低，对该列数据以等值查询为主，没有范围查询、没有排序 ，特别适合采用哈希索引

InnoDB引擎则是采用B+树的索引结构。这也是大部分数据库引擎的索引结构。B+树索引适用于绝大数场景。

3、InnoDB中的B+树是怎么产生的？

• InnoDB中一页多大：InnoDB_page_size = 16384 ~ 差不多16kb
• InnoDB存数据时，先要在内存中开辟至少一页的内存（16kb），然后当要存入磁盘时，是一页一页的存；从磁盘里读取数据时，也是一页一页的读；使用page这样的逻辑单位，可以减少io次数，提高查询效率
• 当插入多条数据时，即便没有设置主键自增，不按主键大小顺序插入时，查询到的所有数据的结果却发现是按照主键递增的顺序返回结果 ，这是为什么？

因为InnoDB在插入数据时就会进行排序。当插入用户数据时，会根据主键的大小按照递增的顺序来插入到用户数据区域，形成一个链表，这样的好处是**当下次查询一个元素时，可以通过比较大小很快确定元素在的位置，不用遍历全部的元素 ** ，但是插入的效率会有所降低；因此用innoDB时，建议设置主键自增，这样会优化插入性能。非自增的话，每次插入都要比较id来插入到数据区域，经常要打乱原来的顺序，这样性能肯定会下降。

InnoDB中的B+树的产生

接回上面，当用户数据区域链表越来越长时，这时候查询效率就会变的很低，如何解决呢？InnoDB的优化策略是加上一个页目录，页目录是将用户数据区域分组，“组长”便是这组中主键值最小的，将它放入到页目录中，这样就将用户数据区域分为一组一组的，当再次查询数据时，先查页目录，和页目录中的值比较大小以确认在哪个分组，然后在数据区域里找到数据 ；如下图：

当这一页都插满了之后，就会再开辟一页，然后继续按照这样的数据结构来排序，这一页其实就是一个节点 。页与页之间会有指针指向下一页，如下图：

当数据非常多，开辟的页（节点）也越来越多，这个时候又形成一个很长很长的页链表，InnoDB同样选择再加一层来进行优化。再分出一层来存储页的分组。将每一页的页目录的最小值存在新加的一层，当查询数据时，从上往下查，减少遍历次数，提高查询效率！

看得出，这其实就演变成了一颗B+树。这是一个两层的B+树，同理，当数据越来越多，继续往上面加层数！每一页就是一个leaf page ，上面的是root page 。这样就解释了为什么MySQL官网中将节点叫做页，因为页才是最恰当的。同样，这也解释了为什么非叶子节点的元素的值都会在叶子节点冗余一份，因为根节点的值就是取自于叶子节点，查询时从上往下，不断确定分组–确定页。

4、InnoDB如何支持范围查找能走索引？

• 叶子节点存储的是完整数据（称为数据页 ），而非叶子节点存储的是索引（称为索引页 ），如上面生成B+树的例子中，存的是主键索引。找到了索引也就找到了数据，这就是聚簇索引 ，主键索引就是一种聚簇索引，一般情况下，主键会默认创建聚簇索引，且一张表只能有一个聚簇索引。
• 当查询时根据的字段是索引时，是从上往下查询，走索引的，可以迅速确定到页，然后找到数据，这样会非常的快就能查找到数据

非范围查询，如 select * from user where id = 6 ; 根据索引页直接找到id=6在哪一页，然后找到数据

范围查询，如 select * from user where id > 6;先执行id=6时的操作，利用索引，然后在数据页中，大于就往右走小于就往左走----这就是为什么说数据页之间是双向链表 。因此根据索引范围查询也是走索引的

• 而当查询的字段根据的是非索引字段时，不能从索引页查，而是从叶子节点（数据页）查找 ，一条一条的遍历—这称为全表扫描
• 因此对于经常要查询的字段建议加上索引，能极大的提高查询速度

5、为什么要遵守最左前缀原则才能利用到索引？

• 什么是最左前缀匹配原则？

最左前缀匹配原则是指，在使用联合索引时，MySQL会根据联合索引中的字段顺序，从左到右依次到查询条件中去匹配，如果查询条件中存在 与联合索引中最左侧字段相匹配的字段，就会使用该字段过滤一批数据，直至联合索引中全部字段匹配完成。所以与where语句后面的查询字段的顺序没有关系，是根据联合索引里从最左边的字段来看查询条件里有没有相匹配的字段

• 在使用联合索引时，B+树的存储时这样的，这也叫作非聚簇索引（辅助索引）

用InnoDB时，建议用主键自增，这样会优化插入性能。非自增的话，每次插入都要比较id来插入到数据区域，经常要打乱原来的顺序，这样性能肯定会下降。

例如现在联合索引的字段是（a，b，c），那么索引页存储的是联合字段的值 ，数据页存储的是 联合索引字段的值和主键值 。这样的目的是什么呢？

当查询 select * from user where （a=1and b=1and c=1）时，先根据索引页找到索引为111的页，然后在数据页中，根据主键1，回表到主键索引表中的数据页找到这条数据行。辅助索引访问数据总是需要二次查找，第一次找到主键值，第二次根据主键值找到具体的数据行

那么为什么不遵循最左前缀原则就会导致索引失效（用不上索引）？

不遵循最左前缀原则，其实就是你给的查询条件的字段都不匹配联合索引的最左的字段。也就是说，当联合索引是（a，b，c）时，你的查询条件里没有根据a字段，例如（b，c），这时是无法从索引页开始查找的，因为是从联合索引的第一个字段开始查询，而第一个字段就不匹配，就走不了索引页了 ，只能从数据页一条一条查找–全表扫描。

注意：查询条件的字段顺序和联合索引的字段顺序不一致是没有关系的 ，因为是根据联合索引的字段开始从最左端匹配，只要提供了联合索引最左端得到字段，就遵循了最左前缀原则

6、为什么范围查找会导致索引失效？

对于查询，并不一定就是走索引快。

例如联合索引（b，c ，d），现在要查找 select * from user where b>1。如果从索引开始找可不可以呢？当然可以，这是遵循最左原则。查找时，先从索引页开始找，找到b=1的，然后到数据页，找b>1的主键的值，然后回表查询 这些主键所对应的数据的全部字段。这样一定是最快的吗？要知道，任何查询都有一种方式是全表查询，在这个查询情况下，如果直接全表查询，就是将所有的数据页一页一页的遍历，遍历完就能查询到，在这种情况，全表查询效率要比索引查询还快，因此索引就失效了，InnoDB会选择走全表查询

所以是否走索引要根据情况而定，并不是什么时候走索引都是最快的

范围查找时给的查询条件更精确一点，利用索引会更快！

7、覆盖索引是什么

例子还是上面的，联合索引（b，c，d），当查询条件为 select b from user where b>1;

对于这样的查询，走索引的话，先从索引页找到b=1，然后在数据页中找到b>1的页，这个时候，因为我们要查找的是b ，而不是要所有。而b字段的值就是在数据页中保存，不需要通过主键去主键索引里回表查询，直接就能查找到b>1的b的数据，这就是覆盖索引。这样是很快的。如果select a 呢？也是覆盖索引！a是主键，在数据页中存的是主键的值和联合索引的值，因此查a的话也不需要去回表，可以直接查找到，这就是覆盖索引。（不需要二次回表查询 ）

当查询语句为select b from user; 这种情况数据库又是如何查询的呢？

没有查询条件，那么是不是就一定不用索引走全表扫描？其实不是的。InnoDB会比较性能。第一种当然就是全表扫描，扫描主键索引的叶子节点，一页一页的扫描，然后将字段b的所有数据查询出来；第二种，是在（b,c,d）联合索引中，叶子节点存储的联合索引的值和主键值，扫描联合索引的叶子节点同样可以将b的所有数据查询到。但是联合索引中的叶子节点保存的是不完整的字段—只有联合索引字段和主键 ，而主键索引的叶子节点保存的是完整的数据 ，那么联合索引的叶子节点相比主键索引页数会更少，查询当然会更快。因此，这种情况下，InnoDB依旧是走索引查询–bcd联合索引。

8、order by 为什么会导致索引失效？

当查询语句为 select * from user order by (b,c,d);

一样的，会有两种走法，比较性能然后选择性能高的：

• 走全表扫描—主键索引的叶子节点，需要额外排序，但是不用回表
• 走索引扫描—联合索引（b,c,d）的叶子节点，因为没有where查询，所以不能从上往下，只能扫描叶子节点。此时是不需要排序的，因为叶子节点就是按照索引排序的，但是因为查询的是*，需要回表查询，找到相应的主键然后回表查出所有数据，八条数据就需要回八次表！

那么哪种更快呢？当数据量少的时候，显然全表扫描会更快一点，虽然要额外排序但是因为数据少，所以排序的时间非常短，和回八次表相比是很微小的，因此这种情况InnoDB也会选择走全表扫描，索引失效

但是当改为 select b from user order by (b,c,d);

这个时候，全表扫描还是像上面那样的步骤；但是索引扫描就省去了回表这一操作，所以肯定会走索引

需要二次回表的话直接走全表会更快；而不需要二次回表，走索引更快！

9、关于字段的数据类型转换导致索引失效

int a

varchar b

a是主键，现在建立b的索引

select * from user where a = 1；—会走索引

select * from user where b = “1”；—会走索引

select * from user where a = “1”；—会走索引

select * from user where b = 1；—不会走索引

对于第一种和第二组当然没问题，会走索引，a是int类型，查询a=1的数据，走主键索引；b是字符串类型，查询b=“1”的数据，走b索引；

而对于第三种情况，a是int类型，现在查询条件是有没有a等于一个字符串的数据，这个时候，InnoDB会将“1”转化为数值类型的1 ，然后查询a=1，所以也会走主键索引；

对于第四种情况，同样要将字符转换为数值，这里要做的是把这个“字段”转化为从varchar转换为int，如何把字段转化为数值呢，需要把b字段的所有字符数据都转换为int类型 ，这可不是一个小工程，是很难办到的，并且会改变索引的b+树，因为b索引的b+树里存的是字符，现在要改为对于的int数字，这样显然是非常耗内存和性能的。因此InnoDB走的是全表扫描，不走索引。

在InnoDB中，涉及对字段进行操作（包括查询条件包含a+1之类的字段操作），都会导致用不了索引

10、MySQL聚簇索引和非聚簇索引的区别

都是B+树的数据结构。

聚簇索引

• 聚簇索引：将数据存储和索引放在一起，如根节点（索引页）放索引，叶子节点（数据页）放数据 ，并且是按照顺序组织，找到索引也就找到了数据，数据的物理存放顺序与索引顺序是一致的。即：只要索引是相邻的，那么对应的数据一定是相邻地存放在磁盘上的。主键索引就是聚簇索引 ，InnoDB一定有主键—如果不主动设置，则会使用unique索引，没有unique索引则会使用数据库内部的一个行的隐藏id（DB_ROW_ID）来当做主键索引。

优势：

查询通过聚簇索引可以直接获取数据，相比非聚簇索引需要二次查询效率（没有索引覆盖的情况）更高

聚簇索引对于范围查询的效率更高，因为其数据是按照大小排列的

聚簇索引适合用在排序的场合

劣势：

依赖于有序的数据：因为B+树是多路平衡树，如果索引的数据不是有序的，那么就需要在插入时排序，如果数据是整型还好，如果是类似于字符串或UUID这种又长又难比较的数据，插入或查找的速度会非常慢

更新代价大：如果对索引列的数据修改时，那么对应的索引也将会被修改，而且聚簇索引的叶子节点还存放着数据，修改代价很大。所以对于主键索引来说，主键一般都是不可修改的。

维护索引很昂贵，特别是插入新行或者主键被更新导致要分页的时候

非聚簇索引

• 非聚簇索引：也叫作辅助索引，索引结构和数据分开放。叶子节点存储的不是数据，而是数据行的地址（存储索引和主键 ），根据索引查找到数据行再根据数据行的位置去磁盘查找数据。即先根据索引找到叶子节点中的位置，然后根据主键回表（主键索引）查询。这种相当于是建立在主键索引之上，因此也叫作辅助索引。MySQL的MyISAM引擎，不管是主键还是非主键，使用的都是非聚簇索引

• 优点：

更新代价比聚簇索引要小，因为非聚簇索引的叶子节点并不存放数据

• 缺点：

依赖于有序的数据：跟聚簇索引一样，非聚簇索引也依赖于有序的数据。

二次回表，当查到索引对应的指针或主键后，需要根据指针或主键再到数据文件或表中查询。（回表查询）

11、正确使用索引

1、选择合适的字段创建索引

• 不为NULL的字段：索引字段的数据应该尽量不为NULL，因为对于数据为NULL的字段，数据库较难优化
• 被频繁查询的字段：我们创建索引的字段应该是查询操作非常频繁的字段
• 被作为条件查询的字段：被作为where条件查询的字段，应该被考虑建立索引
• 频繁需要排序的字段：索引已经排序，这样查询可以利用索引的排序，加快排序查询时间
• 被频繁用于连接的字段：经常用于连接的字段可能是一些外键列，对于外键列并不一定要建立外键，只是说该列涉及表与表的关系。对于频繁被连接查询的字段，可以考虑建立索引，提高多表连接查询的效率

2、被频繁更新的字段应该甚至建立索引

虽然索引带来的查询上的效率，但是维护索引的成本很大。如果一个字段不经常查询，反而经常要更改，那么不应该建立索引

3、限制索引数量

所有并不是越多越好，建议单张表索引不超过5个

索引可以提高查询效率，但同样会降低插入和更新的效率，甚至有些情况并不会提高查询效率。因为MySQL优化器在选择如何优化查询时，会根据统一信息，对每一个可以用到的索引进行评估，以生成出一个最好的执行计划，如果同时有多个索引都可以用于查询，就会增加MySQL优化器生成执行计划的时间，同时会降低查询性能

4、尽量考虑建立联合索引而不是单列索引

因为索引是需要占用磁盘空间的，可以简单理解为每个索引都对应着一颗B+树 ，如果一个表的字段过多，索引过多，那么当这个表的数据达到一个体量后，索引占用的空间也是很多的的，且修改索引时，耗费的时间也是较多的，如果是联合索引，多个字段在一个索引上，那么将会节约很大的磁盘空间 ，修改数据的操作效率也会提升

5、避免冗余索引

冗余索引指的是索引的功能相同，能够命中索引（a,b）就肯定能命中索引（a），那么索引a就是冗余索引。在大多数情况下，都应该尽量扩展已有的所有而不是创建新索引

6、避免索引失效

索引失效也是慢查询的主要原因之一，常见的导致索引失效的情况：

• 范围查找导致索引失效，select * …where xxx ，where查询范围过大，导致没有走索引而是全表查询。where后的条件尽量精确一点

• 创建了联合索引，但查询时没有遵循最左匹配原则

• 在索引列上进行计算、函数、类型转换等操作

• 以 %开头的LIKE查询，比如 like ‘ %abc’ ----全表扫描，索引失效

• 查询条件中使用or，且or的前后条件中有一个列没有索引，涉及的索引都不会被使用到。

• 使用order by导致索引失效。没有where语句时，对于非聚簇索引，只能从叶子节点开始查找，找到对应主键然后回表查询，这样效率不如直接全表扫描，所以索引失效

7、删除长期未使用的索引

不用的索引会造成不必要的性能损耗，所以要删除长期未使用的索引。MySQL5.7可以通过查询sys库的schema_unuser_indexes视图来查询哪些索引从未被使用