什么是索引，为啥要用索引

使用索引的目的在于提高数据的访问速度。

假设不使用索引，对于数据库中的数据我们一般只能通过一条条的读取数据然后进行对比，直到找到符合我们要求的数据为止（即顺序查找）。很显然，这样的查找效率是非常低下的。更好的办法是我们构建一张表（这里的表不是指数据库中的表，而是数据结构中的表，可以看成是一种映射关系），这张表保存着某个数据和该数据所对应的整条记录在硬盘上所保存的真正的位置。有了这张表，我们就可以非常快速的找到我们想要查找的数据了。

例如对于上面的这张表映射关系，我们相当于对某张数据库表的 name 字段添加了索引，这样在添加或修改某条记录的时候，我们除了要修改真正的数据本身，还要同时修改这张映射表中的关系。例如我们要添加一条 name 为Feynman的记录，我们先把这条数据保存到硬盘上，然后在映射表中添加一条 name=Feynman 的记录，之后把刚刚数据保存在硬盘的具体位置信息保存到映射表中的这条记录上。

当以后我们要检索 name=Feynman 的数据的时候，因为 name 字段已经加上了索引，所以我们先从映射表中找到所有的 name=Feynman 的记录，之后根据映射表中保存的物理地址信息中去查找真实的数据，之后把真正的记录读取出来即可。

从上面我们可以发现索引本质上就是一张映射表，用来保存被检索字段和真实的数据位置信息的映射关系。索引本质上和书籍的目录是一回事，书籍的目录使用章节信息作为索引，因为章节与页码之间存在着映射关系，所以我们可以通过在目录中查找章节信息从而找到其对应的页码，最终把数据本身给读取出来。

B 树

在上一小节中我们已经知道了索引其实就是被检索字段与真实数据位置信息之间的映射关系，那么索引应该怎么保存呢？最基本的办法就是在硬盘上面划一块空间，然后把索引保存进去，之后当我们要用的时候把它从硬盘读到内存里面，我们就可以使用它的映射关系了。

看上去是个不错的方案，不过索引一般其本身可能非常的大，一次性都读到内存中会导致大量的内存的占用，更何况全部读入的索引中有些被检索的字段我们可能根本就不会用到，所以这种方案被pass。我们想起来我们了解的红黑树或AVL树，那么我们可不可以这样：把索引本身以红黑树的形式保存到硬盘中，这样当我们要使用到某一条索引记录的时候就对红黑树执行查找操作。因为我们不会把整个索引读到内存中，与之相对的是只读入红黑树的一些节点，所以内存的占用会大大的降低。

例如对于上面这个例子，我们只需要读入四个节点就完成了检索操作，假设这棵树本身共有20个节点，那么我们使用红黑树构建索引的结构比把整个索引读入内存减少了4/5的内存浪费。看起来还不错，我们已经节约了大量的内存，但是不要忘了硬盘的操作速度是很缓慢的，我们每读入一个红黑树的节点就意味着进行一次硬盘的读取操作，如果这个节点离根很远，那么就意味着大量的硬盘读取操作，这会导致索引本身的检索速度非常的慢。

  1. 全部读入内存，索引是完整的，但是浪费内存
  2. 使用红黑树，按照需要从硬盘中获取索引信息，但是多次读取硬盘效率低下

我们尝试了以上的两种策略，它们都存在着一定的问题，下面我们了解一下B树这种数据结构，它能比较好的解决上面两个策略存在的问题。B-Tree（即B树，那个横杆不是减号的意思，B-Tree写起来是一个整体）的定义如下注1：

  1. 为了描述B-Tree，首先定义一条数据记录为一个二元组[key, data]，key为记录的键值，对于不同数据记录，key是互不相同的；data为数据记录除key外的数据。那么B-Tree是满足下列条件的数据结构：
  2. d为大于1的一个正整数，称为B-Tree的度。
  3. h为一个正整数，称为B-Tree的高度。
  4. 每个非叶子节点由n-1个key和n个指针组成，其中d<=n<=2d。
  5. 每个叶子节点最少包含一个key和两个指针，最多包含2d-1个key和2d个指针，叶节点的指针均为null 。
  6. 所有叶节点具有相同的深度，等于树高h。
  7. key和指针互相间隔，节点两端是指针。
  8. 一个节点中的key从左到右非递减排列。
  9. 所有节点组成树结构。
  10. 每个指针要么为null，要么指向另外一个节点。
  11. 如果某个指针在节点node最左边且不为null，则其指向节点的所有key小于v(key1)v(key1)，其中v(key1)v(key1)为node的第一个key的值。
  12. 如果某个指针在节点node最右边且不为null，则其指向节点的所有key大于v(keym)v(keym)，其中v(keym)v(keym)为node的最后一个key的值。
  13. 如果某个指针在节点node的左右相邻key分别是keyikeyi和keyi+1keyi+1且不为null，则其指向节点的所有key小于v(keyi+1)v(keyi+1)且大于v(keyi)v(keyi)。

定义看起来很复杂，其实并只要对照下图注2来仔细的观察一下就能很容易的理解了。

B-Tree相较于红黑树的一个特性在于它的高度很低，这意味着从根节点到叶子节点只需要经过很少的路径，使用B-Tree就能够让我们的查找次数降低，同时就会意味着硬盘的读取操作次数减少，减少了硬盘查找这样的耗时操作就能够提高了索引的查找速度。在查找到我们想要的数据位于某个B-Tree的节点之后，我们就把整个节点读入内存，根据局部性原理，当我们使用到一个数据的时候，接下来我们很有可能还会用到这个数据附近的数据，所以如果之后再有数据查找操作，我们可以先对内存中已经存在的数据进行查找，如果没有再去硬盘中进行查找，这样就可以提高查找效率。除此之外，对于已经加载到内存中的数据，我们可以使用我们熟悉的红黑树或AVL进行组织，这样也能一定程度上提高数据的查找速度。

B-Tree还有很多的变种（B+Tree、B*Tree等等），它们都是为了提升某些具体的特性的，这里就不介绍了，感兴趣的朋友可以去了解了解。

InnoDB索引实现

InnoDB的索引是用B+Tree实现的，不过它和我们之前说的不太一样的地方在于它的数据本身是存储在B+Tree的叶子节点上面的（也就是说索引和数据是存放在一起的，这种索引叫聚集索引），而这棵树是由这张表的主键来构建的，所以到这里你应该明白为啥InnoDB数据库会强制要求一张表必须包含有主键了，因为没有主键没法构建B+Tree，也就没有办法存储数据了啊╮（╯＿╰）╭。

InnoDB另一个有趣的地方在于它除了主键以外的索引都是指向了主键索引的，也就是说这些索引保存的不是记录的真正的地址，而是保存了该条数据的主键索引的值，查找过程为 索引 -> 主键索引 -> 真正的记录。理解了以上的过程之后对我们使用InnoDB的索引也是有指导意义的，例如使用自增的字段做主键可以保证B+Tree本身不会为了自身的有序性而频繁的改变结构，提高了插入的效率。

索引最左匹配原则

我们知道索引可以不加在一个字段而是加在多个字段上面，这种称为联合索引。其实联合索引的工作方式很简单，例如我们利用 name 和 age 两个字段做联合索引，那么我们会先根据 name 字段来创建B+Tree，只有当name字段相等的时候我们则会使用age字段来决定数据插入的位置。这样的结果就是：

  1. 我们可以使用 name 和 age 两个字段来进行查找，我们优先使用name字段进行查找，当 name 相等的时候我们就使用age字段查找
  2. 我们可以依然可以单独使用 name 字段来进行查找，因为 name 字段本身在索引中就是有序的，所以查找效率依然很高
  3. 但是，我们不能单独使用 age 字段来在索引中进行查找，因为 age 字段的有序性是依赖于 name 字段的，从整个索引中来说 age 字段是无序的，所以单独使用 age 字段查找将会进行全表扫描，这是相当低效的

我们举个例子，例如要对某次考试的成绩进行排序，我们排序的第一条规则是总分，当总分相等时我们则会使用语文的分数进一步排序。那么我们想要找总分为350分的学生就很快，因为总分是有序的；我们找总分340分同时语文为150分的学生也很快，只要先找到总分为340分的学生，之后再根据顺序找到语文为150的学生即可；但是单纯查找语文成绩为160分的学生则非常慢，因为语文成绩本身是无序的，所以你必须遍历一遍所有的学生之后把成绩为160分的学生找出来才行，这自然耗时很长。

讲了这些其实就是想说我们在联合索引中因为只有最左边的字段是完全有序的，所以如果我们想只根据联合索引中某单个字段进行查找，那么这个字段只应该是联合索引的最左字段，因为除了最左字段之外的任何字段的查找都将导致全表扫描，效率十分低下。由此你也可以看出，索引最左匹配规则其实只在联合索引中才有意义。

注1：这些定义皆摘取于此篇文章：http://blog.codinglabs.org/articles/theory-of-mysql-index.html
注2：图片摘自 http://blog.codinglabs.org/uploads/pictures/theory-of-mysql-index/2.png
注3：关于最左匹配规则可以参考 mysql索引最左匹配原则的理解?