MySQL数据库 - 索引（上）

目录

1 简介

1.1 索引是什么

1.2 为什么要使用索引

2 索引应该选择哪种数据结构

2.1 HASH

2.2 二叉搜索树

2.3 N叉树（B树）

2.4 B+树

3 MySQL的页

3.1 为什么要使用页

3.2 页文件头和页文件尾 

3.3 页主体

3.4 页目录

4 B+树在MySQL索引中的应用

5 索引分类

5.1 主键索引

5.2 普通索引

5.3 唯一索引

5.4 全文索引

5.5 聚集索引

5.6 非聚集索引

5.7 索引覆盖

---

1 简介

1.1 索引是什么

MySQL的索引是一种数据结构，它可以帮助数据库高效地查询、更新数据表中的数据。索引通过一定的规则排列数据表中的记录，使得对表的查询可以通过对索引的搜索来加快速度。

MySQL索引类似于书籍的目录，通过指向数据行的位置，可以高速定位和访问表中的数据，比如汉语字典中的目录（索引）页，我们可以按笔画、偏旁部首、拼音等排序的目录（索引）快速查找到需要的字。

1.2 为什么要使用索引

显而易见，使用索引的目的只有一个，就算提升数据检索的效率，在应用程序运行的过程中，查询操作的频率远远高于增删查改的频率。

2 索引应该选择哪种数据结构

2.1 HASH

时间复杂度：O（1）  ，是最重要的数据结构，没有之一。

缺点：不支持范围查找。

MySQL没有采用此数据结构。

2.2 二叉搜索树

中序遍历是一个有序序列--->支持范围查找

时间复杂度：O(n)

缺点：

节点个数过多时，无法保证树高。

由于数据库上的数据都是在磁盘中保存的，每一次访问子节点都会都会发生一次磁盘IO

磁盘IO是制约数据库性能的主要因素。

因此数据库没有采用二叉搜索树的数据结构。

2.3 N叉树（B树）

N叉树每个节点都可以有超过两个的子节点，可以解决树高问题。

时间复杂度：O（logN）

在数据量相同的情况下，可以有效控制树高，也就是可以使用更少的IO找到目标节点，从而提高数据库的效率。

然而MySQL并没有采用此数据结构。

2.4 B+树

B+树是一种经常用于数据库和文件系统等场合的平衡查找树，是MySQL索引采用的数据结构，以三阶B+树为例，如下图所示：

时间复杂度：O（logN）

优点：可以有效控制树高

B+树与B树对比：

1.叶子节点之间有一个相互连接的引用，可以通过一个叶子节点找到它相信的兄弟节点。

MySQL在组织叶子节点时使用的是双向链表。

2.非叶子节点的值都保存在叶子节点中。

MySQL非叶子节点只保存了对叶子节点的引用，没有保存真实的数据，所有真实的数据都保存在叶子节点中。

3.对于B+树而言，在相同树高的情况下，查找任一元素的时间复杂度都一样，性能均衡。

3 MySQL的页

3.1 为什么要使用页

在.ibd文件中最重要的结构体就是Page（页），页是内存与磁盘交互的最小单元，默认大小为16KB,每次内存与磁盘的交互至少读取一页，所以在磁盘中每个页内部的地址都是连续的，之所以这样做，是因为在使用数据的过程中，根据局部性原理，将来要使用的数据大概率与当前访问的数据在空间上是临近的，所以一次从磁盘中读取一页的数据放入内存中，当下次查询的数据还在这个页中时就可以从内存中直接读取，从而减少磁盘I/O，提高性能。

---

MySQL每创建一张表，就会生成一个.ibd文件。这个.ibd文件被称为独立表空间文件。

MySQL中有很多页类型，这里只讨论数据页（或者叫做索引页）

3.2 页文件头和页文件尾 

页文件头和页文件尾中包含的信息，如下图所示：

这里我们只关注，上一页页号和下一页页号，通过这两个属性可以把页与页之间链接起来，形成一个双向链表。

通过页号和页大小，可以计算出下一页和上一页在磁盘上的偏移量（或者叫地址）

3.3 页主体

页主体部分是保存真实数据的主要区域，每当创建一个新页，都会自动分配两个行：一个是页内最小行Infimun,另一个是页内最大行Supermun。这两个行并不存储任何真实信息，而是作为数据行链表的头和尾，第一个数据行有一个记录下一行的地址偏移量的区域next_record将页内所有数据行组成一个单向链表，此时新页的结构如下图所示：

当向一个新页插入数据时，将Infimun连接第一个数据行，最后一行真实数据行连接Supermun，这样数据行就构建成了一个单向链表，更多的行数据插入后，会按照主键从小到大的顺序进行链接，如下图所示：

3.4 页目录

分组：数据行的的分组，每个分组最多可以容纳8条记录，超过8条记录时会分裂出来一个新的组。

注意：最小行单独为一个组，最大行永远在最后一个组。

创建分组时会在页目录中创建一个槽，槽的数量与分组的数量一致，槽会指定对应分组的最后条记录，同时保存这条记录的主键值。

查询某条记录的步骤：

1.首先要找到这个记录所在的页

2.在页中找到所在的槽

3.在分组中找到对应的记录

4 B+树在MySQL索引中的应用

非叶子节点保存索引数据，叶子节点保存真实数据，如下图所示：

以查找id为5的记录，完整的检索过程如下：

1.首先判断B+树的根节点中的索引记录，此时5<7，应访问左孩子节点，找到索引页2.

2.在索引页2中判定id大小，找到与5对等的记录，命中，

以上的IO过程：加载索引页1 -->加载索引页2 -->加载数据页3

共三次IO

5 索引分类

5.1 主键索引

当在一个表上定义一个主键时，该表会自动创建索引，索引的值是主键列的值，InnoDB使用它作为聚集索引（或者叫聚簇索引）。

推荐为每个表定义一个主键。如果没有逻辑上唯一且非空的列或列集可以使用主键，则添加一个自增列。

5.2 普通索引

最基本的索引类型，没有唯一性的限制。

可能为多列创建组合索引，称为复合索引或组全索引

5.3 唯一索引

当在一个表上定义一个唯一键UNIQUE时，自动创建唯一索引。

与普通索引类似，但区别在于唯一索引的列不允许有重复值。

5.4 全文索引

基于文本列（CHAR、VARCHAR或TEXT列）上创建，以加快对这些列中包含的数据查询和DML操作

用于全文搜索，仅MyISAM和InnoDB引擎支持。

5.5 聚集索引

与主键索引是同义词。

如果没有为表定义PRIMARY KEY，InnoDB使用第一个UNIQUE和NOT NULL的列作为聚集索引。

如果表中没有PRIMARY KEY或合适的UNIQUE索引，InnoDB会为新插入的行生成一个行号并用6字节的ROW_ID字段记录，ROW_ID单调递增，并使用ROW_ID作为索引。

（ROW_ID是数据行中的一个隐藏列之一）

5.6 非聚集索引

聚集索引以外的索引称为非聚集索引或二级索引。

二级索引中的每条记录都包含该列的主键列，以及二级索引指定的列。

InnoDB使用这个主键值来搜索聚集索引中的行，这个过程称为回表查询。

5.7 索引覆盖

当一个select语句使用了普通索引且查询列表中的列刚好是创建普通索引时的所有或部分列，这时就可以直接返回数据，而不用回表查询，这样的现象称为索引覆盖。

---

完

如果哪里有疑问的话欢迎来评论区指出和讨论，如果觉得文章有价值的话就请给我点个关注还有免费的收藏和赞吧，谢谢大家！