一、MyISAM存储引擎索引实现

1.1 存储位置

1.2 MyISAM索引结构

MyISAM索引文件和数据文件是分离的(非聚集)

MyISAM引擎，叶子节点的data存的是索引所在行的磁盘空间地址。

MyISAM引擎，它的主键索引，跟数据是分开存储的，它存储的是数据对应的磁盘空间地址，跟数据没有放在一起，这种就叫做非聚集索引，也叫非聚簇索引。

1.3、MyISAM索引查找过程

假如有一个sql select * from table where Col1 = 30;

mysql先判断Col1是不是索引，如果是，在这个树上进行判断，定位到叶子节点30，然后，取出磁盘空间地址。

拿出来之后，到MYD文件中，快速的定位到磁盘空间地址，把这行数据拿出来。

二、InnoDb存储引擎索引实现

2.1 存储位置

对于MySQL的InnoDB存储引擎，它有两个文件，frm存储表结构，Ibd文件既存储索引，又存储数据。

2.2 InnoDB索引结构

表数据文件本身就是按B+Tree组织的一个索引结构文件

聚集索引-叶子节点包含了完整的数据记录

非叶子节点不存储data，只存储索引(冗余)，可以放更多的索引

叶子节点包含所有索引字段

叶子节点用指针连接，提高范围查找性能。

为什么非主键索引结构叶子节点存储的是主键值？(一致性和节省存储空间)

与MyISAM不同，InnoDB叶子节点，存的是列数据，不再是索引所在行的磁盘空间地址。

这里就引出了聚集索引：

聚集索引，也就是聚簇索引，叶子节点包含了完整的数据记录，也就是说，你的索引，包括你的索引所在行的其他数据，都是放在一起的。这就是聚集索引。

InnoDB的主键索引，它就是聚集索引。

2.3 问题

为什么建议InnoDB表必须建主键，并且推荐使用整型 自增主键？

InnoDB底层要靠主键，来组织数据表数据，通俗点，就是要靠主键，来维护这个B+树。

但是，当我们对一张表不建主键时，发现也没有报错。其实，是Mysql底层为我们做了这件事。

它会看我们的每一列是否有唯一的这些数据列，如果有，就用这一列来组织树结构。

假如，连这个唯一的数据列也没有，那么，它会建一个唯一的隐藏列row_id，来维护B+树。

Mysql本身资源就很紧张了，所以，这些我们能做的一定要尽量做，尽量建立主键，

为什么要保证是整型且自增呢？

因为，mysql插入以及维护的时候，是有序的。

在查找数据的时候，会牵扯到很多比较，整型比大小，相比于uuid之类的字符串比大小要快的多。另外，整型相比于uuid类似的字符串，会更加节省空间。

假如，不是自增插入，由于B+树要维护索引的有序性，如果插入到之前页的数据，但是这些页16KB已经满了，就会涉及到B+树的分裂，影响性能。

如果，都是用自增的，每次都是往现有数据的后面插入数据。

B+Tree为什么可以提高范围查询性能？

首先，Mysql是一个排好序的数据结构，叶子节点都有一个双向指针进行连接。

假如，我们要查找col>20这些数据，我们可以先查col=20对应叶子节点的位置，定位到以后，由于都是排好序的，只需要依次往后遍历即可查出所有。

对于col<20，也是一样，因为叶子节点存有向前的指针，也是可以很方便查出所有数据。

2.4 辅助索引

辅助索引，也叫二级索引，它的叶子节点存储的是我们主键

那为什么Mysql要这么涉及，为什么不像主键索引那样，依旧做聚集索引呢？

因为，节省空间，对于我们的数据项是很耗费空间的，所以，mysql对于，二级索引，叶子节点直接存储主键索引，然后，再根据查找到的主键索引，到主键索引树里，查找对应的记录，这个过程叫做回表。

三、聚簇索引和非聚簇索引

mysql的innodb引擎的聚集索引和非聚集索引网上看到很多资料，有的叫innodb的索引为聚集索引，有的叫做聚簇索引，其实都是一样的，只是在翻译过来了时候命名产生了分歧，聚簇(集)索引的叶子节点就是数据节点。

而非聚簇(集)索引的叶子节点仍然是索引节点，只不过有指向对应数据块的指针。非聚簇(集)索引在innodb引擎中，又叫做二级索引，辅助索引等。

聚簇索引并不是一种单独的索引类型，而是一种数据存储方式。术语‘聚簇’表示数据行和相邻的键值聚簇的存储在一起。如下图，左侧的索引就是聚簇索引，因为数据行在磁盘的排列和索引排序保持一致。、

（1）聚集索引（聚簇索引）

以 InnoDB 作为存储引擎的表，表中的数据都会有一个主键，即使你不创建主键，系统也会帮你创建一个隐式的主键。

这是因为 InnoDB 是把数据存放在 B+ 树中的，而 B+ 树的键值就是主键，在 B+ 树的叶子节点中，存储了表中所有的数据。

这种以主键作为 B+ 树索引的键值而构建的 B+ 树索引，我们称之为聚集索引。

（2）非聚集索引（非聚簇索引）

以主键以外的列值作为键值构建的 B+ 树索引，我们称之为非聚集索引。

非聚集索引与聚集索引的区别在于

非聚集索引的叶子节点不存储表中的数据，而是存储该列对应的主键，想要查找数据我们还需要根据主键再去聚集索引中进行查找，这个再根据聚集索引查找数据的过程，我们称为回表。

明白了聚集索引和非聚集索引的定义，我们应该明白这样一句话：数据即索引，索引即数据。

聚簇索引的好处：

按照聚簇索引排列顺序，查询显示一定范围数据的时候，由于数据都是紧密相连，数据库不用从多个数据块中提取数据，所以节省了大量的io 操作。

聚簇索引的限制：

对于mysql 数据库目前只有innodb 数据引擎支持聚簇索引，而Myisam 并不支持聚簇索引。由于数据物理存储排序方式只能有一种，所以每个Mysql 的表只能有一个聚簇索引。一般情况下就是该表的主键。

为了充分利用聚簇索引的聚簇的特性，所以innodb 表的主键列尽量选用有序的顺序id，而不建议用无序的id，比如uuid 这种。

参考、参考、视频教程、索引