《尚硅谷MySQL数据库面试题宝典，mysql面试必考！mysql工作必用！》2022-11-29

https://www.bilibili.com/video/BV1N24y1y7a1

# P1 MySQL 如何实现的索引机制

MySQL 中索引分三类：B+ 树索引（InnoDB、MyISAM）、Hash 索引（配合 B+ 树索引）、全文索引

# P2 InnoDB 索引和 MyISAM 索引实现的区别是什么？

## MyISAM

MyISAM 索引文件和数据文件是分离的，使用 B+ 树实现，主键索引和辅助索引实现一致，索引文件仅保存记录所在页的指针（物理位置），通过这些地址来读取页，进而读取被索引的行。

- InnoDB 的辅助索引 data 域存储相应记录主键的值而不是地址
- InnoDB 的数据文件本身就是主索引文件
- MyISAM 的索引和数据是分开存储的。

# P3 一个表中如果没有创建索引，那么还会创建 B+ 树吗？

指定了主键，就会拿主键创建聚簇索引

没有主键，也会创建聚簇索引。索引生成的是隐式的 row id

# P4 说一下 B+ 树索引实现原理（数据结构）

假设有一个表 index_demo，表中有 2 个 INT 类型的列，1 个 CHAR(1) 类型的列，c1 列为主键：

```mysql
CREATE TABLE index_demo(c1 INT, c2 INT, c3 CHAR(1), PRIMARY KEY(c1));
```

index_demo 表的简化的行格式示意图如下：

| record_type | next_record      | c1 列    | c2 列    | c3 列    | 其他信息       |
| ----------- | ---------------- | -------- | -------- | -------- | -------------- |
| 记录的类型  | 记录的下一条记录 | 记录列值 | 记录列值 | 记录列值 | 记录的其他信息 |

我们只在示意图里展示记录的这几个部分：

- `record_type`：表示记录的类型，0 是普通记录，2 是最小记录，3 是最大记录，1 是 B+ 树非叶子节点记录
- `next_record`：表示下一条记录的相对位置，我们用箭头来表明下一条记录。
- `各个列的值`：这里只记录在 index_demo 表中的三个列，分别是 c1、c2 和 c3。
- `其他信息`：除了上述 3 种信息以外的所有信息，包括其他隐藏列的值以及记录的额外信息。

把一些记录放到页里的示意图就是（这里一页就是一个磁盘块，代表一次 IO）：

（图略）

**MySQL InnoDB 默认的页大小是 16KB**，因此数据存储在磁盘中，可能会占用多个数据页。如果各个页中的记录没有规律，我们就不得不依次遍历所有的数据页。如果我们想快速的定位到需要查找的记录在哪些数据页中，我们可以这样做：

- 下一个数据页中用户记录的主键值必须大于上一个页中用户记录的主键值
- 给所有的页建立目录项

以 **页28** 为例，它对应**目录项2**，这个目录项中包含着该页的**页号28**以及该页中用户记录的**最小主键值 5**。我们只需要把几个目录项在物理存储器上连续存储（比如：数组），就可以实现根据主键值快速查找某条记录的功能了。**比如：查找主键值为 20 的记录，具体查找过程分两步**：

1. 先从目录项中根据二分法快速确定出**主键值为 20 的记录在目录项 3 中**（因为 12 <= 20 < 209），对应页9
2. 再到页 9 中根据二分法快速定位到主键值为 20 的用户记录。

至此，针对数据页做的简易目录就搞定了。这个目录有一个别名，称为**索引**。

## InnoDB 中的索引方案

我们新分配一个编号为 30 的页来专门存储**目录项记录**，页10、28、9、20 专门存储**用户记录**

目录项记录和普通的用户记录的不同点：

- 目录项记录的 record_type 值是 1，而普通用户记录的 record_type 值是 0。
- 目录项记录只有主键值和页的编号两个列，而普通的用户记录的列是用户自己定义的，包含很多列，另外还有 InnoDB 自己添加的隐藏列。

现在查找主键值为 20 的记录，具体查找过程分两步：

1. 先到页 30 中通过二分法快速定位到对应目录项，因为 12 <= 20 < 209，就是页9
2. 再到页 9 中根据二分法快速定位到主键值为 20 的用户记录。

**更复杂的情况如下：**

我们生成了一个存储更高级目录项的页 33，这个页中的两条记录分别代表页 30 和页 32，如果用户记录的主键值在 `[1, 320)` 之间，则到页 30 中查找更详细的目录项记录，如果主键值不小于 320 的话，就到页 32 中查找更详细的目录项记录。**这个数据结构，它的名称是 B+ 树**。

# P5 聚簇索引与非聚簇索引 B+ 树实现有什么区别？

## 聚簇索引

特点：

- **索引和数据保存在同一个 B+ 树中**
- **页内的记录**是按照主键的大小顺序排成一个**单向链表**
- **页和页之间**也是根据页中记录的**主键**的大小顺序排成一个**双向链表**
- 非叶子节点存储的是记录的**主键+页号**
- 叶子节点存储的是**完整的用户记录**。

优点：

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

缺点：

- 插入速度严重依赖于插入顺序，按照主键的顺序插入是最快的方式，否则将会出现页分裂，严重影响性能。因此，对于 InnoDB 表，我们一般都会定义一个**自增的 ID 列为主键**。
- 更新主键的代价很高，因为将会导致被更新的行移动。因此，对于 InnoDB 表，我们一般定义**主键为不可更新**。

限制：

- 只有 InnoDB 引擎支持聚簇索引，**MyISAM 不支持聚簇索引**。
- 由于数据的物理存储排序方式只能有一种，所以**每个 MySQL 的表只能有一个聚簇索引**。
- 如果没有为表定义主键，InnoDB 会选择**非空的唯一索引列代替**。如果没有这样的列，InnoDB 会**隐式的定义一个主键**作为聚簇索引。
- 为了充分利用聚簇索引的聚簇特性，InnoDB 中表的**主键应选择有序的 id**，不建议使用无序的 id，比如 UUID、MD5、HASH、字符串作为主键，无法保证数据的顺序增长。

## 非聚簇索引

（二级索引、辅助索引）

**聚簇索引**，只能在搜索条件是**主键值**时才发挥作用，因为 B+ 树中的数据都是按照主键进行排序的，如果我们想以别的列作为搜索条件，那么需要创建**非聚簇索引**。

例如，**以 c2 列作为搜索条件**，那么需要使用**c2 列创建一棵 B+ 树**

这个 B+ 树与聚簇索引有几处不同：

- **页内的记录**是按照从**c2 列**的大小顺序排成一个**单向链表**
- **页和页之间**也是根据页中记录的 **c2 列**的大小顺序排成一个**双向链表**。
- 非叶子节点存储的是记录的 **c2 列 + 主键**这两个列的值。
- 叶子节点存储的并不是完整的用户记录，而只是 **c2 列 + 主键**这两个列的值。

# P6 说一下 B+ 树中聚簇索引的查找（匹配）逻辑

# P7 说一下 B+ 树中非聚簇索引的查找（匹配）逻辑