前言

数据库是一个老生常谈的话题，类别众多，如内存数据库(Redis)，文档数据库(MongoDB)，时序数据库(InfluxDB)，图数据库(Neo4j)等，还有目前使用最广泛、最重要的关系数据库(MySQL、PostgreSQL 等)，这也有今天的主角——关系数据库。

对于关系数据库，与它有关的论文、书籍、博文都数不胜数，但是大部分书籍和博文都在教开发者如何去使用一款数据库，鲜有去教开发者如何去弄懂数据库系统架构设计、原理和实现的。

《Database System Concepts》正是这样一本书(中文名：《数据库系统概念》)，而恰好也有这么一门课程 CMU15445，来教我们如何去弄懂数据库原理，掌握数据库系统设计，甚至去实现一个小巧的数据库—— bustub 。

缓存池

减少磁盘和内存之间的数据 IO 次数是数据库提升查询效率的主要途径之一，也是数据设计的主要目标。

为了达到这个目标，数据库需要在内存中保留尽可能多的数据页，最大限度地提高在内存中处理数据查询的机会，减少磁盘访问次数。

但不可能将所有页都保存在内存中，我们需要一个管理内存与磁盘数据的中介组件——缓存池。

磁盘上保存的数据实则是缓存池数据的副本。缓存池中的基本单位是页(对应操作系统 IO 的基本单位也是页)，每一页在磁盘上都有一个副本，磁盘上的副本可能是老数据(脏页)，负责分配缓存池的组件被称为缓存管理器(buffer_manager)。

并发 B+树

主流关系数据库(如 MySQL、PostgreSQL 等)在数据组织和索引组织上几乎都选择了 B+树或其变种。B+树在关系数据库上的重要性不言而喻，这里我们先简单的来介绍一下 B+树 。

B+树定义

B+树是一种多路自平衡树，不同于二叉树，B+树可以拥有多个子节点，并且能够一直保持完美的自平衡。一颗 B+树包括根节点、内部节点、叶子节点三种节点，根节点既可以是内部节点，也可以作为叶子节点。如下图 4 所示：

执行器

前面的两个小节中，分别介绍了缓存池组件以及支持存储引擎的 B+树，本节的主角是执行器。

数据库系统从客户端接收到 SQL 语句后，对语句解析、优化并得到该语句的「查询计划」，而执行器的作用就是按照查询计划来执行查询操作。

这里的查询操作，并不单单指数据查询，它包括如下几类操作：

• 访问、查询，如表遍历，记录查询等；
• 更改，如数据更新、插入、删除等；
• 其它，如 Limit、Offset、聚合函数，Join 等；

注意：bustub 中不会实现 SQL 解析器、优化器，这里也不做介绍。

并发控制

在并发 B+树这一节中，我们实现了支持并发访问的 B+树，B+树可用于存储索引，但是数据库还有更加重要的数据部分——数据表记录(Tuple)。

在 bustub 中，是通过 TransactionManager(事务管理器) 和 LockManager(锁管理器) 来实现 Tuple 并发访问控制和数据库事务的。

事务

事务是数据库访问、更新数据的一个基本执行单元，它可由多个数据库操作组成，且多个操作不可分割，要么全部成功，要么全部失败。

事务具有如下四个特性(摘自维基百科)，习惯上被称之为 ACID特性 。

日志和恢复

计算机容易发生各种故障，如磁盘故障、宕机、软件错误等。一旦计算机故障就容易引起运行其内的数据库丢失数据，因此数据库必须预先采取措施以保证即使发生故障，数据仍然找回。

恢复机制是数据库必不可少的一部分，它能保证数据库即使在故障发生的情况下，仍然恢复到发生前的状态，保证前后数据的一致性，保证数据库的高可用性。

恢复算法是确保数据库一致性、原子性和持久性的关键技术。

恢复算法主要工作包括如下两部分：

• 记录事务处理期间的操作，以确保 DBMS 可以从故障中恢复；

• 将数据库恢复到某个失败后的状态，确保操作的原子性、一致性和持久性。 恢复算法主要思路：

• 预写日志(WAL)：

  • 任何数据更改在应用到数据库之前，必须先由日志写入磁盘。
  • 必须使用 STEAL + NO-FORCE 缓冲池策略。

• 在重做期间恢复历史数据：在重新启动时，重做操作并将数据库恢复到崩溃前的状态。

• 撤消期间记录更改：将撤消操作记录到日志中以确保操作不会在重复失败的情况下重复执行。