MySQL索引

1. 多页结构

OS存储数据按页来存储，一页是4KB，读取数据也是一次读一页，原因是程序局部性的概念，大意是“一个程序在访问了一条数据之后，在之后会有极大的可能再次访问这条数据和访问这条数据的相邻数据”。

MySQL的InnoDb引擎中，一页是16KB。页内部存储数据是采用了链表的结构，链表的查询很慢，采用的优化措施就是在每一页添加页目录。每个目录项会存放自己这个目录项当中最小的id，在查询时先找在哪个目录，然后再逐条查找。而这种方式能成立的原因在于数据库在用户插入数据时会默认按照主键排序，否则按照页目录来查找就会出现问题。

在开辟新页的时候，我们插入的数据不一定是放在新开辟的页上，而是要进行所有页的数据比较，来决定这条插入的数据放在哪一页上，而完成数据插入之后，最终的多页结构就会如下：

页与页之间通过指针关联，也算是链表结构，所以在多页查询时也会出现查询效率低的情况。优化方式和页内部数据的优化一样，即创建一个目录页来管理页，存放的是页的地址以及这一页中最小的数据。

在查询时先在目录页中查询，对比最小地址，找到相应页的地址，然后进入到页中查看这一页的目录，找到数据。这个最终的结构就是B+树。

其中的每个节点就可以理解为是一个页，而叶子节点也就是数据页，除了叶子节点以外的节点就是目录页。

B+树的优势：

由于叶子节点上存放了所有的数据，并且有指针相连，每个叶子节点在逻辑上是相连的，所以对于范围查找比较友好。
B+树的所有数据都在叶子节点上，所以B+树的查询效率稳定，一般都是查询3次。
B+树有利于数据库的扫描。
B+树有利于磁盘的IO，因为他的层高基本不会因为数据扩大而增高（三层树结构大概可以存放两千万数据量。）

2. 页的结构

File Header 字段用于记录 Page 的头信息，其中比较重要的是 FIL_PAGE_PREV 和 FIL_PAGE_NEXT 字段，通过这两个字段，我们可以找到该页的上一页和下一页，实际上所有页通过两个字段可以形成一条双向链表。

Page Header 字段用于记录 Page 的状态信息。接下来的 Infimum 和 Supremum 是两个伪行记录，Infimum（下确界）记录比该页中任何主键值都要小的值，Supremum （上确界）记录比该页中任何主键值都要大的值，这个伪记录分别构成了页中记录的边界。

User Records 中存放的是实际的数据行记录，具体的行记录结构将在本文的第二节中详细介绍。Free Space 中存放的是空闲空间，被删除的行记录会被记录成空闲空间。Page Directory 记录着与二叉查找相关的信息。File Trailer 存储用于检测数据完整性的校验和等数据。

3. 聚簇索引和非聚簇索引

所谓聚簇索引，就是将索引和数据放到一起，找到索引也就找到了数据，我们刚才看到的B+树索引就是一种聚簇索引，而非聚簇索引就是将数据和索引分开，查找时需要先查找到索引，然后通过索引回表找到相应的数据。InnoDB有且只有一个聚簇索引，而MyISAM中都是非聚簇索引。

4. 联合索引的最左前缀匹配原则

多个字段建立的联合索引，只要有主键，就是一个聚簇索引；其他索引都是非聚簇索引，在叶子节点里不在有数据，而是存了一个主键索引，通过主键索引回表查询数据。

最左前缀匹配原则，MySQL会一直向右匹配直到遇到范围查询（>、<、between、like）就停止匹配，比如 a=3 and b=4 and c>5 and d=6,如果建立(a,b,c,d)顺序的索引，d是无法使用索引的，如果建立(a,b,d,c)的索引则都可以使用到，a、b、d的顺序可以任意调整。
=和in可以乱序，比如 a=1 and b=2 and c=3 建立(a,b,c)索引可以任意顺序，MySQL的查询优化器会帮你优化成索引可以识别的形式。

id, age, weight, name 字段 按照age,weight建立一个联合索引 

SELECT * FROM user where age>1

这条语句不会走索引，但是可以走索引。这句话是什么意思呢？这条SQL很特殊，由于其存在可以比较的索引，所以它走索引也可以查询出结果，但是由于这种情况是范围查询并且是全字段查询，如果走索引，还需要进行回表，MySQL查询优化器就会认为走索引的效率比全表扫描还要低，所以MySQL会去优化它，让他直接进行全表扫描。

explain 查看执行计划的优化，大概流程如下

根据搜索条件，找出所有可能使用的索引

计算全表扫描的代价

计算使用不同索引执行查询的代价

对比各种执行方案的代价，找出成本最低的那一个。

5. 为什么InnoDB只有一个聚簇索引，而不将所有索引都使用聚簇索引？

因为聚簇索引是将索引和数据都存放在叶子节点中，如果所有的索引都用聚簇索引，则每一个索引都将保存一份数据，会造成数据的冗余，在数据量很大的情况下，这种数据冗余是很消耗资源的。

6. 总结

排序：优化查询的根本，插入时进行排序实际上就是为了优化查询的效率。
页：用于减少IO次数，还可以利用程序局部性原理，来稍微提高查询效率。
页目录：用于规避链表的软肋，避免在查询时进行链表的扫描。
多页：数据量增加的情况下开辟新页来保存数据。
目录页：“特殊的页目录”，其中保存的数据是页的地址。查询时可以通过目录页快速定位到页，避免多页的扫描。