引言
MySQL的索引机制，自始至终对于我们都是一个黑盒般的存在，我们并不清楚建立索引后MySQL会发生什么，也并不清楚使用索引查询时会如何检索......。对于索引咱们也留下了很多很多的疑惑：
相信大家多多少少都有了解过，毕竟这也是面试过程中出现次数较为频繁的一个技术点。在本文中就来一窥MySQL索引底层的神秘面纱！
一、MySQL索引为何使用B+树结构？
MySQL的索引机制中，有一点可谓是路人皆知，既默认使用B+Tree作为底层的数据结构，但为什么要选择B+树呢？有人会说树结构是以二分法查找数据，所以会在很大程度上提升检索性能，这点确实没错，但树结构有那么多，MySQL为什么不选二叉树、AVL树、红黑树或B树呢？下面一起先聊一聊这个话题。
对于索引为什么不支持数组、链表、队列等结构就不做过多解释了，因为这些结构中的元素都是按序并排存储，如果选择这些结构来实现索引，那走索引依旧等价于走全表，并未带来查询时的效率提升，反而带来了额外的存储开销，这是没有意义的。
1.1、普通SQL的全表扫描过程
想要真正理解MySQL为何选B+树结构之前，你必须要先了解一条普通SQL的全表扫描过程，否则你很难真正切身感受出有索引和没索引的区别。当然，这里就不再以伪逻辑的形式讲解全表扫描了，而是真正的为大家讲解MySQL全表扫描的实际过程。以下面这张用户表为例：
首先假设表中不存在任何索引，此时来执行下述这条SQL：
SELECT * FROM `zz_user` WHERE `name` = "黑熊";
复制代码因为表中不具备索引，所以这里会走全表扫描的形式检索数据，但不管是走全表亦或索引，本质上由于数据都存储在磁盘中，因此首先都会触发磁盘IO，所以先来说说磁盘寻道的过程：
如果磁盘不是SSD类型，大致长上面这个样子，里面有一个个的盘面和磁针，当发生磁盘IO时，首先会根据给出的磁盘地址，在盘面上寻道。这个寻道过程是怎么回事呢？就跟小时候VCD、DVD放光碟类似，盘面会开始转圈圈，在盘面上有一个磁道的概念，当转到了对应的地址时，磁道和磁针会相互吸引，然后以一上一下的方式读取0、1二进制数据，最终从磁盘中将目标地址中的数据读取出来。
磁盘寻道的大致过程如上，具体的细节没写出来，重点是大家要感受这个过程即可。
当走全表扫描时，会发生磁盘IO，但是磁盘寻道是需要有一个地址的，这个地址最开始就是本地表数据文件中的起始地址，也就是从表中的第一行数据开始读，读到数据后会载入内存，然后MySQL-Server会根据SQL条件对读到的数据做判断，如果不符合条件则继续发生磁盘IO读取其他数据（如果表比较大，这里不会以顺序IO的形式走全表检索，而是会触发随机的磁盘IO）。
那来看一下，上面给出的用户表中，「黑熊」这条数据位于表的第五行，那这里会发生五次磁盘IO吗？答案是NO，为什么呢？因为OS、MySQL中都有一个优化措施，叫做局部性读取原理。
1.1.1、局部性原理
局部性原理的思想比较简单，比如目前有三块内存页x、y、z是相连的，CPU此刻在操作x页中的数据，那按照计算机的特性，一般同一个数据都会放入到物理相连的内存地址上存储，也就是当前在操作x页的数据，那么对于y，z这两页内存的数据也很有可能在接下来的时间内被操作，因此对于y，z这两页数据则会提前将其载入到高速缓冲区（L1/L2/L3），这个过程叫做利用局部性原理“预读”数据。
但是一次性到底预读多大的数据放入到高速缓冲区中呢？
这个是由缓存行大小决定的，比如因特尔的MESI协议中，缓存行的默认大小为64k，也就是说在因特尔的CPU中，一次性会将“当前操作数据”附近的64K数据（16页数据）提前载入进高速缓冲区。
