1. 磁盘数据页的存储结构

大量的数据页按顺序一页一页存放的，然后两两相邻的数据页之间会采用双向链表的格式相互引用。然后一个数据页内部会存储一行一行的数据，也就是平时我们在表里插入的一行一行的数据就会存储在数据页里，然后数据页里的每一行数据都会安照主键大小进行排序存储，同时每一行数据都会有指针指向下一行数据的位置，组成单链链表。

其实每个数据页里都会有一个页目录，里面根据数据行的主键存放了一个目录，同时数据行是被分散存储到不同的槽位里去的，所以实际上每个数据页的目录里，就是这个页里每个主键跟所在槽位的映射关系。

假设没有建立任何所以索引，那么无论根据主键查询，还是根据其他字段来条件查询，实际上都没有什么取巧的地方。
直接从第一个数据页开始遍历所有的数据页，从第一个数据页开始，你得先把第一个数据页从磁盘上读取到内存buffer pool 的缓存页里来。
然后你就在第一个数据页对应的缓存页里，假设根据主键查找的，你可以在数据页的页目录里二分查找，假设你要是根据其他字段查找的，只能根据数据页内部的单向链表来遍历查找。
如果第一个数据页没找到你要的那条数据，没办法，只能根据数据页的双向链表去找下一个数据页，然后按一样的方法在一个缓存页内部查找那条数据。如果找不到，继续加载下一个数据页，以此类推，循环往复。最坏的情况下，你就得把所有数据页的每条数据都得遍历一遍，这其实就是全表扫描。

2. 页分裂

假设不停的往表里插入数据，那么刚开始就是不停的往一个数据页插入数据，接着数据越来越多，此时就要在搞一个数据页。但是此时会遇到一个问题，索引机制的一个核心基础就是要求你后一个数据页的主键值要大于前面一个数据页的主键值，但是如果你的主键是自增的，很容易保证这一点，但是如果不是，就可能出现后一个数据页的主键值里，有的主键是小于前一个数据页的主键值的。这就出现了问题。
所谓的页分裂其实就是解决这个问题的过程，就是万一你的主键值都是你自己设置的，那么在增加一个新的数据页的时候，实际上会把前一个数据页里主键值较大的，挪到新的数据页，然后把你新插入的主键值较小的数据挪动到上一个数据页里去，保证数据页里的主键值一定比上一个数据页里的主键大。
页分裂的核心目标就是保证下一个数据页里的主键值都比上一个数据页的主键值要大。

3. 主键索引

为了避免全表扫描，需要针对主键设计一个索引，针对主键的索引实际上就是主键的目录，这个主键目录呢，就是把每个数据页的页号，还有数据页里最小的主键值放在一起，组成一个索引的目录。

有了上图的主键目录就方便了，直接就可以到主键目录里去搜素，比如你要找 id=3的数据，此时就会跟每个数据页的最小主键来比，首先id = 3 大于了数据页2 里最小的主键值1，接着小于了数据页8 里的最小的主键值4。所以可以定位到 id=3 的数据一定是在数据页2里的。

4. B+ 树

数据页很多的情况，主键目录里就要存储大量的数据页和最小主键值，这样不行。考虑到这个问题，实际上是采取了一种把索引数据存储在数据页里的方式来做。
也就是说，你的表的实际是存放在数据页里的，然后你表的索引其实也是存放在页里的，此时索引放在页里之后，就会有索引页，假设你有很多很多数据页，那么此时你就可以有很多的索引页。
但是现在有存在一个问题，你现在有很多索引页，但是此时你需要知道，你应该到哪个索引页里去找你的主键数据，是索引页20？还是索引页28？这也是大问题。
于是接下来我们又可以把索引页多加一个层级出来，在更高的索引层级里，保存了每个索引页和索引页里最小主键值。
还有一个问题，假如最顶层的那个索引页里存放的下层索引项的页号也太多了，怎么办。此时可以再次分裂，再加一层索引页，比如下图。

这就是B+树，属于数据结构里的一种树形结构。
当你一个表的主键建立起来索引之后，其实这个主键的索引就是一颗B+树，然后当你要根据主键来查询数据的时候，直接就是从 B+ 树的顶层开始二分查找，一层一层往下定位，最终一直定位到一个数据页里，在数据页内部的目录里二分查找，找到那条数据。

5.聚簇索引

如果一颗大的B+树索引数据结构里，叶子节点就是数据页自己本身，那么此时我们就可以称这颗B+树索引为聚簇索引。
其实在InnoDB 存储引擎里，对数据增删改的时候，就是直接把你的数据页放在聚簇索引里的，聚簇索引包含了数据，比如你插入了，那么就是在数据页里插入数据。

6. 二级索引

假设你要针对主键外其他字段建立索引，比如name、age之类的字段，都是一样的原理，简单来说，比如你插入数据的时候，一方面会把完整的数据插入到聚簇索引的叶子节点的数据页里去，同时维护好聚簇索引，另一方面会为你其他字段建立的索引，重新建立一颗B+数。
值得注意的是这是独立于聚簇索引外的另外一颗索引的B+ 树，严格来说是name字段的索引 B+树，所以在name 字段的索引B+树里，叶子节点的数据页里仅仅存放了主键和name 字段值，至于排序规则之类的，都是跟之前说的一样的。
针对”select from table where name=xxx’ 这样的语句，你先根据name 字段值在name 字段的索引B+ 树里去找，找到叶子节点也仅仅是找到了对应的主键值，而找不到这行数据完整的字段值。
所以此时还需要进行“回表”，这个回表就是说还需要根据主键值，再到聚簇索引里从根节点开始，一路找到叶子节点的数据页，定位到主键对应的完整的数据行，此时才能把select 要的字段值都拿出来。
因为我们根据name 字段的索引B+ 数找到主键之后，还要根据主键去聚簇索引里去找，所以一般把 name 字段这种普通字段的索引称之为二级索引，一级索引就是聚簇索引，这就是普通字段的索引运行原理。
其实也可以把多个字段联合起来，建立联合索引，比如name+age。

7. 插入数据时维护索引

首先，刚开始一个表搞出来以后，其实他就是一个数据页，这个数据页就是属于聚簇索引的一部分，而且目前是空的，
此时你如果插入数据，就是直接在这个数据页里插入即可，也没必要弄索引页。这个初始的数据页就是一个根页，每个数据页内部默认就有一个基于主键的页目录，所以此时你根据主键来搜索都是ok 没有问题的，直接在唯一一个数据页根据页目录找就行了。
然后你表里的数据越来越多，此时你的数据页满了，那么就会搞一个新的数据页，然后把你的根页里面的数据都拷贝过去，同时再搞一个新的数据页，根据你的主键值的大小进行挪动，让两个新的数据页根据主键值排序，第二个数据页的主键值都大于第一个数据页的主键值。
此时就会把根页升级为索引页，这个根页里放的是两个数据页的页号和他们里面最小的主键值。
接着继续不停地往表里灌入数据，然后数据页不停的页分裂，分裂出来越来越多的数据页。
此时你 唯一的一个索引页，也就是根页里存放的数据页索引的条目越来越多，连你的索引页都放不下，那么就让一个索引页分裂成两个索引页，然后根继续往上走一个层级引用两个索引页。
接着类推，你的数据页越来越多，那么根页指向的索引页也会不停的分裂，分裂出更多的索引页，当你下层的索引页数量太多的时候，会导致你的根页指向的索引页太多了，此时根页继续分裂成多个索引页，根页再次往上去一个层次。
二级索引也是类似一个原理。

8. 索引使用规则

8.1 索引是不是越多越好

索引的好处是直接根据某个字段的索引B+ 树查找数据，不需要全表搜索，性能提升是很高的。

缺点就是一个空间和一个时间上的。空间上而言，你要是给很多字段创建很多的索引，那你必须有很多的索引B+ 树，每一颗B+ 树都要占用很多的磁盘空间。其次，时间上你进行增删改查的时候，每次都需要维护各个索引的数据有序性，可能会进行数据页挪动并且各个索引页都要不停，不停的增加新的索引页，这个过程是非常耗时的。

8.2 理解联合索引查询原理以及全值匹配规则

为了尽可能的让索引的数量少一些，避免磁盘占用太多，增删改性能太差。所以引出联合索引。
假设一下，有一个表存储学生成绩的，这个表当然有id，这个id 是一个自增主键，默认的情况下就会基于他做一个聚簇索引。然后，学生班级、学生姓名、科目名称、成绩分数四个字段中，最多的查询就是查找某个班的某个学生的某个科目的成绩。
所以，我们针对学生班级、学生姓名和科目名称建立一个联合索引。

下面有两个数据页，第一个数据页里有三条数据，每条数据都包含了联合索引的三个字段的值和主键值，数据页内部是按照顺序排序的。
首先按照班级字段的值来排序，如果一样则按照学生姓名字段来排序，如果一样，则按照科目名称来排序，所以数据内部都是按照三个字段值来排序的，而且还组成了单向链表。
索引页里就是两条数据，分别指向两个数据页，索引存放的是每个数据页里最小的那个数据的值，大家看到，索引页里指向两个数据页的索引项都是存放了那个数据页的最小的值。
索引内部的数据页是组成单向链表有序的，如果你有多个索引页，那么索引页之间也是有序的，组成了双向链表。

假设我们想要搜索: 1班 + 张小强 + 数学 的成绩，此时你可能会写一个类似下面的SQL语句，select * from student_score where class_name=’1班’ and student_name=’张小强’ and subject_name=’数学’。
此时就涉及到了一个索引使用的规则，那就是你发起的SQL 语句里，where 条件里的几个字段基于等值来查询，都是用的等于号！，而且where 条件里的几个字段的名称和顺序跟你的联合索引一模一样，此时就是等值匹配规则。
找到id=127 然后到聚簇索引找那条数据。

所谓的全值匹配规则，即假设你的SQL语句的where条件里的几个字段的名称和顺序，都跟你的索引里的字段一样，同时你还是用等号在做等值匹配。
对于联合索引而言，就是依次按照各个字段进行二分查找，先定位到第一个字段对应的值在哪个页里，然后如果第一个字段有多条数据值都一样，就根据第二个字段来找，以此类推，一定可以定位到某条或者某几条数据。

8.3 最左侧匹配规则

假设我们的联合索引是KEY(class_name,student_name,subject_name), 那么不一定必须要在 where 语句里根据三个字段来查，其实只要根据最左侧的部分字段来查，也是可以的。
比如你可以写 select from studet_score where class_name =’’ and studet_name=’’，就查某个学生所有科目的成绩，这是可以的。
但是假设你写一个 select from student_score where subject_name ，那就不行了，因为联合索引的B+ 树里，是必须按照class_name 查，再按照 student_name 查，不能跳过前面两个字段，直接按最后一个 subject_name 查询。
另外，假设你写一个 select * from student_score where class_name=’’ and subject_name=’’ ，那么只有 class_name 的值可以在索引里搜索，剩下的 subject_name 是没法在索引里找的。

8.4 最左侧前缀匹配规则

即如果你要用 like 语法来查，比如 select * from student_score where class_name like ‘1%’，查找所有 1 打头的班级的分数，那么也是可以用索引的。
因为你的联合索引的B+ 树里，都是按照 class_name 排序的，所有你要是给出 class_name 的确定的最左前缀就是1，然后后面的给一个模糊的匹配符号，那也是可以基于索引来查找的，这也是没问题的。
但是你写了class_name like ‘%班’，在左侧用一个模糊匹配符，那他就没法用索引了，因为你不知道最左前缀是什么。

8.5 范围查找规则

这个意思是说，我们可以用 select * from student_score where class_name > ‘1班’ and class_name<’5班’ 这样的语句来范围查找几个班级的分数。
这个时候也会用到索引的，因为我们的索引的最下层的数据页都是按顺序组成双向链表的，所以完全可以先找到 ‘1班’ 对应的数据页，再找到’5班’对应的数据页，两个数据页中间的那些数据页，就全都是在你范围内数据了。

但是如果你要是写 select * from student_score where class_name > ‘1班’ and class_name < ‘5班’ and student_name>”，这里只有 class_name 是可以基于索引来找的， student_name 的范围查询是没法用到索引的。
这是一条规则，就是你的 where 语句里如果有范围查询，那只有对联合索引最左侧的列进行范围查询才能用到索引！

8.6 等值匹配 + 范围匹配的规则

如果你要是用 select * from student_score where class_name=’1班’ and student_name>” and student_name<”,那么此时你首先可以用 class_name 在索引里精准定位一波数据，接着这波数据里的 student_name 都是按照顺序排列的，所以student_name >’’ 也会基于索引来查找。但是接下来 subject_name < ‘’ 是不能用索引的。

9. 排序如何才能使用索引

假设你有一个 select * from table where xxx=xxx order by xxx 这样的一个SQL 语句，似乎应该是基于 where 语句通过索引快速通过索引筛选出一波数据，接着放到内存里，或者放在一个临时的磁盘文件里，然后通过排序算法按照某个字段进行排序，最后把排序好的数据返回。

但是这样的话速度有点慢，尤其万一你要排序的数据量比较大的话，还不能用内存来排序，如果基于磁盘文件来排序，那么在MySQL 里有个术语叫做 filesort，这速度就比较慢了。
通常而言，最好不要这么做，尤其类似于 select from table order by xx1,xx2,xx3 limit 100 这样的语句，按照多个字段进行排序后然后返回100 条数据，这会很慢。
所以通常而言，在这种情况下，假设我们建立了一个 INDEX(xx1,xx2,xx3) 这样一个联合索引，这个时候默认的情况下在索引树里本身就是按照 xx1,xx2,xx3 三个字段的值去排序的，那么此时你再运行 select from table order by xx1,xx2,xx3 limit 100 这样的SQL 语句，就不需要临时磁盘文件里进行排序。
所以说，在你的SQL语句里，应该尽量是按照联合索引的字段顺序去进行 order by 排序，这样就可以直接利用联合索引树里数据的有序性，到索引树里直接按照字段值得顺序去获取你需要的数据。
但是这里有一个限定规则，因为联合索引里的字段值在索引树里都是从小到大依次排序的，所以你在 orderby 里要不然就是每个字段后边什么都不加，直接就是 order by xx1,xx2,xx3 ，要不然就都加DESC 降序排序，就是 order by xx1 DESC, xx2 DESC,xx3 DESC。
另外，要是你order by 语句里有的字段不在联合索引里，或者你对order by 语句里的字段用了复杂的函数，这些也不能使用索引去进行排序的。

10. 分组如何才能使用索引

假设你要走一个 select count(*) from table group by xxx 的SQL语句，似乎看起来必须把你所有的数据放到一个临时磁盘文件里还有加上部分内存，去搞一个分组，按照指定的字段值分成一组一组的，接着对每一组都执行一个聚合函数，这个性能也是极差的。
因为在我们的索引树里默认的都是按照指定的一些字段都排序好的，其实字段值相同的数据都是在一起的，假设要是走索引去执行分组后再聚合，那性能一定是比临时磁盘文件执行好很多。
所以通常而言，对group by 后的字段，最好也是按照联合索引里的最左侧的字段开始，按顺序排列开来，这样的话，其实就可以完美的运用上索引来直接提前一组组的数据，然后针对每一组的数据执行聚合函数就可以了。
其实会发现，这个group by 和 order by 用上索引的原理和条件都是差不多的，本质都是在 group by 和 order by 之后的字段顺序 和 联合索引的中的从左侧开始的字段顺序一致，然后就可以充分利用索引树里已经完成排序的特性，快速的根据排序号的数据执行后续的操作了。

11. 覆盖索引

假设你走类似 select from table order by xx1,xx2,xx3 的语句，可能你就是得从联合索引的索引树里按照顺序取出来所有的数据，接着对于每一条数据都走一个主键的聚簇索引的查找，其实性能也不是很高的。
有的时候MySQL 的执行引擎甚至可能认为，你要是类似于 select from table order by xx1,xx2,xx3 的语句，相当于是得把联合索引和聚簇索引，两个索引的所有数据扫描一遍，那还不如走联合索引，直接全表扫描得了，这样还就扫描一个索引而已。
但是你如果要是 select * from table order by xx1,xx2,xx3 limit 10 这样的语句，那执行引擎就知道了，你先扫描联合索引的索引树拿到10条数据，接着对10条数据在聚簇索引查找10次就可以了，那么就还是会走联合索引的。

覆盖索引就是针对类似 select xx1,xx2,xx3 from table order by xx1,xx2,xx3 这样的语句，这种情况下，你仅仅需要联合索引里的几个字段的值，那么实际上就只要扫描联合索引的索引树就可以，不需要回表去聚簇索引里找到其他字段。
所以这个时候，需要的字段直接在索引树里就能提取出来，不需要回表到聚簇索引，这种查询方式就是覆盖索引。

也正是这样，所以你写SQL语句的时候，一方面要注意一下也许你用到联合索引，但是是否可能导致大量的回表到聚簇索引，如果需要回表到聚簇索引的次数太多了，可能就直接给你做成全表扫描，不走联合索引了。
一方面是尽可能还是在SQL里指定你仅仅需要的几个字段，不要搞一个 select * 把所有的字段都拿出来，甚至最好直接走覆盖索引的方式，不要去回表到聚簇索引。
即使真的要回表到聚簇索引，那你也尽可能用 limit、where 之类的语句限定一下回表到聚簇索引的次数。

12. 索引设计原则

12.1 针对SQL语句里的where条件、order by 条件和 group by 条件去设计索引

设计一个或者两三个联合索引，每一个索引尽量包含上你的where、orderby、group by 里的字段，接着你就要仔细查每个SQL 语句，是不是每个 where、order by、 group by 后面跟的字段顺序，都是某个联合索引的最左侧开始的部分字段。

12.2 一般建立索引，尽量使用那些基数比较大的字段

值比较多的字段，才能发挥B+树快速二分查找的优势来。不过这个字段的类型要相对小一点。
万一真有 varchar(255) 的字段，可能里面的值太大了，你觉得放在索引树里太占据磁盘文件，此时可以换一种策略，可以仅仅针对这个 varchar(255) 字段的前20 个字符建立索引。
此时你建立的索引类似于 KEY my_index(name(20),age,course)这样的形式。此时你在where 条件里搜索的时候，如果根据name 字段来搜素，那么此时就会先到索引树里根据 name 字段的前20 个字符去搜索，定位到之后前20个字符的前缀匹配的部分数据之后，再回到聚簇索引提取出来完整的 name 字段值进行比对就可以了。
但是假如你要是 order by name，那么此时你的name 因为在索引树里仅仅包含了前20个字符，所以这个排序是没法用上索引了。同理 group by 也是。

12.3 尽量让你的查询语句里的字段不要进行计算

假设你设计好了一个索引，接着在SQL语句里写： where function(a)=xx，这样也用不了索引。