24数据库开发复习

SEBugMaker version1.0

7-8道题

20%上机+80%期末

编程题

  • SQL 编程题

    3道题（数值、时间、字符串3选2），记住常见函数

    • 数值考虑空值
    • 时间，索引，日期的差
    • 中位数，众数不太容易考
    • 标注使用的数据库
    • 递归查询可能会考一个
    • 可能会用到外连接，数值？
    • 注意函数用对

NULL处理

MySQL提供了三大运算符:

  • IS NULL: 当列的值是 NULL,此运算符返回 true。
  • IS NOT NULL: 当列的值不为 NULL, 运算符返回 true。
  • <=>: 比较操作符（不同于 = 运算符），当比较的的两个值相等或者都为 NULL 时返回 true。

example

1
2
select * , columnName1+ifnull(columnName2,0) from tableName;
# columnName1，columnName2 为 int 型，当 columnName2 中，有值为 null 时，columnName1+columnName2=null， ifnull(columnName2,0) 把 columnName2 中 null 值转为 0。

数值型

函数 说明
abs(num) 返回 num 的绝对值
ceil(num) 返回大于 num 的最小整数值
floor(num) 返回小于 num 的最大整数值
mod(num1,num2) 返回 num1 对 num2 进行模运算结果
rand() 返回 0 到 1 内的随机值
round(num,n) 返回 num 的四舍五入的 n 位小数的值
truncate(num,n) 返回数字 num 截断为 n 位小数的结果
sqrt(num) 返回 num 的平方根

时间

函数 说明
DATE_FORMAT(date,format) DATE_FORMAT 根据 format 串格式化 date 值，每个格式符前必须包含 %。
输出格式如：2020-01-23 00:24:12
SELECT DATE_FORMAT(NOW(),’%Y-%m-%d %H:%i:%s’)
SELECT DATE_FORMAT(NOW(),’%Y-%m-%d %T’)
#输出格式如：20200123
SELECT DATE_FORMAT(NOW(),’%Y%m%d’)
#本月第一天，如：2020-01-01
SELECT DATE_FORMAT(NOW(),’%Y-%m-01’)
TIME_FORMAT(time,format) TIME_FORMAT()用法与 DATE_FORMAT()函数类似，但是格式字符串可能仅包含小时，分钟，秒和微秒的格式说明符。其他说明符产生 NULL 值或 0。
STR_TO_DATE(str,format) 将字符串转换成日期或者时间，或者日期时间，取决于给定的 format 包含了哪部分内容。如果 format 包含了日期和时间格式，将返回 datetime 类型的值；如果只包含日期格式，则返回 date 类型的值；如果只包含了时间格式，将返回 time 类型的值。
SELECT STR_TO_DATE(‘01/23/2020’,’%m/%d/%Y’);
SELECT STR_TO_DATE(‘Jan 23,2020’,’%M %d,%Y’);
SELECT STR_TO_DATE(‘23,01,2020 00:28:12’,’%d,%m,%Y %h:%i:%s’);
# 未指定日期或者时间部分的值为 0
SELECT STR_TO_DATE(‘abc’,‘abc’);
2020-01-23 2020-01-23 2020-01-23 00:28:12 0000-00-00
DATE_ADD(date,INTERVAL expr unit) date_add() 可用于日期、时间的加减计算，类似的函数还有 date_sub()、adddate()、addtime()、subdate()、subtime()。
date_add() 接收两个参数，第一个参数可以是 date 类型或者 datetime 类型，第二个参数是个间隔值，表示将在第一个参数的基础上增加或者减少某个单位时间的值。
SELECT DATE_ADD(‘2020-01-28’,INTERVAL 1 DAY);
SELECT DATE_ADD(‘2020-01-28 15:28:01’,INTERVAL 2 HOUR);
DATEDIFF(expr1,expr2) DATEDIFF() 函数用于计算两个日期之间相差的天数，计算方式是 expr1 - expr2。expr1 和 expr2 是日期或日期时间表达式，在计算中仅使用值的日期部分。
获取时间 获取当前日期可以使用 CURDATE()、CURRENT_DATE()、SYSDATE() 等函数。
同样的，获取当前时间可以使用 CURTIME()、CURRENT_TIME()、NOW()、CURRENT_TIMESTAMP()、SYSDATE()、LOCALTIME()、LOCALTIMESTAMP()。

字符串

递归

Oracle

在 Oracle 中是通过 start with connect by prior 语法来实现递归查询的。

MySQL

在MySQL中，递归查询可以使用WITH RECURSIVE语句来实现。该语句允许我们定义一个递归查询，并在查询中引用自身。

三个部分

  • 初始查询（Anchor Query）：这是递归查询的起点，返回初始结果集。它是递归查询的第一步。

  • 递归查询（Recursive Query）：这是递归查询的核心部分，它引用自身并定义了如何从上一层的结果集中继续查询下一层的数据。递归查询通常包含一个递归关系，通过引用父节点与子节点之间的关联来构建数据的层级结构。

  • 终止条件（Termination Condition）：这是递归查询的结束条件，用于指定何时停止递归查询。终止条件通常是基于已查询的数据的某种条件或限制。

执行步骤

  1. 执行初始查询，获取初始结果集。
  2. 将初始结果集作为递归查询的输入，执行递归查询，并将结果集与初始结果集合并。
  3. 重复执行递归查询，直到满足终止条件为止。

Example

1
2
3
4
5
6
7
8
9
CREATE TABLE `organization` (
  `org_id` int NOT NULL COMMENT '主键',
  `org_name` varchar(100) CHARACTER SET utf8mb4 COLLATE utf8mb4_general_ci NOT NULL COMMENT '组织名称',
  `parent_id` int DEFAULT NULL COMMENT '父组织id',
  `org_level` int DEFAULT NULL COMMENT '组织级别',
  PRIMARY KEY (`org_id`),
  KEY `parent_id` (`parent_id`),
  CONSTRAINT `organization_ibfk_1` FOREIGN KEY (`parent_id`) REFERENCES `organization` (`org_id`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4 COLLATE=utf8mb4_general_ci COMMENT='公司组织架构';
1
2
3
4
5
6
7
8
9
10
11
12
13
WITH RECURSIVE RecursiveOrganization AS (
  SELECT org_id, org_name, parent_id, org_level
  FROM organization
  WHERE parent_id IS NULL  -- 查找根节点
  UNION ALL
  SELECT o.org_id, o.org_name, o.parent_id, o.org_level
  FROM organization o
  INNER JOIN RecursiveOrganization ro ON ro.org_id = o.parent_id
)
SELECT org_id, org_name, parent_id, org_level
FROM RecursiveOrganization
ORDER BY org_id
LIMIT 2 OFFSET 0;  -- 设置每页的条目数量和偏移量

解析一下这个SQL：

  • 首先，使用WITH RECURSIVE子句创建了一个名为RecursiveOrganization的递归查询视图。

在初始查询部分，通过WHERE parent_id IS NULL条件查找根节点，选择了根节点的组织信息（org_id, org_name, parent_id, org_level）。

  • 然后，使用UNION ALL和INNER JOIN将递归查询与organization表连接起来，逐级递归获取下级组织的信息。通过SELECT o.org_id, o.org_name, o.parent_id, o.org_level选择下级组织的信息，并使用ON ro.org_id = o.parent_id指定连接条件。
  • 最后，从RecursiveOrganization视图中选择所需的组织架构数据，并使用ORDER BY对结果按org_id进行排序。通过LIMIT和OFFSET可以设置每页的条目数量和偏移量，实现分页查询。

索引

  • 索引

    索引叶节点的基本逻辑，叶/内部节点分裂/合并的逻辑

索引叶节点

B 树& B+树两者有何异同呢？

  • B 树的所有节点既存放键(key) 也存放数据(data)，而 B+树只有叶子节点存放 key 和 data，其他内节点只存放 key。
  • B 树的叶子节点都是独立的;B+树的叶子节点有一条引用链指向与它相邻的叶子节点。
  • B 树的检索的过程相当于对范围内的每个节点的关键字做二分查找，可能还没有到达叶子节点，检索就结束了。而 B+树的检索效率就很稳定了，任何查找都是从根节点到叶子节点的过程，叶子节点的顺序检索很明显。
  • 在 B 树中进行范围查询时，首先找到要查找的下限，然后对 B 树进行中序遍历，直到找到查找的上限；而 B+树的范围查询，只需要对链表进行遍历即可。

综上，B+树与 B 树相比，具备更少的 IO 次数、更稳定的查询效率和更适于范围查询这些优势。

同级指针

如果没有同级指针，必须通过⽗节点才能重新定位

最右指针

B 数拆分子树并进行遍历，指向子页的指针总比键的个数多一个（指针 N+1）

最右指针单独存放，其他键值+指针匹配存放

叶/内部节点分裂/合并的逻辑

分裂

B树的节点分裂步骤

Step 1:分配一个新节点

Step 2:一半元素从分裂节点复制到新节点点

Step 3:新元素放入相应的节点

Step 4:在分裂节点的父节点处，添加一个分割键和指向新节点的指针

合并

日志

  • 日志

    • redo日志
    • undo日志

    两者区别，如何完成（物理组织ppt）

redo日志

Redo log（重做日志） 的特点

  1. 占用空间很小
  2. 顺序写入磁盘（顺序 I/O）

redo日志的设计

  1. 静态结构
    • redo记录的结构
    • redo日志页需不需要设置大小？要不要比正常的Page大或者小？
    • redo日志是顺序组织还是随机组织？
  2. 动态结构
    • 事务的原子性如何保证？冲突如何控制？
    • redo日志也是双存储结构的，应该如何刷写？
  3. 维护实现
    • 如何循环使用redo？

格式

Redo 日志格式不同数据库有不同的定义，但整体的分类就这三种：

  1. 记录具体位置的物理修改
  2. 记录一个 page 的全部修改
  3. 记录操作（执行恢复的参数）

一些数据库也会做一些压缩操作，比如 space id，page number 等

Mini-Transaction

并发事务

redo log block

redo日志缓冲

redo log 的刷盘时机

  • log buffer空间不足（50%的阈值）
  • 事务提交时
  • 脏页刷新
  • 定时进程，固定频率刷新（1s，log buffer中的redo log刷新到硬盘）
  • 正常关闭服务器

lsn值（log sequence number）

check point

  • 理想状况，check point记录一次就行，但如果更新过快，可能需要多次记录
  • check point每执行一次，均要修改redo日志文件的管理信息
  • 后台刷脏操作和check point操作是两个并行的操作
    • 修改页面非常频繁，导致lsn快速增长，无法及时做checkpoint，则线程做刷脏操作
    • 定时完成check point操作

redo日志文件格式

  • log buffer本质上是一片连续的内存空间，被划分为若干个512k大小的block
  • redo日志刷新到磁盘是把block的镜像写入日志文件，文件也是若干个512k的block

恢复（Recovery）

  • 确定恢复的起点（checkpoint_lsn）
    • 选取最近发生的那次checkpoint的信息，checkpoint_no比较一下大小
    • 然后找checkpoint_lsn以及checkpoint_offset
  • 确定恢复的终点（log中记录了每个block的字节空间，找没满的那个）
  • 按照日志的内容依次扫描，checkpoint_lsn之后的redo日志，进行页面恢复

Undo日志（Undo log）

  • 事务保证原子性靠的就是日志
    • 错误：服务器、操作系统、断电
    • 手动或自动rollback
  • 对每一条记录进行改动的时候，需要留一手
    • INSERT，记录主键，rollback就删除主键
    • DELECT，记录内容，rollback恢复记录
    • UPDATE，记录内容，rollback恢复记录

每一个事务对数据的修改都会被记录到 undo log ，当执行事务过程中出现错误或者需要执行回滚操作的话，MySQL 可以利用 undo log 将数据恢复到事务开始之前的状态。

undo log 属于逻辑日志，记录的是 SQL 语句，比如说事务执行一条 DELETE 语句，那 undo log 就会记录一条相对应的 INSERT 语句。同时，==undo log 的信息也会被记录到 redo log 中，因为 undo log 也要实现持久性保护。==并且，==undo-log 本身是会被删除清理的，==例如 INSERT 操作，在事务提交之后就可以清除掉了；UPDATE/DELETE 操作在事务提交不会立即删除，会加入 history list，由后台线程 purge 进行清理。

undo log 是采用 segment（段）的方式来记录的，每个 undo 操作在记录的时候占用一个 undo log segment（undo 日志段），undo log segment 包含在 rollback segment（回滚段）中。事务开始时，需要为其分配一个 rollback segment。每个 rollback segment 有 1024 个 undo log segment，这有助于管理多个并发事务的回滚需求。

通常情况下， rollback segment header（通常在回滚段的第一个页）负责管理 rollback segment。rollback segment header 是 rollback segment 的一部分，通常在回滚段的第一个页。history list 是 rollback segment header 的一部分，它的主要作用是记录所有已经提交但还没有被清理（purge）的事务的 undo log。这个列表使得 purge 线程能够找到并清理那些不再需要的 undo log 记录。

Redo log & Undo log

  • 前像（before-image）和后像（after-image）的相互转换

  • Undo：一个事务在执行过程中，还未提交，发生崩溃或者需要回滚

    保障原⼦性、实现MVCC（多版本并发控制）

    • Undo log 撤销回滚的日志，记录更新前的数据到undo日志文件中
    • Undo日志记录的是操作记录，插入记录主键、删除记录内容、更新记录旧值
    • Undo日志只在乎“操作之前”（roll_pointer指针串成链表/版本表，trx_id事务id）

  • Redo：掉电，磁盘I/O崩了，之前提交的记录如何保存（crash-safe 奔溃恢复）

    保障持久性

    • 事务提交时，未必检查点同步，事务提交成功的标记是——redo日志持久化了
    • Redo日志记录的是物理修改，（xxx数据页yyy的偏移量做了zzz的修改/影子页）
    • 循环写，不用于备份恢复、主从复制，用于掉电等故障恢复——binlog用于全局备份

  • 被修改的Undo log本身，也会记录Redo log

分区、分表、分库

  • 分区、分表、分库

    原因、解决的问题、会遇到的问题

分区

就是把一张表的数据分成N个区块，在逻辑上看最终只是一张表，但底层是由N个物理区块组成的

  1. 分区（partition）也是一种数据分组的方式

    1. 提高并发性（concurrency）和并行性（parallelism）：很多大型的表分成了很多的小型的表
    2. 从而增强系统架构的可伸缩性（scalable）

  2. 面对两大问题

    • 管理问题（备份和恢复）
    • 数据量巨大的表，B+树索引失效，非聚簇索引的大量随机I/O问题

  3. 分区能解决并发问题吗？不能

  4. 又回到了IOT类似的问题：“冲突”

    • A. 通过分区键将数据聚集，利于高速检索；

    • B. 对并发执行的更改操作，分散的数据可以避免访问过于集中的问题

    So，A or B……完全取决于您的需求

  5. 可以使用多层分区，用不同标准在不同层处理

  6. 分区是把双刃剑

    • NULL值会使分区过滤无效（PATITION by RANGE COLUMN（order_date））
    • 分区列和索引列不匹配（没有索引，或关联查询时关联条件不匹配索引）
    • 选择分区的成本可能很高（范围分区的成本需要注意）
    • 打开并锁住所有底层表的成本可能很高（开销和分区类型无关，主键查找单行会带来明显开销）
    • 维护分区的成本可能很高

循环分区

不受数据影响的内部机制

  • 分区定义为各个磁盘的存储区域
  • 可以看作是随意散布数据的机制
  • 保持更改带来的磁盘I/O操作的平衡

数据驱动分区

根据一个或多个字段中的值来定义分区

  • 一般叫分区视图（partitioned view），而MYSQL老版本称为（merge table）

分区的实现方式

  • 哈希分区（Hash-partitioning）
  • 范围分区（Range-partitioning）/键值分区
  • 列表分区（List-partitioning）

分区表的底层实现原理

  • 分区表是由多个相关的底层表实现的
    • 底层表也是由句柄对象（Handler object）表示，可以直接访问各个分区
    • 存储引擎的角度来看，底层表和一个普通的表没有任何去表，它并不管是普通表还是分区表的一部分
    • 分区表的索引是在底层表上各自加上一个完全相同的索引
  • 分区表上的操作逻辑
    • SELECT，分区层打开并锁住所有底层表，优化器判断过滤部分分区，在调用引擎接口访问
    • INSERT，分区层打开并锁住所有底层表，确定哪个分区接受这条记录，在写入底层表
    • DELETE，分区层打开并锁住所有底层表，确定对应分区，在进行删除操作
    • UPDATE，分区层打开并锁住所有底层表，确定分区，取出数据更新，再决定放入哪个分区，删除原纪录

分库

是为了解决数据库连接资源不足问题，和磁盘IO的性能瓶颈问题。 – javaguide

分库就是将数据库中的数据分散到不同的数据库上，可以垂直分库，也可以水平分库。

分库方法

  1. 垂直分库 就是把单一数据库按照业务进行划分，不同的业务使用不同的数据库，进而将一个数据库的压力分担到多个数据库。

    举个例子：说你将数据库中的用户表、订单表和商品表分别单独拆分为用户数据库、订单数据库和商品数据库。

  2. 水平分库 是把同一个表按一定规则拆分到不同的数据库中，每个库可以位于不同的服务器上，这样就实现了水平扩展，解决了单表的存储和性能瓶颈的问题。

    举个例子：订单表数据量太大，你对订单表进行了水平切分（水平分表），然后将切分后的 2 张订单表分别放在两个不同的数据库。

  3. 读写分离

    对于时效性不高的数据，可以通过读写分离缓解数据库压力

    需要解决的问题：在业务上区分哪些业务上是允许一定时间延迟的，以及数据同步问题

什么时候考虑使用分库

  • 单台DB的存储空间不够
  • 随着查询量的增加单台数据库服务器已经没办法支撑

分库解决的问题

  • 其主要目的是为突破单节点数据库服务器的 I/O 能力限制，解决数据库扩展性问题

分库的问题和解决方案

  • 问题
    • 事务的支持，分库分表，就变成了分布式事务
    • join时跨库，跨表的问题
    • 分库分表，读写分离使用了分布式，分布式为了保证强一致性，必然带来延迟，导致性能降低，系统的复杂度变高
  • 常用的解决方案
    • 对于不同的方式之间没有严格的界限。需要根据实际情况，结合每种方式的特点来进行处理
    • 选用第三方的数据库中间件（Atlas，Mycat，TDDL，DRDS），同时业务系统需要配合数据存储的升级

分表

就是把一张表按一定的规则分解成N个具有独立存储空间的实体表。系统读写时需要根据定义好的规则得到对应的字表明，然后操作它。

是为了解决单表数据量太大，sql语句查询数据时，即使走了索引也非常耗时问题。此外还可以解决消耗cpu资源问题 - 来自javaguide

分表 就是对单表的数据进行拆分，可以是垂直拆分，也可以是水平拆分。

分表的方法

  1. 垂直分表 是对数据表列的拆分，把一张列比较多的表拆分为多张表。

    举个例子：我们可以将用户信息表中的一些列单独抽出来作为一个表。

  2. 水平分表 是对数据表行的拆分，把一张行比较多的表拆分为多张表，可以解决单一表数据量过大的问题。

    举个例子：我们可以将用户信息表拆分成多个用户信息表，这样就可以避免单一表数据量过大对性能造成影响。

    水平拆分只能解决单表数据量大的问题，为了提升性能，我们通常会选择将拆分后的多张表放在不同的数据库中。也就是说，水平分表通常和水平分库同时出现。

分表解决的问题

  • 分表后单表的并发能力提高了，磁盘I/O性能也提高了，写操作效率提高了
  • 数据分布在不同的文件，磁盘I/O性能提高
  • 读写锁影响的数据量变小
  • 插入数据库需要重新建立索引的数据减少
  • 分表的实现方式（复杂）
    • 需要业务系统配合迁移升级，工作量较大

什么时候分表分库

（这部分来自javaguide）遇到下面几种场景可以考虑分库分表：

  • 单表的数据达到千万级别以上，数据库读写速度比较缓慢。
  • 数据库中的数据占用的空间越来越大，备份时间越来越长。
  • 应用的并发量太大（应该优先考虑其他性能优化方法，而非分库分表）。

下图来自6+的ppt

分表分库带来的问题 - 来自javaguide

引入分库分表之后，会给系统带来什么挑战呢？

  • join 操作：同一个数据库中的表分布在了不同的数据库中，导致无法使用 join 操作。这样就导致我们需要手动进行数据的封装，比如你在一个数据库中查询到一个数据之后，再根据这个数据去另外一个数据库中找对应的数据。不过，很多大厂的资深 DBA 都是建议尽量不要使用 join 操作。因为 join 的效率低，并且会对分库分表造成影响。对于需要用到 join 操作的地方，可以采用多次查询业务层进行数据组装的方法。不过，这种方法需要考虑业务上多次查询的事务性的容忍度。
  • 事务问题：同一个数据库中的表分布在了不同的数据库中，如果单个操作涉及到多个数据库，那么数据库自带的事务就无法满足我们的要求了。这个时候，我们就需要引入分布式事务了。
  • 分布式 ID：分库之后， 数据遍布在不同服务器上的数据库，数据库的自增主键已经没办法满足生成的主键唯一了。我们如何为不同的数据节点生成全局唯一主键呢？这个时候，我们就需要为我们的系统引入分布式 ID 了。
  • 跨库聚合查询问题：分库分表会导致常规聚合查询操作，如 group by，order by 等变得异常复杂。这是因为这些操作需要在多个分片上进行数据汇总和排序，而不是在单个数据库上进行。为了实现这些操作，需要编写复杂的业务代码，或者使用中间件来协调分片间的通信和数据传输。这样会增加开发和维护的成本，以及影响查询的性能和可扩展性。

分区和分表的区别与联系

  • 分区和分表的目的都是减少数据库的负担，提高表的增删改查效率。
  • 分区只是一张表中的数据的存储位置发生改变，分表是将一张表分成多张表。
    • 当访问量大，且表数据比较大时，两种方式可以互相配合使用
    • 当访问量不大，但表数据比较多时，可以只进行分区
    • 分表可以多库，分区不能
  • 常见分区分表的规则策略（类似）

SQL解释器

  • SQL解释器

    • 基于成本优化器

      例如基于成本优化器的计算方式

    • 基于规则优化器

优化器只能对关系领域进行优化

优化器的有效范围

  • 优化器需要借助数据库中找到的信息

  • 能够进行数学意义上的等价变换

  • 优化器考虑整体响应时间

  • 优化器改善的是独立的查询

基于成本的优化器 CBO

什么是成本：

  • 参考网上的资料，数据库里的成本实际上就是对于执行目标SQL所需要IO,CPU等资源的一个估计值。而成本值是根据索引，表，行的统计信息计算出来的(计算过程比较复杂)

  • ppt上的解释

    成本一般有两个方面组成

    • I/O 成本，MyISAM 、 InnoDB 存储引擎都是将数据和索引存储到磁盘的
    • 从磁盘到内存的加载，涉及到“物理读写”，这种耗损的时间称之为 I/O 成本
    • CPU 成本，读取记录，以及检测记录是否满足搜索条件、对结果集排序，称之为 CPU 成本

基于成本的优化算法

要点是执行计划的成本估算

基础仍然是规则方案探索

基于成本的优化步骤

  1. 根据搜索条件，找出所有可能使用的索引
  2. 计算全表扫描的代价（row，Data_length) (show table status like ‘T’\G)
  3. 计算使用不同索引的代价

两表连接的成本分析

连接查询的总成本 = 单词访问驱动表的成本 + 驱动表扇出值 * 单次被驱动表的成本

不同驱动表的成本是不一样的，寻找成本最低的那个

扇出值的计算是估算，根据条件占比的估算*

多表连接类似，只是可选路径是 N 的阶乘

基于成本优化器的实现

  1. Volcano模型（Apache Calcite）看源码
    • 提供了一套SQL解析和执行的接口，包含SQL查询和执行相关的一系列任务的执行代码
    • 优点，流行，纯后端，很多Apache项目都使用它完成SQL解析和执行
    • 缺点，文档不够充分（怎么这么听，这么像软⼯三的题？）
  2. 需要具备的基本知识
    • 贪心算法，动态规划算法（自底向上，自顶向下）
    • 广度优先搜索，启发式算法

基于规则的优化器 RBO

要点是结构匹配和替换

  • 应用规则的算法一般需要先在关系代数结构上匹配一部分局部结构
  • 再根据结构的特点进行辩护乃至替换操作

基于规则的优化算法

  • 变化规则的选择，哪些规则应该被应用，以什么顺序被使用？
  • 变换效果的评价，经过变换的查询性能的评估，算子效率和数据集
  • 所以，一般固定规则一定会构建人工的优先级顺序 => 通用性下降，适应范围变窄

最后一题

  • 还有一道题没有复习范围，纯粹的送分题？？