为什么需要索引

索引就像书籍的目录一样，可以更快的查找数据。

常见的索引模型

innodb 索引模型选用B+树是由MySQL的应用场景（等值区间查找、插入删除等操作频繁）及机械磁盘的特点（寻址耗时）决定的。像Redis等一些Nosql数据库，他们的索引模型就是哈希表、跳表等。

• 数组
  • 等值查询很快（数组有序排列的情况下，二分查找）
  • 区间查询很快
  • 数据的插入删除很慢
• 哈希表
  • 等值查询极快
  • 插入删除极快
  • 区间查询很慢（只能一个个的查找）
• 搜索树（链表）
  • 二叉搜索树
    • 等值查询、区间查询很快，效率等于数组的二分查找
    • 插入删除效率logN，需要树的再平衡，再平衡的效率也是logN
  • 多叉搜索树树
    • 相比于二叉树，多叉树一次寻址能取出更多的数据，能大大减少寻址次数
    • 一个节点下面，叶子节点的个数取决于硬盘上数据块的大小

MySQL的应用场景中，等值查询和区间查询是很高频的场景，插入删除操作也十分频繁，因此综合考虑，搜索树最适合作为底层的存储引擎。又因为机械硬盘时代，磁盘寻址的时间成本很高，因此 innodb 底层的那存储引擎选用的索引模型是B+树。

本文后续主要介绍innodb的索引。

Innodb中的索引

主键索引和非主键索引

主键索引： 主键索引的叶子结点（最后一层）存储的是数据库的行数据。

非主键索引： 非主键索引的叶子节点（最后一层）存储的是主键索引。

对于一个查询操作，查询条件如果是主键索引，则直接返回结果；如果是非主键索引，则先返回主键，然后根据主键查询主键索引树，再返回结果。

查询原则：尽量使用主键索引查询。

索引类别

innodb中不同索引类别的特点如下：

• 普通索引
  • 没有任何限制
• 唯一索引
  • 索引列的值唯一
  • 允许有空值
  • 组合索引，列值必须唯一
• 主键索引
  • 只能作用于一个列上
  • 键值唯一
  • 不能为空

业务上，如果只有一个索引，并且是唯一索引，可以直接用该字段建立索引（尽量使用主键索引查询原则）

索引维护

插入数据或者删除数据，都涉及到索引表的调整。

插入数据的时候，有可能会导致叶子节点数据的挪动，也可能导致数据页的分裂。(对性能的影响需要结合B+树的增删改查操作)

删除数据的时候，一般只是对数据标记下删除，并不会立即调整索引树，除非索引树中被删除的数据过多，浪费了大量的空间，则需要重建索引树。

自增主键的优势

• 主键自增，索引树不需要维护主键的有序性
• 自增ID占空间较小，非主键索引树占用的空间更小

索引从性能和存储上考虑，自增ID都是更好的选择。

想象以下，一个用户信息表，如果索引选择身份证号码，那每次新增一条数据，为了保证索引有序，都有可能导致一个数据块上数据重新排列，也能导致一个数据块分裂，显然更耗时。

如果这个用户信息表还有其它非主键索引树，那它的叶子节点存储的都是18位的身份证号码，显然消耗的空间相较于自增ID要更多

覆盖索引

覆盖索引只是一种场景，或者一种现象，构造出这种现象有利于提高查询性能。

先看一个查询的例子。如果我们有如下的一张表：

mysql> create table T (
ID int primary key,
k int NOT NULL DEFAULT 0, 
s varchar(16) NOT NULL DEFAULT '',
index k(k))
engine=InnoDB;

insert into T values(100,1, 'aa'),(200,2,'bb'),(300,3,'cc'),(500,5,'ee'),(600,6,'ff'),(700,7,'gg');

如果执行如下语句，需要查询几次？

select * from T where k between 3 and 5;

答：查询非主键索引树3次，回表2次。

同样如果执行下面的语句，需要查询几次？

select id from T where k between 3 and 5;

答：查询非主键索引树3次，不需要回表。

如果索引树的查询结果已经包含了我们需要的结果，不需要回表，这种情况就称为覆盖索引。覆盖索引是常用的一种性能优手段。

联合索引和最左前缀原则

联合索引和最左前缀原则并没有什么必然的联系，这里放在一起讨论是因为联合索引的查找过程会应用到最左前缀原则。

最左前缀原则

B+ 树这种索引结构，可以利用索引的“最左前缀”，来定位记录。

查询的时候，如果查询条件是索引的最左N个字段，或者最左N个字符，都能用上索引，加快查询速度。

如何安排联合索引的顺序

联合索引是按照索引项的顺序建立索引的，如（A，B），建立索引的时候，是先按A排序，然后对同一个A，再按B排序，检索的顺序也是如此，先检索A，再检索B。所以建立联合索引的时候，一定要考虑索引的复用 程度。复用程度越高，越要放前面。

显然如果建立了联合索引（A，B），索引A是不需要单独建立索引的。

回到之前的覆盖索引，如果有个高频的需求是根据用户的身份证查询姓名，那有必要建立身份证号和姓名的联合索引吗？答案是不考虑索引维护的成本下是有必要的。

建立了身份证和姓名的联合索引之后，只需要查询联合索引树，就能直接返回查询结果而不需要回表，大大提高查询性能。

当然，索引的维护是有代价的。因此建立冗余的索引来实现覆盖索引就需要权衡考虑了。

实践

题目：对于如下表，由于历史原因，联合索引（a, b）是必须的，那这里面有不必要的索引吗？

CREATE TABLE `geek` (
  `a` int(11) NOT NULL,
  `b` int(11) NOT NULL,
  `c` int(11) NOT NULL,
  `d` int(11) NOT NULL,
  PRIMARY KEY (`a`,`b`),
  KEY `c` (`c`),
  KEY `ca` (`c`,`a`),
  KEY `cb` (`c`,`b`)
) ENGINE=InnoDB;

答：ca是不必要的索引。

对于联合索引（a，b），其内部的组织是先根据a排序，再根据b排序，因此索引树c的内容其实是cab，即先根据c排序，再根据a排序，再根据b排序的一个B+数据。索引树（c，a）的叶子节点实际上是b，树的内容也是cab，和索引树c是一致的，因此ca索引树是不必要的。

---