Loading...
墨滴

jrh

2021/10/16  阅读:23  主题:橙心

Java 4

前言

这是系列文章【 Java 面试八股文】数据库篇的第一期。

【 Java 面试八股文】系列会陆续更新 Java 面试中的高频问题,旨在从问题出发,理解 Java 基础,数据结构与算法,数据库,常用框架等。该系列前几期文章可以通过点击文末给出的链接进行查看~

按照惯例——首先要做几点说明:

  1. 【 Java 面试八股文】中的面试题来源于社区论坛,书籍等资源;感谢使我读到这些宝贵面经的作者们。
  2. 对于【 Java 面试八股文】中的每个问题,我都会尽可能地写出我自己认为的“完美解答”。但是毕竟我的身份不是一个“真理持有者”,只是一个秉承着开源分享精神的 “knowledge transmitter” & 菜鸡,所以,如果这些答案出现了错误,可以留言写出你认为更好的解答,并指正我。非常感谢您的分享。
  3. 知识在于“融释贯通”,而非“死记硬背”;现在市面上固然有很多类似于“Java 面试必考 300 题” 这类的文章,但是普遍上都是糟粕,仅讲述其果,而不追其源;希望我的【 Java 面试八股文】可以让你知其然,且知其所以然~

那么,废话不多说,我们正式开始吧!

数据库篇(一)

1、请详细说明在 MySQL 中,一条 SQL 查询语句是如何执行的?


我们先来看一下 MySQL 的客户端架构示意图:

如上图中所示,MySQL 客户端可以分为 Server 层与存储引擎层两个模块。

select * from T where ID = 10

那么,像上面这条 SQL 查询语句在 MySQL 客户端是如何被执行并返回结果的呢?接下来,我们从客户端的这些模块开始逐一进行分析:

首先,MySQL 客户端要与服务端建立正确的连接,而确保这一点的正是连接器。

连接器主要的作用有两个:

  • 权限验证
  • 维持与管理连接

当我们输入命令:

mysql -h$ip -P$port -u$user -p$password

并且验证通过时,连接器会到权限表中查询出你目前登录的用户拥有的权限。

连接器的另外一个功能是维持与管理连接。客户端如果太久没有任何操作,那么连接器就负责自动断开连接,默认的超时时间为 8 小时。

当连接器确保 MySQL 客户端与服务端的连接建立完成后,便会来到查询缓存模块。需要注意的是,MySQL 8.0 版本开始便不再有查询缓存这个模块了。而查询缓存模块的功能也非常容易理解,当 MySQL 客户端拿到了一个查询请求之后,就会在查询缓存模块中查看之前是否有执行过这条语句,如果有,那么就会将缓存的结果直接返回。不过我们可以想象一下,为什么 MySQL 8.0 开始废除了查询缓存这一功能?

其实原因很简单,查询缓存往往是弊大于利的。因为,如果我们的表有任何修改,那么查询缓存便会全部失效。这样我们既浪费了内存,也没有得到查询缓存带来的好处。对于更新频次非常快的数据表,命中查询缓存的概率不仅很低,而且浪费内存空间。所以,从 MySQL 8.0 起,干脆彻底取消了查询缓存功能。

如果这条 SQL 查询语句在查询缓存中没有命中,那么就会来到分析器模块。

分析器主要的功能有三个:

  • 词法分析
  • 语法分析
  • 语义分析

简单来说,分析器的功能就是判断你写的 SQL 查询语句是否满足 MySQL 的语法规则,并且弄清楚你这条 SQL 语句到底在做什么。

通过分析器的分析后,这条 SQL 查询语句便会来到优化器模块。

优化器会对我们的 SQL 语句进行优化,譬如,我们的表中有多个索引,优化器会决定优先使用哪一个索引,又或者一个查询语句涉及到多表关联时,优化器会决定各个表的连接顺序,找出最佳的执行方案。

当我们的查询语句经过优化器模块优化之后,就会进入到执行器模块。

执行器,故名思义,其功能为调用存储引擎并执行 SQL 语句。如果语句执行后有返回结果就将查询的结果集返回。

我们的查询语句为:

select * from T where ID = 10

在这个查询语句中,ID 字段是没有索引的,执行器便会调用默认的 InnoDB 引擎接口(InnoDB 是 MySQL 5.5.5 版本开始默认的存储引擎),开始执行语句,执行流程如下所示:

  1. 调用 InnoDB 引擎接口,取这个表的第一行数据,判断 ID 值是不是 10,如果不是则跳过,如果是则将这行记录存在结果集中;
  2. 调用 InnoDB 引擎接口取“下一行”,重复相同的判断逻辑,直到取到这个表的最后一行。
  3. 执行器将上述遍历过程中,所有满足条件的行组成的记录作为结果集返回给客户端。

如果 ID 字段有索引,那么也非常简单,执行器会调用 InnoDB 引擎接口,取出索引树的第一行数据,判断其值是否符合条件,如果是则将记录存在结果集中,如果不是就取索引树的下一条数据。

以上过程,就是一条 SQL 查询语句在 MySQL 客户端的全部执行流程。

总结

这是一道 MySQL 经典的面试问题,旨在考察面试者对 MySQL 客户端架构的了解程度。

面试官的问法可能不仅仅局限于此,他可能会直接地问:MySQL 框架有几个组件,各个组件的作用是什么?

如果基础掌握不太牢固的童鞋可以自行搜索一下,这些组件具体的功能~

2、请谈一下 MySQL 中,redo log,binlog 这两种日志的区别?


我会先向大家介绍这两种日志的功能,然后再来比较它们之间的区别。

先来看一张图:

这是一条更新语句在各个模块执行的顺序图,虽然目前这张图还不全面,但是在我们稍后会将这个框架图陆续补充完整。

首先,在 Server 层中,一条 update 语句仍然会依次通过连接器,查询缓存,分析器,优化器,最后再由执行器调用 InnoDB 接口。这个部分的流程就不再赘述了,接下来我们将重点分析 InnoDB 存储引擎和磁盘之间的联系。

我们首先要知道一点,数据一定是落到磁盘上的,相信大家对磁盘与内存都有着充分的认知,我就不再介绍他们二者的区别了。

当执行器调用 InnoDB 存储引擎接口来执行一条更新语句时,我们首先会在 InnoDB 的 Buffer Pool 里查看是否有我们要修改的数据页,如果有,那么我们就直接修改 Buffer Pool 里数据页的数据并直接将结果返回给执行器;否则就先从磁盘里将数据读到 Buffer Pool 的数据页中,然后再修改并返回。

Buffer Pool 是 InnoDB 引擎为了提升用户体验设计的缓存,如果我们每次修改数据都要不断从磁盘中读写,那么毫无疑问这种高成本的 IO 操作会严重影响性能。而在内存中操作的速度就非常快了,我们可以先在缓存中修改数据,等到“不那么忙”的时候再将缓存中“脏页”的数据同步到磁盘上。

不过,这样就会出现一个问题——如果我们缓存中的修改还没有同步到磁盘上就断电了怎么办?这不就导致数据丢失了嘛?

为了解决这个问题,MySQL 使用了一种技术叫做 WAL。WAL 的全称为 Write-Ahead Logging,即:先写日志。

在跟大家介绍什么是 WAL 之前,我们先来看一下 redo log 这个东西到底是啥?

redo log 是 InnoDB 独有的一种物理日志系统。为什么管他叫物理日志,这一点我们在后面会结合逻辑日志的概念一同解释。总之,redo log 是 InnoDB 引擎独有的,它包含了两部分:第一部分是在内存里面的日志缓冲 redo log buffer,另一部分是在磁盘上的日志文件 redo log file。我们通常说的 redo log 就是 redo log file,所以你可以把 redo log 也当成是磁盘的一块区域。

我们回过头再来看一条 update 语句的执行过程:首先 InnoDB 引擎会将数据查询并缓存到 Buffer Pool,然后会将 Buffer Pool 里面这页数据更新到 redo log buffer 中,再将 redo log buffer 写进 redo log file。而这种先写日志的技术就是 WAL。此时在 Buffer Pool 的数据页虽然还是脏页,但是可以慢慢同步到磁盘,并且因为 redo log 已经存储了脏页的更改,我们就可以保证即便出现断电或数据库发生异常重启,之前提交的更新都不会丢失,还可以从日志当中恢复,这种能力就是 crash safe

如上图所示,我们的框架图添加了 redo log 这一部分。

可能有的童鞋还会问这样的问题,既然脏页的数据从 Buffer Pool 同步到磁盘是在写磁盘,而 redo log buffer 中的数据写到 redo log file 也是在写磁盘,那为啥不直接将脏页的数据同步到磁盘,然后再写日志,感觉 WAL 这么设计完全没有必要啊?

其实不然,虽然 redo log 落盘的本质也是磁盘的 IO 操作,不过先写日志要比先写磁盘更快!因为,写日志采用的方式是顺序 IO,而写磁盘采用的方式则是随机 IO。

随机 IO 是指,我们的数据分散地分布在磁盘的不同页的不同扇区,如果我们要找到相应的数据就需要通过寻址操作定位到指定的页,然后再到对应的扇区中寻找我们需要的数据,因此访问速度较慢。

顺序 IO 是指读写操作的访问地址连续,定位到第一块数据后,就无需重新寻址,读/写 磁头可以以最小的移动访问下一块数据。

如果每次更新操作 InnDB 都要先写磁盘,那么每次都需要通过随机 IO 定位到磁盘的相应位置,这个过程是低效的。而先写日志是使用顺序 IO 的方式,效率则高的多。

在 InnoDB 中,redo log file 默认有两个文件分区,不过我们可以按照自己的业务需求来设置 redo log file 文件分区的数量以及每个文件分区的大小。比如我可以配置 redo log file 有 4 个文件分区,每个文件分区的大小是 1GB。这时,redo log 的大小就固定了,你可能会问,如果 redo log 写满了咋办?

如上图所示,redo log file 中有两个”标记指针“。write pos 记录了当前写到的位置,一边写一边往后移,当写到第 3 号文件末尾就会回到 0 号文件的开头。而 checkpoint 则是当前要擦除的位置,也是往后推移并且循环的,每当脏页的一部分数据落到磁盘时,checkpoint 就会向后推移一部分。如果 redo log file 写满会怎样呢?此时 MySQL 会停止所有的更新操作,将脏页数据刷到磁盘上,然后向后推移 check point,为 redo log file 腾出空间。

关于 redo log 的内容就暂时先谈这些,接下来我们看一下 bin log 是个啥子东西。

我们在上文已经说明了,redo log 是 MySQL InnoDB 存储引擎才有的物理日志系统,而 binlog 则是 Server 层的逻辑日志系统。

为啥 MySQL 要备两份日志?这要追溯到 MySQL 更早的版本。MySQL 从 5.5 版本开始规定默认的存储引擎为 InnoDB,而在这之前默认的存储引擎则是 MyISAM。了解 MyISAM 存储引擎的同学就知道,MyISAM 存储引擎并不具备 crash-safe 的能力,而 InnoDB 存储引擎则是另一个公司以插件形式引入到 MySQL 上的,就是为了弥补 MyISAM 无法从崩溃状态中恢复数据,不支持事务等不足。所以,MySQL 就有了这两种类型的日志系统。

接下来,我将介绍一下什么是物理日志(physical log),什么是逻辑日志(logical log)?

很多人都不明白物理日志与逻辑日志的概念,我举个例子🌰相信大家一下子就能明白了~

说老王和帅恒正在下国际象棋:

老王执黑,帅恒执白。正在你来我往之时,突然一阵狂风把二人的棋盘吹翻了。请问要怎么恢复棋盘的局面呢?

老王说:“这好办,我记得咋俩下的每一个步骤,你第一步走了马 b3,然后我第二步走了兵 c6...”

帅恒说:“害,这么麻烦干啥,我记得每个子的位置,咱们不用从头捋,按我说的摆就行!”

好了,我已经将什么是逻辑日志,什么是物理日志讲清楚了。

所谓的逻辑日志就是老王记住棋盘局面的方式,你可以认为逻辑日志记录的就是前后我们执行了哪些 sql 语句。而物理日志就是帅恒记住棋盘局面的方式,它记录了数据页具体做了什么改动。

binlog 和 redo log 还有一个重要的区别。我们知道 redo log 是固定大小的,采用循环写的方式;而 binlog 则是追加写的,“追加写”是指 binlog 文件写到一定大小后会切换到下一个数据页,并不会覆盖以前的日志,所以,binlog 也被称为归档日志。

讲到这里,你可能会觉得:“为啥 binlog 就不具备 crash-safe 的能力,我刚刚看你举老王帅恒下棋的例子,不是演示了使用逻辑日志做数据恢复的嘛?”

那么,我们就拿只有 binlog 没有 redo log 的情况来举个例子🌰:

我们知道 binlog 存储的是逻辑日志,假设 binlog file 中记录了两条更新语句:

  1. 给 ID=3 的这条记录的字段 A 加 1
  2. 给 ID=3 的这条记录的字段 A 加 2

而此时,脏页的数据还没有同步到磁盘中,磁盘中这条记录的字段 A 的值为 100,内存中的值为 103。

然后突然断电。

当我们重启数据库时,你就傻眼了,binlog file 虽然记录了两条更新语句,但是你并不知道此时磁盘上对应的 ID=3 的这条记录有没有刷盘更新过。

现在你应该明白为什么 binlog 不具备 crash-safe 的能力了。而 redo log 则不同,它呈现的是一种物理结构,在数据库重启后,我们只需要将 redo log 中的数据直接恢复至内存就可以了。

综上所述,redo log 和 binlog 这两种日志的区别如下:

  1. redo log 是 InnoDB 引擎特有的,而 binlog 则是 MySQL Server 层实现的,所有引擎都可以使用。
  2. redo log 是物理日志,而 binlog 是逻辑日志。
  3. redo log 是循环写的,空间固定会用完;binlog 则是追加写的。
总结

这个问题的答案其实只有最后这三行总结。

不过相信大家可以从我的解答中看到更多的与 redo log,binlog 相关的面试题:

譬如:

  • 什么是 WAL 技术?
  • 为啥要先写日志再写磁盘,顺序颠倒过来不行吗?
  • 什么是物理日志,什么是逻辑日志?
  • redo log 的大小是固定的吗?如果写完了会怎么样?
  • binlog 为什么不具备 crash-safe 的能力?
  • 等等......

3、基于主键索引的查询与普通索引的查询有什么区别?


如果没有特殊规定,那么我们默认 MySQL 使用的就是 InnoDB 存储引擎。

在 InnoDB 中,表是根据主键顺序以索引的形式存放的,每一个索引对应一棵 B+ 树。

例如,我们有一个主键为 ID 的表,表中有字段 k,并且在 k 上创建了普通索引,该表的建表语句为:

create table T(
  id int primary key
  k int not null
  name varchar(16),
  index (k)
)engine=InnoDB;

表中 R1~R5 的 (ID,k) 值分别为:(100,1),(200,2),(300,3),(500,5) 和 (600,6),主键索引与普通索引 k 的索引树示意图如下:

InnoDB 的主键索引是聚簇索引(clustered index),叶子节点存放的是 Page(页),也就是说数据文件和主键索引是绑在一起的;而非主键索引的叶子节点存放的则是主键的值,非主键索引也被成为二级索引(secondary index)。

那么,基于 InnoDB 引擎的主键索引查询和普通索引查询有什么区别呢?

如果我们的查询语句为:

select * from T where ID = 500;

在使用主键索引进行查询时,InnoDB 引擎内部只需要搜索主键索引这棵 B+ 树即可;

如果我们的查询语句为:

select * from T where k = 5

在使用普通索引进行查询时,InnoDB 就需要先搜索二级索引 k 的 B + 树,得到 ID 的值为 500,然后再到主键索引树搜索 ID 为 500 对应的数据。这个过程称之为回表。也就是说使用主键索引查询只需要查询一次查询,而使用普通索引则需要两次查询。

总结

如果面试官没有指定存储引擎,那么默认就是使用 InnoDB 存储引擎。

而 MyISAM 存储引擎在索引的实现上和 InnoDB 是不同的,虽然 MyISAM 索引的实现也是靠 B+ 树这种数据结构,不过它的实现方式是非聚簇索引。

MyISAM 索引和数据文件是分离的,索引树的叶节点存放的是数据的地址。MyISAM的主键索引(Primary Key)与辅助索引(Secondary key)在结构上没有任何区别,只是主键索引要求 key 是唯一的,而辅助索引的 key 可以重复。

下图为在 MyISAM 存储引擎中,主键索引与普通索引存储数据的表示方式:

4、你知道哪些索引模型?它们都有什么特点?为什么 InnoDB 采用的是 B+ 树这种索引模型?


先来简单谈一谈一些常用的索引模型。

1. 哈希表

哈希表是一种以键值对儿存储的数据结构,大概长成这样:

对于哈希表这种数据结构我就不再赘述了。我们需要知道的是向哈希表增删改查的时间复杂度均为 ,通常使用拉链法解决哈希冲突。

譬如,有一个学生表,并且我们对学生编号这个字段使用了索引。那么我们每次拿到一个学生编号,都可以在 的时间将数据查询并返回,似乎,哈希表作为底层索引模型是完美的。

此时我有一个需求,查询学生编号在 这个区间的所有用户。这时,哈希表的弊端就暴露出来了。因为在哈希表中,数据分布的位置是完全随机的,如果我们要查询某个范围区间的数据,就需要将整个哈希表全部扫面一遍。

所以,哈希表这种结构只适用于等值查询的场景,并不适用于范围查询。

2. 有序数组

有序数组这种数据结构大家肯定都不陌生。上图中,有序数组存储的元素按照 num 字段的值的递增顺序进行排序。

有序数组在等值查询与范围查询的场景中的性能就非常优秀了。我们的需求还是查询学生编号在 这个区间的所有用户。有序数组可以使用二分查找法,快速定位到 的位置,时间复杂度为 。然后向右顺序遍历,直到查找到第一个值大于 的数据,退出循环。

如果仅仅看查询效率,有序数组是最好的索引模型。不过在需要更新数据时,就麻烦了,譬如向有序数组中新增一条记录的时间复杂度为 ,如果更新操作比较频繁,那么有序数组很显然不是一个好的选择。所以,有序数组索引只适合用于静态存储引擎。

3. 红黑树

红黑树是一种经典的数据结构,其增删改查的时间复杂度均为

关于红黑树到底是怎么样的一种数据结构,在我往期的文章中有详细地讲解过,感兴趣的朋友不妨查阅一下~

红黑树既是一棵二分查找树,也是一棵平衡二叉树(黑节点绝对平衡,整体伪平衡),通过性能上来看,红黑树似乎是最优的选择,不过这需要一个前提,那就是所有的数据都需要在内存中查找。

不过,我们知道索引不仅仅存储在 InnoDB 的内存中,还要落到磁盘上。假如我们的红黑树高度为 20。那么,一次查询可能需要访问磁盘上 20 个数据块。这种高成本的 IO 会严重拖慢查询的性能。

那么究竟哪一种数据结构才适合作为索引模型呢?

4. B 树

我们的第一直觉是希望有像红黑树这样的平衡二叉查找树,并且它的高度能够尽可能地低,因为树的高度越低就意味着将耗费更少的磁盘 IO。

而 B 树就是这样的一种数据结构。B 树是一种多路平衡查找树,并且是一棵绝对平衡的多叉树,所谓的绝对平衡指的是,对于 B 树的任意一个节点,都保证子树高度是相同的。

如上图所示,这棵树是一棵 3 阶 B 树。对于 B 树的阶的定义为:一棵 阶 B 树中每个节点至多有 个孩子节点。

比起红黑树,B 树显然更“矮胖”一些。虽然查询一个元素,B 树的比较次数不比红黑树少,但是这些比较操作大部分都在内存中完成,而实际上的磁盘访问次数要比红黑树节省的多。

5. B+ 树

MySQL 默认的存储引擎 InnoDB 使用的索引模型为 B+ 树。

如上图所示,这就是一棵 B+ 树。

B+ 树与 B 树的主要区别有以下三点:

  1. B+ 树只有叶子节点会存储 data 数据,而其他的非叶子节点存储的是索引以及指针,是一个查询的范围区间。这就导致了在 B+ 树中查询的时间复杂度为 B+ 树的高度,是一个固定的值,而 B 树查询复杂度是不固定的,与 key 在树当中的位置有关。
  2. B + 树叶子节点是两两相连的,形成了一个有序的双向循环链表的结构。这就增加了区间的访问性,使得 B+ 树只需要遍历叶子节点就可以实现整棵树的遍历。
  3. B+ 树更适合外部存储,因为 B+ 树的节点无 data 域,这就使得每个节点能够存储更大的索引区间,所以 B+ 树在形状上比 B 树要更“矮胖”一些~

那么,为什么说 B+ 树要比 B 树更适合做数据库索引模型呢?

首先,B+ 树的磁盘读写代价要更低。我们已经说过了,B+ 树的每一个节点无 data 域,所以可以存储更大的索引区间。这就使得 B+ 树在存储和 B 树相同的数据量时,其高度更低,高度更低就会更节省磁盘 IO 的次数。

第二点,B+ 树的查询效率要更加稳定。和 B 树不同,B+ 树的 data 域存储在叶子节点上,所以关键字查询的路径长度相同,使得每一个数据的查询效率相当。

第三点,B+ 树比 B 树更适合做区间查询。因为 B+ 树的叶子节点两两相连,如果我们要扫一遍库,只需要遍历底层叶子节点形成的有序链表即可。而在数据库操作中,区间查询又是一个非常频繁的操作,所以 MySQL 最终选择 B+ 树作为存储引擎的索引模型。

总结

又是一个可以问出很多东西的面试题。

对于这道题目,面试官不仅考查了数据库相关知识,同时也考察了面试者对各种底层数据结构的了解程度,是一道非常好,且有意义的面试题。

5、什么是最左匹配原则?


举一个例子,user 表的建表语句如下:

create table `user` (
 ID int primary key,
  `name` varchar(32DEFAULT NULL
  `age` int(11DEFAULT NULL
  `ismale` tinyint(1DEFAULT NULL,
  KEY `name_age_ismale`(`name`,`age`,`ismale`)
)engine=InnoDB

我们创建了(name,age,ismale) 这三个字段的联合索引。

联合索引的最左匹配原则就是,当我们创建了(name,age,ismale) 这个联合索引时,会按照从左向右的顺序来建立索引树:

首先 B+ 树会比较 “name” 字段来排序,如果 “name” 列相同,再按照 “age” 进行排序,如果这个时候 “age” 列还是相同的,那么再按照 “ismale” 进行排序。

如果你的 sql 语句用到了联合索引中 “最左边的” 索引,那么这条 sql 语句是可以使用联合索引进行匹配的。通俗地讲,我们相当于创建了(name) 这个单列索引,(name,age) 这个联合索引以及 (name,age,ismale) 这三个字段组合的联合索引。值得注意的是,当遇到范围查询时,匹配就会停止。

例如:

select * from user where name = 'Jack'

这条语句是可以使用联合索引最左匹配原则进行匹配的。

select * from user where name = 'Jack' and age = 22

这条语句也是可以使用联合索引最左匹配原则进行匹配的。

select * from user where age > 18 and name = 'Jack'

这条语句是可以使用联合索引最左匹配原则进行匹配的,虽然 age > 18 这个条件不是一个等值匹配,但 name = 'Jack' 是一个等值匹配,优化器会先优化这条查询语句,颠倒条件顺序,优先匹配 name 字段,然后再匹配 age 字段。所以,这条语句的前半段可以用到 name 字段的索引。

select * from user where age = 18;

这条 sql 查询语句是无法使用联合索引进行匹配的,因为 age 字段相对于 name 字段有序,但是全局整体无序,并不符合最左匹配原则。所以单拿出 age 字段用不上联合索引。

总结

对于最左匹配原则这个知识点,很多面试题会通过以下这种形式进行考查~

已知查询条件为:

WHERE a = 1 AND b = 1
WHERE b = 1
WHERE b = 1 ORDER BY time DESC

如果只能创建一条索引,该如何创建?

本题的答案为:

以 b,a,time 这个顺序创建一个联合索引:

CREATE INDEX b_a_time ON T (b,a,time);

相信大家如果掌握了最左匹配原则,回答出这道题也不难。

总结

今天我主要分享了 MySQL 数据库中的一些面试常考题和知识点,后面的内容我会抓紧更新,敬请期待哦~

往期文章链接:

好啦,至此为止,这篇文章就到这里了~欢迎大家关注我的公众号,在这里希望你可以收获更多的知识,我们下一期再见!

jrh

2021/10/16  阅读:23  主题:橙心

作者介绍

jrh