在这篇文章中，我会先介绍一下什么是索引，索引有什么作用。
之后会介绍一下索引的数据结构是什么样的，有什么优点，又会带来什么样的问题。
在分析完数据结构后，我们可以根据这个数据结构，研究索引的用法，以及如何设计更高效的缓存。
最后，我会对上一篇的内容进行补充，介绍change buffer的作用以及分析change buffer对性能的影响。
1 目的在我们学习索引之前，我们要先了解它是什么，以及有什么作用。
官方对于索引的定义是这样的：
Indexes are used to find rows with specific column values quickly. Without an index, MySQL must begin with the first row and then read through the entire table to find the relevant rows.
也就是说，索引是用来快速查找具有特定值的一行数据(的一种数据结构)。如果没有索引，MySQL必须得从第一行开始逐行扫描数据。
尤其是当我们的数据量越来越大的时候，恰当的索引是可以帮助我们拥有更优秀的性能的。
这句话的另外一层含义在于：如果索引设计的不好，可能会使得我们的数据库性能变得更加的糟糕。
那么，索引到底是什么呢？我们接着往下看。
2 模型在讲索引具体的数据结构之前，我们来想象一下我们在英文词典里面找一个单词。
如果我们需要找一个单词："awesome"！
我们会在目录里面找到以字母 A 开头的一系列单词，然后从以字母 A 开头的一系列单词中找到 W ，然后是 E ...
就这样不断的往下查找，不断缩小我们的查找范围。如果我们不适用目录，直接在正文里面找这个单词，可能需要花费更多的时间。
况且，这个词典里面的单词是排好序的，如果我们找 Z 开头的字母，可能得找好几百页，才能最终找到。
这个例子不能说特别的准确，但是反映了索引的核心：减少查找的次数。
我们都知道，MySQL的数据保存在了磁盘中。而磁盘的IO是最慢的。所以，减少磁盘的读写是提高性能必不可少的做法。虽然现在大多数计算机已经使用了SSD，不再需要寻道等，但是索引的原则还是成立的。
这里我们来看看InnoDB的B+树是怎么实现的（图来自于《高性能MySQL》）：
可以看出，这是一颗N叉树，树中的每一个结点，都是MySQL中的一个数据页。
其实说白了这里的N叉树，和二叉查找树查找逻辑是一样的。只不过不同的地方在于这里的每一个结点，包含了比二叉查找树更多的数据与指针。这样做的目的是使得在数据量相同的情况下，B+树可以使得树的高度更低。
而又因为所有的数据页都是持久化保存在磁盘中的，所以更低的高度意味着查找一个数据需要进行磁盘IO的次数越少，效率变得更高。
注意，因为N叉树的N越大，对应的树的高度就会越低。而每一个结点（每一个数据页）的大小是固定的（默认是16K，可以使用innodb_page_size参数修改），所以当设置为索引的key越小的时候，N就会越大。
3 分类在经过上面的介绍之后，我想你应该能理解索引的查找方法了。下面我们再来说说索引的分类：
主键索引和非主键索引。
主键索引，就是非叶子结点中存储的值都是主键的值，在查找的时候通过主键查找。直到查找到最后的叶子节点。在最后的叶子节点中保存了这个主键对应的整行数据。
非主键索引，就是非叶子结点中存储的值都是索引的值，查找的时候通过这一个数值进行查找。查找到最后的叶子节点，保存了对应的主键ID。然后，MySQL会根据查到的主键，再查找主键索引对应的B+树，直到找到这一行的所有数据。而这个通过查找到主键，然后再利用主键来再次查找，或者这一行数据的过程，称为回表。
注意，我们在新建一张表的时候，一定会有一颗以主键为索引的B+树。哪怕你没有设置主键，MySQL都会选一个不包含NULL的第一个唯一索引列作为主键列，并把它用作一个主键索引。如果没有这样的索引就会使用行号生成一个聚集索引，把它当做主键。
此外，每增加一个索引，MySQL就会多维护一颗B+树。维护B+树的过程也是很复杂的，涉及到了页的分裂等，我想在以后的文章进行介绍。
另外之前也提到了，影响MySQL性能的一个很重要的因素就是磁盘IO。而回表这个操作，无异于增加了很多的IO次数。
那么有什么办法可以减少这一部分的开销吗，我们接着往下看。
4 联合索引我们在上面提到的索引，都是单个的数据进行查找。
这样的话，我们每次对其中一个列建立一个索引，就得多维护一颗B+树，同样对性能和空间造成了浪费。
那么我们有没有可能同时对多个数据进行排序，然后再进行查找呢？答案是可以的，我们可以采用联合索引。
4.1 最左前缀