深入理解MySQL索引的底层原理和优化

1. 什么是索引

索引是帮助MySQL高效获取数据的排好序的数据结构。用于提高查询性能，相当于书的目录。比如我们在读一本书的时候，首先是通过目录来定位到文章的页码，然后通过页码再来快速定位到具体的内容。MySQL中也是一样，在查询数据的时候，首先看查询条件是否满足某个索引，符合则通过索引进行cha'z数据，如果不行的话则通过全表扫描，这样的效率是十分低的

MySQL读取数据原理
MySQL的数据是存在磁盘中的，在没有索引的前提下，数据是分散在磁盘的各个地方。我们知道性能瓶颈基本来自IO，这个时候逐行查找数据也就意味着要将数据片段加载到内存中，假如有N条数据，那么时间复杂度就是O(N)

无索引

在没有索引的时候，全表扫描，根据address地址去到对应的偏移量将数据load到内存中，其中IO加载则是性能瓶颈

引入树

创建索引的目的就是减少磁盘的IO次数，加快查询的速度

变成二叉树以后，时间复杂度由O(N)变成了O(logN)，磁盘IO减少，效率明显提升。比如我要查col2为89的23的数据，不加索引则有7次磁盘IO，加了索引以后就有3次即可

2. 索引相关的数据结构

2.1 Hash表

hash表也称为散列表，是一种根据关键字直接访问内存位置的数据结构。它通过将关键字映射到哈希函数计算得到的索引位置，将数据存储在数组中。哈希函数将关键字映射到数组的索引位置，使得查找、插入和删除操作都能在常数时间复杂度内完成

这样看来hash表在查询速度上确实可以尝试作为表索引结构，但是不可避免的是会带来一些问题，比如hash碰撞和退化等等，最恶劣的情况就是回到了没有索引的全表扫描结构

在插入数据的时候，首先计算hash值，然后将数据通过链表的形式连接起来，如果出现hash碰撞，添加到后续节点即可，比如A->B。如果hash表很均匀，那么在查询数据的时候确实很快，多索引keyjinx一次hash计算就可定位数据的位置，时间复杂度可以达到O(1)级，但是缺点问题也有很多

存在的问题

1. 浪费内存：使用hash表来作为索引结构的话，那就意味着需要维护一张大的hash表，这张表中含有全部key的hash值(包括hash碰撞)，那么在每次使用hash表的时候就需要将数据全量加载到内存，就比较浪费内存。比如我要并发执行1000次点查，那就要将1000份超大的hash表加载到内存中，这样就会导致很大的内存问题
2. 支持点查，不支持范围查询：在使用等值查询的时候，直接计算Hash即可，但是如果我要查询>A的全部数据呢？那么还是会走全表扫描，所以hash表作索引无法进行范围查询，同理排序也不可以
3. Hash碰撞导致退化为单链表：Hash碰撞是由不同的key计算出来的hash值相同就导致了数据倾斜，这样就退化成了一个普通单链表(极端情况)。比如我A B C的全部hash值都是 2，那么如果也要查询C，还是走的全表扫描

2.2 二叉树和红黑树

二叉树是由节点组成，每个节点最多有两个子节点，分别成为左子节点和右子节点，并且位置是有序的。
红黑树是自平衡的二叉树，它在二叉树的基础上增加了一些规则来保持树的平衡性。红黑树的节点有两种颜色，红色和黑色，通过对节点的颜色进行调整和旋转操作，红黑树可以保持树的高度平衡，从而提高了插入、删除和查找等操作的效率

每个节点只能存一个数据的索引值，而CPU每次从磁盘上至少读取1页（64位系统为4K）的数据，但是由于每个节点在磁盘中的位置是随机的，所以有很大概率CPU每次仅仅只能从磁盘读取到一个索引值，这样也会导致要进行多次的磁盘IO

2.2.1 二叉树

左边是使用顺序插入的，右边是乱序插入的，可见这个数据插入的顺序也会导致树的高度发生变化。顺序插入会导致二叉树退化，如果乱序插入的数据量很多，那也会导致树的高度暴涨

存在问题

1. 二叉树退化成单链表：二叉树如果是使用顺序插入的，那么就会进行失衡往右或者往左暴涨，直接退化成了单链表，这样会导致使用索引还是全表扫描。例如：自增的主键ID，如果要使用id作为索引就会导致结果退化成为了单链表
2. 数据量爆涨导致树高不低：如果数据量很多，那么生成的树的高度也会增加，这个时候的IO也会增加。例如：我现在有1000w条数据，如果树是平衡的，那么要检索(磁盘IO)的次数为log2(1000w) 也就是23次，如果退化为了单链表，那就是O(1000w)，也就是1000w次

2.2.2 红黑树

红黑树是自平衡的，不管数据的插入顺序如何他都会自动来调整树的平衡进行左旋和右旋，同时带来的问题也是由数据量爆涨导致树的高度很高

2.3 B树

B树即平衡查找树，一般理解为平衡多路查找树，也称为B-树、B_树。是一种自平衡树状数据结构，能对存储的数据进行O(log n)的时间复杂度进行查找、插入和删除

在上面遗留下来的问题就是节点信息少，数据高度会爆炸。如果将树的节点进行横向扩展，这样就可将节点信息增加(一次IO可以读取的信息更多)，树的高度也会降低

每个节点占用一个盘块的磁盘空间，一个节点上有n个升序排序的关键字和n+1个指向子树根节点的指针p，指针存储的是子节点所在的磁盘块的地址。以上图为例：每个节点有2个关键字，指向3棵子树。从根节点开始，关键字为17 35，p1指针指向的子树的数据范围为小于17，p2指针指向的子树的数据范围为17~35，p3指针指向的子树的数据范围为大于35，依次类推

特点

1. 叶节点具有相同的深度，叶节点的指针为空
2. 所有索引元素都不重复
3. 节点中存放的数据更多，数据索引是从左到右递增的

分析

如果我们要查索引关键字为29的数据，步骤如下：

1. 根据根节点找到磁盘块1，读入内存(磁盘I/O操作第1次)。比较关键字29在区间(17,35)，找到磁盘块1的指针P2
2. 根据P2指针找到磁盘块3，读入内存(磁盘I/O操作第2次)。比较关键字29在区间(26,30)，找到磁盘块3的指针P2
3. 根据P2指针找到磁盘块8，读入内存(磁盘I/O操作第3次)。在磁盘块8中的关键字列表中找到关键字29

分析上面过程，发现需要3次磁盘I/O操作，和3次内存查找操作。由于内存中的关键字是一个有序表结构，可以利用二分法查找提高效率。而3次磁盘I/O操作是影响整个B树查找效率的决定因素。B树相对于其他树缩减了节点个数，使每次磁盘I/O取到内存的数据都发挥了作用，从而提高了查询效率

问题

B树的每个节点都有data域，这无疑增大了节点大小，说白了增加了磁盘IO次数，为什么呢，因为磁盘IO一次读出的数据量大小是一个固定值，如果你的data数据和我的关键字一起的话，那一个节点所能存的关键字就少了(也就是说如果你把存放data的空间用来存关键字，那是不是可能更快的找到我想要的关键字)，所以每次读取的就少，IO次数就要增多，其中，磁盘的IO耗时是远大于在内存中的任何操作

2.4 B+树

B+树在B树的基础上做了进一步的优化，使其更加适合实现外存索引结构。上面的B树的每个节点不仅包含数据的索引值，也包含了数据的data值，B+树在此基础上只包含了索引

每一个节点就是每一页数据，在节点的存储空间一定的前提下，B树包含了索引值和数据值，而B+树只包含索引值，这就意味着B+树可以存更多的索引。当存储的数据量很大时同样会导致B树的深度较大，增大查询时的磁盘I/O次数，进而影响查询效率。在B+树中，所有数据记录节点都是按照键值大小顺序存放在同一层的叶子节点上，而非叶子节点上只存储索引值信息，这样可以大大加大每个节点存储的索引值数量，降低B+树的高度

InnoDB的底层数据结构就是B+树，其中主页节点是常驻内存的，检索的方式同B树，但是载入内存的大小就减少了很多，对比B树，它的优点如下：

1. 非叶子节点data，只存储索引，可以放更多的索引
2. 所有叶子节点之间都有一个链指针（顺序访问指针，可以提高访问的性能），比如检索大于36的数据，通过索引找到36所在的位置之后，然后直接读取指针就可以拿到全部数据
3. 数据记录都存放在叶子节点中(磁盘)中，只有找到之后才加载到内存中

InnoDB存储引擎页的默认大小是16KB，一般表的主键类型是int，也就是4bytes或者bigint 8bytes，按照bigint来计算，指针类型也一般为6bytes，也就是说根节点一个页中大概存储16KB/(8B+6B)=1170个键值，假设叶子节点的一个页(主要存data的节点)的数据大小为1kb，那么大概就可以存16kb/1kb = 16条数据。也就是说，如果B+树的索引高度为3，那么可以维护的记录数量为1170 * 1170 * 16 = 21902400条数据，当数据量超过2000w条的时候，mysql的性能会急剧下降。实际情况中每个节点可能不能填充满，因此在数据库中，B+Tree的高度一般都在2 ~ 4层。MySQL的InnoDB存储引擎在设计时是将根节点常驻内存的，也就是说查找某一键值的行记录时最多只需要1~3次磁盘I/O操作

B+树的索引是存在父子节点冗余的，就是因为这些冗余索引，索引就可以提高了数据检索的速度。就算是全表扫描也是直接走的叶节点之间的指针

3. 聚簇索引与非聚簇索引

在聚簇索引中，数据库表行中数据的物理顺序与键值的逻辑（索引）顺序相同。一个表的物理顺序只有一种情况，因此对应的聚集索引只能有一个。如果某索引不是聚集索引，则表中的行物理顺序与索引顺序不匹配，与非聚集索引相比，聚集索引有着更快的检索速度
非聚簇索引也被称为辅助索引（Secondary Key），是相对于主键索引（Primary Index）而言的。主键索引是用来唯一标识表中每一行数据的索引，而辅助索引则是基于表中的其他非主键列构建的索引

因为聚集索引的特性，它的建立有一定的特殊要求：

1. 在Innodb中，聚簇索引默认就是主键索引
2. 如果表中没有定义主键，那么该表的第一个唯一非空索引被作为聚集索引
3. 如果没有主键也没有合适的唯一索引，那么innodb内部会生成一个隐藏的主键作为聚集索引，这个隐藏的主键是一个6个字节的列，改列的值会随着数据的插入自增

自增主键和uuid作为主键的区别
由于主键使用了聚集索引，如果主键是自增id，那么对应的数据一定也是相邻地存放在磁盘上的，写入性能比较高。如果是uuid的形式，频繁的插入会使innodb频繁地移动磁盘块，写入性能就比较低了

3.1 非聚簇索引详解

非聚簇索引的作用是提高查询效率，当我们在表中创建了辅助索引后，可以通过非聚簇索引来加速查询操作，而不必直接依赖主键索引。非聚簇索引的构建方式类似于字典的索引，它会将索引列的值与对应的行记录关联起来，以便快速定位到符合条件的数据行。也可将它理解为是索引的索引，比如查字典，页码当成一级索引，那么部首就当成二级索引，我们通过查遍旁部首(二级索引)拿到字的页码(一级索引)，然后根据页码去拿到真正的字。从结构上来讲，多加一个索引就会多生成一棵非聚簇索引树。因此，索引不能随意增加。在做写库操作的时候，需要同时维护这几颗树的变化，导致效率降低！

结构图如下

注意看上图中的红色箭头，因为扫描完name索引后，Mysql只能获取到对应的id和name，然后用id的值再去聚集索引中去查询score的值。这个过程相对于聚集索引查询的效率下降

这就是通常所说的回表或者二次查询：使用聚集索引查询可以直接定位到记录，而普通索引通常需要扫描两遍索引树，即先通过普通索引定位到主键值，在通过聚集索引定位到行记录，这就是所谓的回表查询，它的性能比扫描一遍索引树低

4. 联合索引原理解析

联合索引（Composite Index）是数据库中的一种索引类型，它由多个列组成，用于提高查询效率。与单列索引不同，联合索引可以同时包含多个列的值，以便更快地定位和检索数据

在创建联合索引时，可以指定多个列作为索引的组合。这些列的顺序非常重要，因为联合索引会按照指定的列顺序进行排序和存储。当查询语句中的条件涉及到联合索引的列时，数据库可以更快地定位到符合条件的数据行

案例分析

现在有联合索引，(name, age, position)这三个字段，并且要注意联合索引的顺序

这样就做好了联合索引B+树，如果我们只拿联合索引内部的值，比如name, agem postion 和 birthday的任意组合，那么可以直接查询该索引树，但是需要注意最左前缀匹配原则

最左前缀原则
在MySQL建立联合索引时会遵守最左前缀匹配原则，即最左优先，在检索数据时从联合索引的最左边开始匹配。可以看出索引key在排序上，首先按照name排序，name相等的再按照age进行排序，在name和age都相等的情况下再按照position进行排序。如果此时的查询条件是name或者name，age或者name，age，position是都可以走索引的。但是如果查询条件是单独的某一个，或者1 3和2 3的组合，那么是用不到索引