MYSQL面试题

001. MySQL如何实现的索引机制

MySql中的索引分3类：

B+树索引
哈希索引
全文索引

002. InnoDB索引和MyISAM索引实现的区别是什么？

索引方式上：
InnoDB索引分为聚簇索引和非聚簇索引，而MyISAM都是非聚簇的。同时InnoDB的表中有且只有一个聚簇索引。他们都是B+树索引。
从结构层面来看：
InnoDB的索引文件和数据文件不是分开的（索引文件就是数据文件），而MyISAM的索引文件和数据文件是分开的。
同时，两个索引都是基于B+树索引，不同的是，MyISAM的叶子节点是由一个指向数据文件的指针和索引值组成的。这表明，从索引的叶子节点查询到了数据，还需要通过这个指针去页中再一次查询到row数据。
而InnoDB分聚簇索引和非聚簇索引，对于聚簇索引来说，叶子节点存储的就是用户记录，可以直接返回；对于非聚簇索引来说，叶子节点存储的是索引值和对应主键，需要二次回表操作（是查询聚簇索引）。
从回表速度上来看：
MyISAM索引（二级索引）和InnoDB的非聚簇索引（二级索引）来看，MyISAM直接通过偏移量进行文件查询，而InnoDB根据主键ID再次去聚簇索引中查询，所以MyISAM回表速度快。
其他不同：
InnoDB需要指定唯一且有序的主键，这是为了保证更好的生成聚簇索引。
MyISAM的表在磁盘上的存储文件为：.sdi(描述表结构),.MYD(数据),.MYI(索引)
InnoDB的表在磁盘上的存储文件为：.ibd

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

答案是会，如果有主键，会根据主键生成一个聚簇索引；如果没有设置主键，MySQL会隐式的为每一行生成一个RowID,再根据这个RowID生成一个聚簇索引。

004. 说一下B+树实现原理？

B + 树是多路平衡查找树，为磁盘 IO 场景设计（数据库 / 文件系统索引核心），是 B 树的磁盘友好优化版，核心设计目标：降低树高减少磁盘 IO + 极致优化范围查询，所有实现围绕m 阶规则和平衡性展开，以下是核心要点：

核心定义（m 阶）

m 为节点最大子节点数，所有操作的基础规则：
根节点：子节点数 1~~m；非根中间节点：子节点数⌈m/2⌉~~m；
叶子节点：关键字数⌈m/2⌉~m，所有叶子节点在同一层（保证平衡）；
树空时根节点即为叶子节点，树高增长仅根节点分裂。

核心结构（三层设计，与 B 树核心差异）

节点按磁盘页大小对齐（减少 IO），内部存有序关键字数组 + 指针 + 元信息，分层专属设计是优化核心：
中间 / 根节点：仅存关键字 + 子节点指针，不存实际数据（最大化存储关键字，降低树高），关键字为子树分界值；
叶子节点：唯一存储实际数据（索引键 + 数据地址 / 行记录），所有叶子节点通过双向链表串联（为范围查询设计）。

核心操作（遵守 m 阶规则，平衡为前提）

所有操作最终落地叶子节点，核心逻辑：满则分裂、空则合并 / 借位，磁盘 IO 次数 = 树的高度：
查找：分点查询（根→中间节点二分找子节点→叶子节点二分找数据）、范围查询（点查询找到左边界→沿叶子链表遍历），范围查询无需回溯，是核心优势；
插入：关键字仅插入叶子节点，插入后若节点超阶则分裂（按中间位置拆分为左右节点，分界关键字向上提升至父节点，父节点超阶则递归分裂）；
删除：仅从叶子节点删除关键字，删除后若节点关键字数不足则先向兄弟节点借位，借位失败则与兄弟节点合并（同时父节点删除对应分界关键字，父节点不足则递归合并 / 借位）。

核心特性（实现带来的核心价值）

多路性：单节点存多个关键字，树高极低（远低于二叉树），大幅减少磁盘 IO；
平衡性：所有叶子节点同层，查询效率稳定，无单边倾斜问题；
磁盘友好：节点与磁盘页对齐，一次 IO 加载一个节点，中间节点不存数据，最大化 IO 利用率；
范围查询高效：叶子节点双向链表串联，一次点查询 + 链表遍历即可完成，无需回溯中间节点；
关键字副本性：中间节点关键字是叶子节点的副本，插入 / 删除仅需维护叶子节点，中间节点仅做索引指引。

与 B 树核心区别（面试高频）

B 树：中间 + 叶子节点均存数据，关键字唯一，范围查询需回溯，磁盘 IO 利用率低；
B + 树：仅叶子节点存数据，中间节点是关键字副本，叶子链表支持高效范围查询，节点存储密度更高、树更低。

005. 聚簇索引与非聚簇索引b+树实现有什么区别？

聚簇索引

特点：

索引和数据保存在同一个B+树中
页内的记录是按照主键的大小顺序排成一个单向链表 。
页和页之间也是根据页中记录的主键的大小顺序排成一个双向链表 。
非叶子节点存储的是记录的主键+页号。
叶子节点存储的是完整的用户记录。
优点：
数据访问更快，因为索引和数据保存在同一个B+树中，因此从聚簇索引中获取数据比非聚簇索引更快。
聚簇索引对于主键的排序查找和范围查找速度非常快。
按照聚簇索引排列顺序，查询显示一定范围数据的时候，由于数据都是紧密相连，数据库可以从更少的数据块中提取数据，节省了大量的IO操作 。
缺点：
插入速度严重依赖于插入顺序，按照主键的顺序插入是最快的方式，否则将会出现页分裂，严重影响性能。因此，对于InnoDB表，我们一般都会定义一个自增的ID列为主键。
更新主键的代价很高，因为将会导致被更新的行移动。因此，对于InnoDB表，我们一般定义主键为不可更新。
限制：
只有InnoDB引擎支持聚簇索引，MyISAM不支持聚簇索引。
由于数据的物理存储排序方式只能有一种，所以每个MySQL的表只能有一个聚簇索引。
如果没有为表定义主键，InnoDB会选择非空的唯一索引列代替。如果没有这样的列，InnoDB会隐式的定义一个主键作为聚簇索引。
为了充分利用聚簇索引的聚簇特性，InnoDB中表的主键应选择有序的id，不建议使用无序的id，比如UUID、MD5、HASH、字符串作为主键，无法保证数据的顺序增长。

非聚簇索引

（二级索引、辅助索引）

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

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

一张表可以有多个非聚簇索引：

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

核心定调：聚簇索引是主键构建的 B + 树，叶节点直接存整行数据，无回表开销，查找 IO 次数 = B + 树高度，是效率最高的索引查找方式，分主键等值匹配和主键范围匹配两类，均基于 B + 树核心特性实现。

前置核心前提（查找逻辑的基础）

索引键为表的主键，整棵树关键字均为主键值；
中间 / 根节点：仅存主键关键字 + 子节点指针，无行数据；
叶子节点：按主键升序连续存储，直接存放整行记录（物理存储与主键逻辑顺序一致，即 “聚簇”），叶子节点通过双向链表串联。

主键等值匹配（如 where id=100）：根→中→叶，纯二分无回表

根节点加载到内存，二分查找定位目标主键的子节点指针；
逐层遍历中间节点，重复「加载 + 二分 + 找子节点指针」；
定位到目标叶子节点后，二分查找匹配主键，直接取出整行数据，无额外操作。

主键范围匹配（如 where id between 100 and 200）：点查定左界，链表遍历右界

先按等值匹配逻辑，找到范围左边界主键所在的叶子节点；
从该叶子节点开始，沿双向链表依次遍历后续叶子节点；
逐个取出链表中符合主键范围的整行数据，直到超出右边界为止。

核心优势（与非聚簇索引对比）

全程无回表开销，等值匹配为单路径遍历，范围匹配依托链表无需回溯，磁盘 IO 仅为树的高度，是数据库中主键查询效率最优的方式。

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

核心定调：非聚簇索引以非主键字段为索引键构建 B + 树，叶节点仅存「索引键 + 主键值」，无整行数据，查找核心是先索引层匹配取主键，再回表查聚簇索引获数据，整体 IO 次数 = 非聚簇索引树高度 + 聚簇索引树高度，支持等值 / 范围匹配，是与聚簇索引的核心区别。

前置核心前提

索引键为非主键字段（支持单字段 / 联合 / 唯一索引），树的关键字为该字段值，允许重复；
中间 / 根节点：仅存索引键 + 子节点指针，无任何行数据；
叶子节点：按索引键升序存储，仅存「索引键值 + 对应行主键值」，叶子节点通过双向链表串联；
强依赖聚簇索引：必须通过主键值回表，才能获取整行数据，回表是核心特征。

等值匹配（如where name=’张三’）：索引层取主键 → 聚簇层回表

遍历非聚簇索引树（根→中间→叶子），每层二分查找定位子节点，最终在叶子节点匹配索引键，取出对应主键值；
以该主键值为条件，执行聚簇索引的等值匹配逻辑，在聚簇索引叶子节点直接获取整行数据。

范围匹配（如where age between 20 and 30）：索引层遍历取主键 → 逐一键回表

遍历非聚簇索引树，按范围匹配逻辑（点查定左界 + 链表遍历），取出范围内所有索引键对应的主键值；
对每个主键值，依次执行聚簇索引等值匹配，逐个回表获取对应整行数据（若主键值多，会产生多次回表 IO）。

核心特点（与聚簇索引对比）

多回表步骤，IO 开销更高；
叶子节点不存实数据，仅做 “索引键→主键值” 的映射；
唯一非聚簇索引与普通非聚簇索引逻辑一致，仅索引键值不重复，回表时主键值唯一。

优化点（面试延伸）

覆盖索引：若查询字段仅为索引键 + 主键，无需回表，直接从非聚簇索引叶子节点取数；
联合索引：按最左匹配原则匹配索引键，减少无效遍历，降低回表次数。

008. 平衡二叉树，红黑树，B树和B+树的区别是什么？都有哪些应用场景？

平衡二叉树
- 基础数据结构
- 左右平衡
- 高度差大于1会自旋
- 每个节点记录一个数据
平衡二叉树（AVL）
- AVL树全称G.M. Adelson-Velsky和E.M. Landis，这是两个人的人名。
- 平衡二叉树也叫平衡二叉搜索树（Self-balancing binary search tree）又被称为AVL树，可以保证查询效率较高。
- 具有以下特点：
  - 它是一棵空树或它的左右两个子树的高度差的绝对值不超过1
  - 并且左右两个子树都是一棵平衡二叉树。
- AVL的生成演示：https://www.cs.usfca.edu/~galles/visualization/AVLtree.html
AVL的问题
- 众所周知，IO操作的效率很低，在大量数据存储中，查询时我们不能一下子将所有数据加载到内存中，只能逐节点加载（一个节点一次IO）。如果我们利用二叉树作为索引结构，那么磁盘的IO次数和索引树的高度是相关的。平衡二叉树由于树深度过大而造成磁盘IO读写过于频繁，进而导致效率低下。
- 为了提高查询效率，就需要减少磁盘IO数。为了减少磁盘IO的次数，就需要尽量降低树的高度 ，需要把原来“瘦高”的树结构变的“矮胖”，树的每层的分叉越多越好。针对同样的数据，如果我们把二叉树改成三叉树：
- 上面的例子中，我们将二叉树变成了三叉树，降低了树的高度。如果能够在一个节点中存放更多的数据，我们还可以进一步减少节点的数量，从而进一步降低树的高度。这就是多叉树。
普通树的问题
- 左子树全部为空，从形式上看，更像一个单链表，不能发挥BST的优势。
- 解决方案：平衡二叉树(AVL)
红黑树
- hashmap存储
- 两次旋转达到平衡
- 分为红黑节点
- 在这个棵严格的平台树上又进化为“红黑树”{是一个非严格的平衡树左子树与右子树的高度差不能超过1}，红黑树的长子树只要不超过短子树的两倍即可！
B+ 树和 B 树的差异：
- B+树中非叶子节点的关键字也会同时存在在子节点中，并且是在子节点中所有关键字的最大值（或最小）。
- B+树中非叶子节点仅用于索引，不保存数据记录，跟记录有关的信息都放在叶子节点中。而B树中，非叶子节点既保存索引，也保存数据记录。
- B+树中所有关键字都在叶子节点出现，叶子节点构成一个有序链表，而且叶子节点本身按照关键字的大小从小到大顺序链接。