刚刚学习完丁奇老师《MySql 实战 45 讲》专栏中的索引部分，图文并茂的风格解开了我之前的许多疑惑，并且学习到许多新的东西，在此做个笔记，方便后续复习。由于 MySql 中存在多种存储引擎，每种存储引擎的实现方式都不太一样，而 InnoDB 在现在是比较流行的存储引擎，因此以下内容都是基于 InnoDB 讨论的。

索引是如何存储的

InnDB 索引是基于 N叉树实现的，为什么要使用 N叉树而不是二叉树呢？这是因为 MySql 中的数据都是存储在磁盘中的，我们查找数据都要进行 IO 操作，IO 操作比 CPU 运行的速度慢了一个等级，使用二叉树存储数据时，当我们从一个节点出发，要找它的子节点，就得进行一次 IO 操作，当数据库存储的数据多了之后，二叉树的层数变高，进行数据查找时 IO 操作也变多了。为了减少数据查询时的 IO 操作，InnDB 底层是使用 N叉树存储的，这个 N 取决于数据块的大小。

主键索引、非主键索引

上面说到，InnoDB 索引是基于 N叉树实现的，但是一个表我们需要建立的索引个数不止一个，因此每建立一个索引，InnoDB 就会创建一颗 N叉树来维护该索引数据，索引树建立完之后 InnDB 是如何通过索引找出我们所需要的数值的呢？

假设有一张表是这个样子的：

create table T(
  id int primary key,
  k int not null,
  name varchar(16),
  index(k))engine = InnDB;
)

这张表显示创建了一个索引 k，还包含一个默认的主键索引 id，InnDB 是按照如下方式来存储这两颗索引树的：

可以看到，主键索引的叶子节点是一个数据块，每个数据块就是一个行记录，包含 id 、k、name 的值，这就叫做主键索引，而索引 k 的叶子节点包含的数据是 id 值，这就是非主键索引。在这个表中，当我们需要根据某个 k 的值查找对应的 name 值，需要先根据 k 的值找出对应的 id 值，再根据 id 值查找对应的数据块，从数据块中才可以得知 name 的值。在 InnDB 里，主键索引也被称为聚簇索引，非主键索引也被称为二级索引。

覆盖索引

上面说到当使用二级索引查找其他字段值时，需要查找两颗索引树才可以找到对应字段的值，这是因为二级索引的叶子节点只包含主键值，如果在二级索引的叶子节点已经包含了我们要查找的内容，那么就可以减少一次查询，提升性能。例如刚刚的那张表，我们需要根据 k 值来找 id，此时二级索引的叶子节点已经包含了我们需要的数据，我们称此为覆盖索引。

我们可以根据具体的业务场景来创建覆盖索引，比如根据身份证 id 查找身份证号这个需求是很常见的，我们就可以给身份证 id 和身份账号建立一个联合索引，这样根据身份证 id 找出来的数据块就包含了身份证号，不用再根据主键去寻找身份证号了。

索引重建

这个是丁奇老师在专栏里面留下的问题：对于上面例子中的 InnDB 表 T，如果要重建索引 k，两个 SQL 语句可以这么写：

alter table T drop indexk;
alter table T add index(k);

如果要重建主键索引，也可以这么写：

alter table T drop primary key;
alter table T add primary key(id);

对于上面两个重建索引的做法，有不合适的地方吗？为什么？有更好的方法吗？

回答：上面的语句中，重建索引 k 的方式合理，但是重建主键的过程不合理。不论是删除主键还是创建主键，都会将整个表重建，所以连着执行两个语句，第一个语句就白做了，这两个语句，可以使用 alter table T engine = InnDB 代替。

该索引是否是必须的

这是老师留下的另一个问题：DBA 小吕在入职新公司的时候，就发现自己接手维护的库里面，有这么一个表，表结构定义类似这样的：

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`)
)

公司的同事告诉他，由于历史原因，这个表需要 a、b 做联合主键，这个小吕理解了。但是，学过本章的内容的小吕又纳闷了，既然主键包含了 a、b 这两个字段，那意味这单独在字段 c 上创建一个索引，就已经包含了这三个字段，为什么要创建 “ca”、“cb” 这两个索引？同事告诉它，是因为他们的业务里面有这样的两种语句：

select * from geek where c=N order by a limit 1;
select * from geek where c=N order by b limit 1;

问题是，这位同事的解释对吗，为了这两个查询模式，这两个索引是否都是必须的？为什么呢？

回答：我们一个一个来分析，首先是主键索引（a、b），主键索引先按照 a 排序，然后按照 b 排序，索引 c 就是按照 c 进行排序，在叶子节点中包含主键，即先按照 c 排序，然后按照 a 排序，接着按照 b 排序。索引 ca 先按照 c 排序，然后按照 a 排序，主键部分包含 b，这样看的话它和索引 c 存储的内容是一样的。索引 cb 先按照 c 排序，然后按照 b 排序，主键部分包含 a。经过上面分析，索引 ca 是可以去掉的，因为它的作用和索引 c 是一样的。