前置知识：

[1] MySQL物理数据行
[2] MySQL数据页、数据区、表空间

没有索引时，怎么搜索数据？

数据行是放在数据页的槽位里面的，每个槽位可以放多条数据，每个数据页都有对应的页目录，页目录存储着主键和槽位的映射关系。当没有索引的时候，就会一页一页地将数据页加载进内存，然后二分查找数据页的页目录的主键，找到对应的槽位，然后遍历槽位里面的数据组找到数据。最差的情况下，需要遍历完所有的数据页。过程如下：

  1. 现有数据页10和数据页11，分别里面有5条数据。

image.png

  1. 现在要取 id=8 的数据。先加载数据页10到内存，然后对它的页目录进行二分查找，发现不存在需要的数据。然后加载数据页11，对页目录进行二分查找，找到了主键8，然后去到对应的槽位进行遍历就获取到数据了。

随着数据页的增加，每次查找都进行全表扫描的话，效率是非常低的。

使用索引提升搜索数据效率

将每个数据页的最小主键值和对应的页号提取出来，这样就会形成一个目录，这样就可以对这个目录进行二分查找，就可以迅速定位到数据对应的数据页。将这些目录存放在数据页里面，就叫做索引页。
image.png

随着数据的增加，数据页越来越多，这时候索引页的性能提升就非常的明显，因为不需要加载所有的数据页到内存遍历了。例如要查找 id=17 的数据，搜索数据的过程如下：
image.png

  1. 加载索引页1，二分查找是否有包含主键id=17的数据页，发现没有。
  2. 加载索引页2，二分查找发现主键id=17的数据在数据页51。
  3. 加载数据页51，对页目录进行二分查找，找到id=17的数据对应的槽位。
  4. 对槽位进行数据遍历，获取到id=17的数据。

由于加了索引页，所以，并不需要加载数据页10和数据页11来查找了。有了索引页，不需要进行全表扫描，极大地提升了效率。

但是，随着数据的增加，索引页也会越来越多，还是需要遍历索引页，效率也会降低。这时候，可以在再上一层，加一层索引页，这层的索引页保存的是最小主键和对应的索引页号。这样，就再次可以减少遍历的次数，增加二分查找的次数，提升效率。如下图，索引页200，就是更上一层的索引页。
image.png

随着索引层级的增加，就形成了一棵树的结构，MySQL 正是使用 B+树来实现索引。使用索引来查找数据的过程，就是遍历顶层的索引页，然后在下层的索引页或者数据页进行二分查找来找到最终的数据。

聚簇索引

像上面建立的 B+树，在同一层级的索引页之间，也是用双向链表将它们连接起来的。这棵 B+树的最底层是数据页。这样一棵巨大的 B+索引树里面，如果叶子结点是数据页自己本身的话，就称这样的索引树为聚簇索引。

实际上是Inno DB 存储引擎里，对数据的增删改就是直接将数据页直接放在聚簇索引里面，数据就在聚簇索引里，聚簇索引里包含了数据。那么，增删改数据的时候，除了维护数据页以外，还会动态地维护聚簇索引。调整索引数据，增删索引页，增删索引层级。

二级索引

除了主键自动建立的聚簇索引以外，还可以使用单个字段建立索引。例如用户表的 name 字段。和巨簇索引的原理也差不多，底层的叶子结点也是数据页。但是这个数据页只包含 name 字段的值和这行数据的主键。数据页内的数据行的顺序是按照 name 的值从小到大排序。

使用 name 字段建立的二级索引是单独开来的一个B+树，和聚簇索引互相独立。增加数据的时候，除了直接添加到聚簇索引里面以外，还会维护 name 对应的二级索引的B+树。进行数据页，索引页的分裂，调整等操作。

查找的过程也和巨簇索引一样。首先遍历顶层的索引页，然后对子索引页进行二分查找定位到最后的数据页，然后在数据页里面就得到了对应的主键。如果查询的是这行数据的全部字段 “SELECT …” ，那么就会根据查找到的主键去巨簇索引里面进行查找。这个使用主键回到巨簇索引里面，查询完整数据的过程，叫做*回表。

联合索引

一般情况下，很少会使用单个字段作为索引，因为需要控制索引的数量，索引建多了，增删改的时候，就需要同时维护多个索引，导致效率下降。所以一般使用几个字段一起建立一个索引，几个字段一起建立的索引就成为联合索引。一般建立几个联合索引即可，也不能建立过多的联合索引。

联合索引会首先使用第1个字段从小到大排序，第1个字段的值相同的话，就使用第2个字段的值从小到大排序，以此类推。例如用户表有id，name，age，height，weight等字段，使用 age 和 height 字段建立联合索引。
image.png

然后执行这个查询”SELECT FROM user WHERE age=15 AND height=161 “。这个查询条件完全使用的是等号，而且查询条件的顺序和索引建立的字段的顺序也是一样的。所以这个是*等值匹配，是可以使用上建立的联合索引的。

先按照年龄 15 去搜索，发现数据在数据页1，然后再数据页1进行二分查找，找到有2条年龄是15的数据，然后根据第2个条件身高161去匹配。找到id=2这个索引数据。然后用id=2去聚簇索引里面查找。最后获取所有的字段出来，就可以了。