1 概述

索引可以认为是存储引擎建立的一种数据结构，用来快速的根据查询条件来找到所需要的数据。由于数据一般存放在磁盘中，每次访问磁盘的时间都会比较长，因此，为了减少对磁盘的访问次数，存储引擎一般使用B-树结构来保存索引。
索引可以减少服务器层需要扫描的数据量，可以帮助服务器避免排序，将随机IO变为顺序IO。

下面讲我们常见的数据B-树结构的索引。

2 B-树索引

B-树通常有如下图所示的结构。

红色部分为索引所在列的值，白色部分为指向叶子页的指针，绿色部分为叶子页中指向下一个相邻页的指针。
蓝色的箭头为指向数据的指针，不同的存储引擎的实现不一样，主键索引和非主键索引也不同。之后再说。

当我们需要查询 where key = x条件时，且x < key1, x = Val1.2。那么，就会将叶子页1从磁盘读入内存，发现x = Val1.2所对应的数据的指针。那么，就可以根据指针去读取数据了。这样，就避免了对整个表的扫描。

2.1 多列索引（或联合索引）

联合索引在创建时，key的值是多个，在节点页内部和节点页之间按照顺序排列。比如,key(name, age, department），则首先按照name排序，如果name相同，则按照age排序，最后为department。

因此，联合索引可以起作用的场景为：

• where name = x and age = x and department = x。称为全值匹配，即所有的条件均有。
• 匹配最左前缀。比如，where name = x 或者 where name = x and age = x。原因是，根据这个数据结构，首先是按照name排序的，那么，就可以根据name来筛选。如果跳过name，直接使用where age = x，则不能从这个数据结构中得到排序后的结果。
• 匹配最左前缀的开头部分。比如，where name = “A%”，则可以匹配所有名字以A开头的。
• 匹配最左前缀的范围值。比如，名字在A%和B%之间的。

2.2 聚簇索引

聚簇索引是一种索引类型，也是一种数据存储方式，它将索引和数据存储在一起，结构如下图所示。它的数据行实际上存放在叶子页中。“聚簇”的意思就是，将数据行和相邻的键值紧凑的存放在一起。因为无法将数据行同时存放在两个索引数据结构中，因此，一个表只会有一个聚簇索引。一般而言，InnoDB会将主键索引当做聚簇索引，也就是说，该索引的数据结构中，键值为主键的值。聚簇索引的优点有：

• 数据是按照主键大小顺序排列的。因此，根据主键查找范围值时，速度会比较快，可能某个范围的值都在一个页中。
• 如果走聚簇索引，速度会很快，因为读索引时就可以读到数据了。但是，这也是在走主键索引的情况下（一般主键索引才是聚簇索引）。

缺点如下：

• 如果数据全都存放在内容中，则聚簇索引的优势就没有了。
• 插入速度依赖于插入顺序。比如，如果id使用聚簇索引，已经插入的记录为id = 1, id = 3，叶子页规定最大为2，前面两个已经成为一个叶子页了，这时候再插入id = 2，那么，前面的叶子页就得分裂，让id = 1, id = 2成为新的叶子页。因为，得保证按照主键的顺序排列数据。

2.3 InnoDB的索引方式和MyISAM的索引方式的对比

InnoDB的索引方式

主键索引：聚簇索引
二级索引（除主键之外其他列的索引存储方式）：实际保存的是主键值，之后还要根据主键索引去查询

MyISAM的索引方式

主键索引：非聚簇索引，直接保存的是行的物理地址
二级索引：与主键相同，保存的也是行的物理地址

下面通过一个例子来解释这些索引方式的区别。

假设需要存储的数据的表结构为：

需要插入的数据为：主键（使用主键索引）取值为1到10000，按照随机顺序插入；列col2（使用二级索引）的值从1到1000之间的随机值。

1. MyISAM的数据存储方式
   MyISAM按照数据插入的顺序存储在磁盘上。如下图所示。这种数据存储方式也很简单。

2. MyISAM的主键索引和二级索引
   MyISAM的主键索引和二级索引，key是被索引的列，叶子页保存的是行的物理地址。
   主键索引结构如下：叶子页中保存的是key值（列值）和行的物理地址。叶子页内部和叶子页之间，也是按照col1（主键）的列值进行排序的。
   二级索引结构如下：
   
   叶子页中保存的也是key值（列值）和行的物理地址，这与主键索引相同。叶子页内部和叶子页之间，按照col2的列值进行排序。

3. InnoDB的主键索引
   InnoDB的主键索引使用的聚簇索引，因此，数据存储方式不同于MyISAM，结构如下：叶子页保存的就是需要存储的数据。TID是事务ID，RP为回滚指针，这两者都是与事务有关的，这里不做讨论。这里的数据行的存放方式，是按照主键大小的顺序排序的。（注意，MyISAM是按照插入顺序来排列的）因此，如果InnoDB的数据插入方式不是按照主键的顺序插入的，InnoDB需要做额外的工作来是数据有序。
   因此，在使用InnoDB时，应该尽可能的按照主键顺序插入数据，并且尽可能的使用单调增加的主键来插入新行，避免页分裂操作。

4. InnoDB的二级索引
   InnoDB的二级索引的叶子页保存的是列值（key值）和主键值。在根据二级索引查询时，先找到主键值，然后再走主键索引，去查询数据。优点：当出现行移动物理位置或者页分裂时，减少了叶子页的维护工作。因为保存的是主键值，不是物理地址。
   缺点：根据二级索引查询时，需要再走主键索引，才可以查询到数据。即需要两次查询。（但是，如果需要查询的数据只有主键，则省去了第二步的主键索引的查询。这是覆盖索引的情况，通过这个索引，就可以拿到所需要的数据了。）

2.4 覆盖索引

当可以通过索引就可以获取到数据时，就不需要读取数据行了。这样的索引，就是覆盖索引。如果一个索引包含所有需要查询的字段的值，就称之为覆盖索引。需要考虑两方面：1）要查询哪些字段；2）被索引的是哪些列。

2.5 使用索引来避免排序

因为索引是按照顺序来存储key值的，因此，对于一些排序操作，就可以利用索引来获取想要排序的结果。

4 总结

在选择索引和查询时，应该记住三个原则：

• 单行访问是很慢的，特别是在机械硬盘存储中，从存储中读取一个数据块获得其中一个行（全表扫描），这是很慢的。使用索引，可以创建位置引用，就可以提升访问的效率了。
• 按顺序访问范围数据是很快的。原因之一为顺序IO不需要多次磁盘寻道，之二为能够顺序读取数据，那么，就不需要额外的排序操作了。
• 覆盖索引查询是很快的，可以直接从索引拿到数据，不需要读取数据文件了。