MySQL索引的数据结构：常见的索引概念

索引按照物理实现方式，可以分为两种，聚簇（聚集）索引，和非聚簇（聚集）索引。我们把非聚簇索引也称为二级索引或者辅助索引。

---

1. 聚簇索引并不是一种单独的索引类型，而是一种数据存储方式（所有用户记录都存储在叶子节点），也就是数据即索引，索引即数据。

聚簇表示数据行和相邻的键值局促的存储在一起。

---

1.1 特点

（1）使用记录主键值的大小进行记录和页的排序，这包括三方面的含义：
页内的记录是按照主键的大小顺序组成的一个单向链表。
各个存放用户记录的页，也是根据用户记录的主键的大小顺序排成一个双向链表。
各个存放目录项记录的页，分为不同层次，在同一层次内，也是根据用户记录的主键的大小顺序拍成一个双向链表。
（2）B+树的叶子节点，存储的是完整的用户记录。
所谓的完整的用户记录，就是指这个记录中存储了所有列的值（包括隐藏列）。
我们把具有这两种特征的B+树称为聚簇索引，所有完整的用户记录都存放在聚簇索引的叶子节点，这种聚簇索引不需要我们自己去创建，InnoDB引擎会自动的为我们创建聚簇索引。

---

1.2 优点

● 数据访问更快，因为聚簇索引将索引和数据保存在同一个B+树中，因此从聚簇索引中获取数据比非聚簇索引快。
● 聚簇索引对于主键的排序查找和范围查找速度非常快。
● 按照聚簇索引排序，查询显示一定范围数据的时候，由于数据都是紧密相连的，数据库不用从多个数据快中提取数据，节省了大量的I/O操作。

---

1.3 缺点

● 插入速度严重依赖于插入顺序，按照主键顺序插入最快，否则会出现页分裂，严重影响性能，因此，对于InnoDB表，一般都会定义一个自增列为主键。
● 更新主键的代价很高，因为更新的主键行会进行移动。
● 二级索引需要两次索引查找，第一次找到主键值，第二次根据主键值知道到行数据。

---

1.4 限制

● 对于MySQL数据库，只有InnoDB支持聚簇索引，MyISAM不支持。
● 由于数据的物理存储排序方式只有一种，所以只能有一个聚簇索引，一般是该表的主键为聚簇索引。
● 如果没有定义主键，InnoDB会选择非空的唯一索引代替，如果没有这样的索引，会自动创建一个隐式的自增主键索引作为聚簇索引。
● 为了充分利用聚簇索引的特性，建议使用顺序主键，而不是使用无序主键。

---

2. 二级索引（辅助索引，非聚簇索引）

2.1 什么是二级索引

上边介绍的聚簇索引，只有在搜索条件是主键的时候才能发挥作用。
如果是搜索其他列，则需要建立相关的索引，即非聚簇索引，非聚簇索引也是B+树的存储方式，只不过叶子节点存储的不是完整的用户记录，而是对应的列值，和主键值。

根据上图可知：
● 非聚簇索引，根据索引列的大小排序
● 非聚簇索引的叶子节点存放的不是完整数据，而是列的值和主键值。

---

2.2 回表

如果，根据非主键列c2进行查找所有的用户记录，先根据二级索引找到主键值，再根据主键值查找聚簇索引找到对应的行数据，这个过程称为回表。也就是说，二级索引需要查找两颗b+树。

为什么不在二级索引中也存放完整的用户记录？
二级索引个可以有很多个，如果每个二级索引都存放完整的用户记录，造成空间浪费，太冗余。

非聚簇索引不影响数据在聚簇索引中的组织，所以可以有多个非聚簇索引。

---

2.3 聚簇索引与非聚簇索引的区别

● 聚簇索引的叶子节点存放的是完整的用户记录，非聚簇索引存放的是数据的位置，非聚簇索引不会影响数据的物理存放顺序。
● 聚簇索引只能有一个，非聚簇索引可以有多个。
● 非聚簇索引查询效率高，但是插入，删除不如非聚簇索引效率高。

---

3. 联合索引

我们可以同时以多个列进行建立索引，以多个列的大小作为排列顺序，比如我们建立c2和c3的联合索引，则需要：
● 先把各个记录和页按照c2的顺序排列
● 在c2列顺序相同的情况下，采用c3列的排序
为c2和c3建立联合索引的示意图如下：

如图所示，我们需要注意以下几点
● 每条目录项记录都由c2，c3，和页码这三个部分组成，每条记录先按c2的顺序排序，如果c2顺序一样，则按c3的顺序排序。
● B+树的叶子节点处，记录的是c2，c3和主键的值。