[大数据] 【从0到1开发一个初级DBMS】(task1)DBMS简述

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 大数据 -> 【从0到1开发一个初级DBMS】(task1)DBMS简述 -> 正文阅读

[大数据]【从0到1开发一个初级DBMS】(task1)DBMS简述

学习总结

关于数据库的面试题总结可以参考之前的笔记：数据库基础知识（面试），但是呢这次这门课不仅需要掌握数据库的使用，还需要进一步学习底层原理和实现过程（如一条SQL语句是如何被正确地解析执行的），其实在找工作的面试中也是可能会被问到的，感觉也是需要和操作系统等底层的东西（如页面置换）结合起来学习的，可以结合菜鸡的操作系统408笔记复习。
本次学习是OceanBase数据库比赛的赛前培训，基础课程是华科老师结合CMU 15-445（英语好的童鞋也可以直接看英文课程）开设的数据库课程，欢迎大家一起参加呀（PS：不嫌我菜的一起组队也行呀，比赛介绍在本文最底下）。

资源介绍：
（1）oceanbase开源官网：https://open.oceanbase.com/
（2）github代码：https://github.com/alibaba/oceanbase

一、学习体系

（1）DBMS简介

作为数据库系统的核心和基础，数据库管理系统（Data Base Management System，DBMS）应用广泛。DBMS帮助用户实现对共享数据的高效组织、存储、管理和存取，经过数十年的研究发展，已经成为继操作系统之后最复杂的系统软件。

（2）DBMS的2个学习阶段：

第一个阶段是学习DBMS的功能使用，包括如何运用数据库语言创建、访问和管理数据库，如何利用DBMS设计开发数据库应用程序。
第二个阶段是学习DBMS的内部结构和实现机制。通过学习DBMS的实现技术，学习者对数据库系统的工作原理会有更深入的理解，利于分析数据库系统在复杂应用环境中可能出现的各种性能问题，设计开发出更高效的数据库应用程序。

在本次学习中，我们从DBMS开发者的视角，讨论实现一个关系型DBMS需要考虑的一些关键问题，比如：数据库在存储介质上是如何组织和存储的？一条SQL语句是如何被正确地解析执行的？有哪些结构和方法可以用来快速定位数据库中的记录，提高存取效率？多用户共享数据库时，如何在避免并发错误的同时提高并发度？发生故障时，如何保证数据库能够恢复到正确的状态？

在此基础上，我们可以尝试自己从零开始开发一个简单的DBMS，并逐渐完善、增强它的功能
在这个过程中掌握各种计算机专业知识在DBMS这样的复杂系统软件设计中的应用，提高自己的系统综合能力。

课前所需要的基础：
关系代数、关系数据库语言SQL、数据结构、算法，以及操作系统及编译的相关知识。

二、数据库管理系统的组成

在这里插入图片描述

图1-1 DBMS内部结构图

DBMS允许用户创建数据库并对数据库中的数据进行查询和修改，同时提供故障时的数据恢复功能和多用户同时访问时的并发控制功能。

图1-1的DBMS的内部结构图中单线框表示系统模块，双线框表示内存中的数据结构，实线表示控制流+数据流，虚线表示数据流。
该图反映了DBMS的几大主要功能的处理流程，即数据定义、数据操纵和事务管理，这些功能均依赖底层的存储管理及缓冲区管理组件提供对磁盘中数据的访问支持。下面对这些功能简要说明：

（1）存储及缓冲区管理

（1）存储管理器：控制数据在磁盘上的放置和数据在磁盘与内存之间的交换。

很多DBMS依赖底层操作系统的文件系统来管理磁盘中的数据，也有一些DBMS为了提高效率，直接控制数据在磁盘设备中的存储和访问。
虚实地址转换：存储管理器登记了数据在磁盘上所处的位置，将上层模块提出的逻辑层面的页面访问请求映射为物理层面的磁盘访问命令。

（2）缓冲区管理器：将内存空间划分为与页面同等大小的帧，来缓存从磁盘读入的页面，并保证这些页面在内存和磁盘上的副本的一致性。DBMS中所有需要从磁盘获取信息的上层模块都需要与缓冲区管理器交互，通过缓冲区读写数据。这些信息包括以下类型：

数据：数据库自身的内容。
元数据：描述数据库的结构及其约束的数据库模式。
日志记录：记录事务对数据库所做修改的信息，用于保证数据库的一致性和持久性。
统计信息：DBMS收集和存储的关于表、索引等数据库对象的大小、取值分布等信息，用于查询优化。
索引：支持对数据进行高效存取的数据结构。

（2）DDL命令的处理

DDL是指数据定义语言，这类命令一般由DBA等有特殊权限的用户执行，用于定义或修改数据库的模式，比如创建或者删除表、索引等。

元数据：关于数据库模式的描述信息。元数据与普通数据一样，也是以表（称为系统表）的形式存在的。DDL命令由DDL处理器解析其语义，然后调用记录管理器及索引管理器对相应的元数据进行修改。

（3）DML命令的处理

DML，即数据操纵语言：一般由普通用户或应用程序执行。DML又可分为对数据库的修改操作（增、删、改）和对数据库的查询操作。

对DML命令的处理中最重要的部分是查询处理。查询处理的过程分为以下几步：

查询分析及检查：先对查询语句的文本进行语法分析，将其转换为语法树，然后进行查询检查（例如，检查查询中所提到的关系是否确实存在），并将语法树中的某些结构转换成内部形式，形成查询树。查询树表示了一个关系代数表达式，即要在关系上执行的一系列操作。
查询优化：查询优化器利用元数据和关于数据的统计信息来确定哪个操作序列可能是最快的，将最初的查询树等价转换为最高效的操作序列。
查询执行：执行引擎负责查询计划的执行，它通过完成查询计划中的各个操作，得到最终的执行结果。在执行过程中，它需要与DBMS中很多其他组件进行交互。例如，调用记录管理器和索引管理器获取需要的数据，调用并发控制组件对缓冲区中的某条记录加锁以避免并发错误，或者调用日志组件登记对数据库所做的修改。

（4）事务处理

事务是一组数据库操作，这组操作要么都做，要么都不做，不可分割。一个事务中包含哪些操作是由用户定义的，可以包含多个数据库操作，也可以只包含单个数据库操作。对事务的处理由事务管理器负责，它包括并发控制组件和日志及恢复组件，目的是保证事务的ACID特性，即原子性（Atomicity）、一致性（Consistency）、隔离性（Isolation）和持久性（Durability）。

事务管理器接收来自用户或应用程序的事务命令，从而得知什么时候事务开始、什么时候事务结束、以及事务的参数设置（例如事务的隔离级），然后在事务运行过程中执行下列任务：

登记日志：为了保证一致性和持久性，事务对于数据库的每一个修改都在磁盘上记录日志，以保证不管在什么时候发生故障，日志及恢复组件都能根据日志将数据库恢复到某个一致的状态。日志一开始被写到缓冲区中，然后会在适当的时机从日志缓冲区写回到磁盘中。
并发控制：事务的执行从表面上看必须是孤立的，但是在大多数系统中，实际上有许多事务在同时执行。因此，并发控制组件必须保证多个事务的各个动作以一种适当的顺序执行，从而使得最终的结果与这些事务串行执行的结果相同。常见的并发控制方式是封锁机制，通过加锁来防止两个事务以可能造成不良后果的方式存取同一数据。

三、关系模型和SQL

本次学习讨论的关系型DBMS是以关系模型为理论基础的。另一方面，SQL作为一种关系数据库标准语言，得到了几乎所有商用关系DBMS的广泛支持。要实现一个关系DBMS，需要考虑如何在系统中支持符合关系模型定义的数据结构、数据操作和数据约束，同时支持用户通过SQL命令来访问系统。

下面为关系模型和SQL中的一些重要概念和二者的关系。

1. 关系模型

1970年，E.F.Codd在他的论文《A Relation Model of Data for Large Shared Data Banks》中首次提出关系模型。关系模型相对于层次模型和网状模型的优势在于：它提供了一种只使用自然结构来描述数据的方法，而不需要为了方便机器表示而附加任何额外的结构。这样就为更高级的数据语言提供了基础，这种语言使得程序能够独立于数据的机器表示及组织方式，具有更好的数据独立性。

（1）关系

关系模型采用的数据结构称为关系。在关系模型中，数据库中的全部数据及数据间的联系都用关系来表示。关系是一个无序的元组集合，每个元组由一组属性值构成，表示一个实体。一个有n个属性的关系称为n元关系。由于关系中的元组是无序的，因此DBMS可以采用任何它希望的方式存储它们，以便进行优化。

（2）主键和外键

主键和外键反映了关系模型的实体完整性约束和参照完整性约束。

主键可唯一地标识关系中的一个元组，以确保没有任何两个元组是完全一样的。如果用户没有定义主键，有些DBMS会自动创建内部主键。
外键指定一个关系中的属性在取值时必须与另一个关系中的某个元组相对应，不能随意取值。

（3）关系代数

关系代数是关系模型定义的一组运算符，用于检索和操作关系中的元组。每个运算符接受一个或多个关系作为输入，并输出一个新的关系。
关系代数表达式：为了表示查询，可以将这些运算符连接在一起以创建更复杂的运算。

常见的关系代数运算符包括：

选择（selection）：选择运算是从关系R中选取满足给定条件的元组构成结果关系，记作σF?。
投影（Projection） ：投影运算是从关系R中选取若干属性列A构成结果关系，记作 ΠA?。
并（ Union ） ：两个关系R和S的并是由属于R或属于S的元组构成的集合，记为 R∪S。
交（ Intersection） ：两个关系R和S的交是由既属于R又属于S的元组构成的集合，记为 R ∩ S。
差（Difference ） ：两个关系R和S的差是由属于R但不属于S的元组构成的集合，记为 R－S。
笛卡尔积（ Cartesian Product） ：两个关系R和S的笛卡尔积是由这两个关系中元组拼接而成的所有可能的元组的集合，记为R×S。
自然连接（Natural Join） ：两个关系R和S的自然连接是由这两个关系中在共同属性上取值相等的元组拼接而成的所有可能的元组的集合，记为R?S。

关系代数可以被视为一种过程化语言，因为一个关系代数表达式指定了查询的具体计算步骤。例如，在这里插入图片描述
指定的计算步骤是先计算关系S和SC的自然连接，然后选择，而
指定的计算步骤则是先选择后连接。这两个表达式其实是等价的，它们的计算结果相同，但是计算速度却不同，后者明显更快。如果像这样由用户来指定查询的计算步骤，性能优化的压力就会落在用户身上，因为他们必须考虑如何写出更高效的查询表达式。所以更好的方法是DBMS提供一种非过程化语言，用户只指定需要什么数据，而不指定如何找到它。这正是SQL的成功之处。

2. SQL语言

SQL 是关系数据库的标准语言，它是1974 年由Boyce和Chamberlin提出的，最初叫 Seque（Structured English Query Language）, 并在IBM公司研发的关系数据库管理系统原型System R上实现，后改名为SQL（Structured Query Language）。

SQL是一种通用的、功能极强的关系数据库语言，其功能不仅仅是查询，而是包括数据库模式创建、数据库数据的插入与修改、数据库安全性完整性定义与控制等一系列功能。
数据查询仍然是SQL中最重要、也最具特色的功能。

关系模型中的关系在SQL中被映射为表或视图：
（1）表是指数据实际存储在数据库中的关系；
（2）视图是指不实际存储数据，但是需要时可以由实际存储的关系构造出来的关系。

注意：关系模型中的关系和SQL中的表和视图在概念上存在一些差异：
前者是基于集合（set）的，即关系中的元组是不允许重复的；
后者是基于包（bag）的，允许表、视图或结果集中出现重复的元组。

（1）SELECT的基本语法

SQL的查询通过SELECT语句来表达，它的基本语法如下：

   SELECT <列名或表达式序列>
   FROM <表名或视图名序列>
   [WHERE <行条件表达式>]
   [GROUP BY <列名序列>
   [HAVING <组条件表达式>] ]  
   [ORDER BY <排序列名>[ASC|DESC] [,...]]

以上语法成分中，只有SELECT和FROM子句是必不可少的。
SQL还提供了一个强大的特性，允许在WHERE、FROM或HAVING子句中嵌入子查询。子查询也是一个SELECT语句，在上述的WHERE、FROM或HAVING子句中可以使用子查询的返回结果来进行计算，这也是SQL之所以称为"结构化"查询语言的原因。

（2）一条典型的查询语句，其结果可以这样计算：

读取FROM子句中基本表及视图的数据，并执行笛卡尔积操作；
选取其中满足WHERE子句中条件表达式的元组；
按GROUP BY子句中指定列的值分组；
提取满足HAVING子句中组条件表达式的那些分组；
按SELECT子句投影出结果关系；
按ORDER BY子句对结果关系进行排序。

（3）三种等价的关系代数表达式

以上计算过程可以被看作是对一系列关系代数运算的执行。实际上一个SELECT语句在DBMS中就是被解析为一个关系代数表达式，再由执行引擎来对其进行计算的。
但是对于同一条SELECT语句，可能存在多个等价的关系代数表达式。例如，对于以下语句：

SELECT 姓名
FROM 学生, 选课
WHERE 学生.学号=选课.学号 AND 课号=2 ;

存在多个等价的关系代数表达式：

? Π_姓名(σ_{学生.学号=选课.学号 ∧ 课号=2}(学生×选课))
? Π_姓名(σ_课号=2 (学生?选课))
? Π_姓名(学生?σ_课号=2 (选课)

这三个表达式的计算代价差异巨大，而DBMS的一个重要任务就是通过查询优化处理找到其中代价最小的那一个。SQL采用的这种非过程化语言形式，既简化了用户的表达，又为DBMS优化查询语句的执行性能提供了巨大的灵活性。

备忘录：Oceanbase比赛时间节点

（1）到10.15截止报名
（2）10.16-11.21初赛：
必选题目全部完成，选座题按照实现的功能计分，总分高者优先晋级（50支队伍）
（3）11.22-12.12复赛：
性能测试，时间短者优先（20支队伍）
（4）12.18-12.19决赛：
性能测试，时间短者优先（10支队伍）

附录：初赛赛题

1. 背景

本次大赛赛题, 是在一个miniob(mini数据库)库的基础上, 让参数选手实现数据库的非常基础的功能, 功能分为入门（预选赛）, 中级（决赛）, 高阶（黑客松） 3个阶段。入门门槛较低, 适合所有参赛选手。面向的对象主要是在校学生，数据库爱好者, 或者对基础技术有一定兴趣的爱好者, 并且考题对诸多模块做了简化，比如不考虑并发操作, 事务比较简单。
目标是让不熟悉数据库设计和实现的同学能够快速的了解与深入学习数据库内核，期望通过miniob相关训练之后，能够对各个数据库内核模块的功能与它们之间的关联有所了解，并能够在使用时，设计出高效的SQL, 并帮助降低学习OceanBase 内核的学习门槛。

比赛分为三个阶段：预选赛、决赛和黑客松48小时极限挑战赛。
10.16-11.21初赛（即预选赛）：必选题目全部完成，选座题按照实现的功能计分，总分高者优先晋级（50支队伍）。

2. 必做题

名称	描述	测试用例示例
优化buffer pool	必做。实现LRU淘汰算法或其它淘汰算法
drop table	必做。删除表。清除表相关的资源。	create table t(id int, age int); create table t(id int, name char); drop table t; create table t(id int, name char);
实现update功能	必做。update单个字段即可。	update t set age =100 where id=2; update set age=20 where id>100;
增加date字段	必做。date测试不会超过2038年2月。注意处理非法的date输入。	create table t(id int, birthday date); insert into t values(1, ‘2020-09-10’); insert into t values(2, ‘2021-1-2’); select * from t;
查询元数据校验	必做。查询语句中存在不存在的列名、表名等，需要返回失败。需要检查代码，判断是否需要返回错误的地方都返回错误了。	create table t(id int, age int); select * from t where name=‘a’; select address from t where id=1; select * from t_1000;
多表查询	必做。支持多张表的笛卡尔积关联查询。需要实现select * from t1,t2; select t1.,t2. from t1,t2;以及select t1.id,t2.id from t1,t2;查询可能会带条件。查询结果展示格式参考单表查询。每一列必须带有表信息，比如: t1.id \| t2.id 1 \| 1	select * from t1,t2; select * from t1,t2 where t1.id=t2.id and t1.age > 10; select * from t1,t2,t3;
聚合运算	需要实现max/min/count/avg. 包含聚合字段时，只会出现聚合字段。聚合函数中的参数不会是表达式，比如age +1	select max(age) from t1; select count(*) from t1; select count(1) from t1; select count(id) from t1;

3. 选做题

名称	分值	描述	测试用例示例
多表join操作	20	INNER JOIN。需要支持join多张表。需要考虑大表问题，不要直接使用笛卡尔积再过滤	select * from t1 inner join t2 on t1.id=t2.id; select * from t1 inner join t2 on t1.id=t2.id inner join t3 on t1.id=t3.id; selec * from t1 inner join t2 on t1.id=t2.id and t2.age>10 where t1.name >=‘a’;
一次插入多条数据	10	一次插入的数据要同时成功或失败。	insert into t1 values(1,1),(2,2),(3,3);
唯一索引	10	唯一索引：create unique index	create unique index i_id on t1(id); insert into t1 values(1,1); insert into t1 values(1,2); – failed
支持NULL类型	10	包括但不限于建表、查询和插入。默认情况不允许为NULL，使用nullable关键字表示字段允许为NULL。 Null不区分大小写	create table t1 (id int not null, age int not null, address nullable); create table t1 (id int, age int, address char nullable); insert into t1 values(1,1, null);
简单子查询	10	支持简单的IN(NOT IN)语句；支持与子查询结果做比较运算；支持子查询中带聚合函数。子查询中不会与主查询做关联。	select * from t1 where name in(select name from t2); select * from t1 where t1.age >(select max(t2.age) from t2); select * from t1 where t1.age > (select avg(t2.age) from t2) and t1.age > 20.0; NOTE: 表达式中可能存在不同类型值比较
多列索引	20	单个索引关联了多个字段	create index i_id on t1(id, age);
超长字段	20	超长字段的长度可能超出一页，比如常见的text,blob等。这里仅要求实现text（text 长度固定4096字节），可以当做字符串实现。注意：当前的查询，只能支持一次返回少量数据，需要扩展	create table t(id int, age int, info text); insert into t(1,1, ‘a very very long string’); select * from t where id=1;
查询条件支持表达式	20	查询条件中支持运算表达式，这里的运算表达式包括 ±*/。仅支持基本数据的运算即可，不对date字段做考察。运算出现异常，按照NULL规则处理。只需要考虑select。	select * from t1,t2 where t1.age +10 > t2.age 2 + 3-(t1.age +10)/3; select t1.col1+t2.col2 from t1,t2 where t1.age +10 > t2.age 2 + 3-(t1.age +10)/3;
复杂子查询	20	子查询在WHERE条件中，子查询语句支持多张表与AND条件表达式，查询条件支持max/min等	select * from t1 where age in (select id from t2 where t2.name in (select name from t3))
排序	10	支持oder by功能。不指定排序顺序默认为升序(asc)。不需要支持oder by字段为数字的情况，比如select * from t order by 1;	select * from t,t1 where t.id=t1.id order by t.id asc,t1.score desc;
分组	20	支持group by功能。group by中的聚合函数也不要求支持表达式	select t.id, t.name, avg(t.score),avg(t2.age) from t,t2 where t.id=t2.id group by t.id;

Reference

（0）华科的谢美意老师《数据库管理系统实现基础讲义》
（1）github版：https://github.com/OceanBase-Partner/lectures-on-dbms-implementation
（2）网页版：https://oceanbase-partner.github.io/lectures-on-dbms-implementation/
（3）b站直播：https://www.bilibili.com/video/BV15P4y1Y75K?spm_id_from=333.999.0.0