0.实验目标

在本实验中，我们将要实现基于日志的中止回滚和崩溃恢复。源码中提供了定义日志格式的代码，并在事务期间的适当时间将记录附加到日志文件中。我们将使用日志文件的内容完成回滚和恢复。

源码中提供的日志代码产生了用于物理上整页undo和redo的记录。当页是首次读入时，代码记住了整页的原始内容做为前置镜像。当事务更新页时，相应的日志记录包含已存储的前置镜像以及修改后的页面做为后置镜像。我们将使用前置镜像在中止期间进行回滚，在recovery期间undo丢失的事务，后置镜像用于在recovery期间redo成功的事务。

0.实验目标

在这个实验中，你将实现一个B+树形索引，用于高效的查找和范围扫描。我们为你提供了实现树形结构所需的所有底层代码。你将实现搜索、拆分页面、在页面之间重新分配 tuple 以及合并页面。

B+树的内部节点拥有多条记录，每个节点的内容包括节点当前值、以及左右子树的指针；相邻键之间共享一个孩子指针，所以拥有m个键的内部节点通常拥有m+1个孩子指针。叶子节点可以包括数据记录或者指向其他数据库文件的指针。为了简单起见，我们实现的B+树的叶子节点只包括数据记录。相邻的叶子页通过左右同级指针链接在一起，因此范围扫描只需要通过根节点和内部节点进行一次初始搜索即可找到第一个叶子页，后续叶子页通过右(或者左)指针找到。

0.实验目标

在这个实验中，你将在SimpleDB中实现一个简单的基于锁的事务系统。你将需要在代码中的适当位置添加锁和解锁调用，以及跟踪每个事务所持有的锁的代码，并在需要时授予事务锁。

本文档的其余部分描述了添加事务支持所涉及的内容，并提供了一个关于如何将这种支持添加到你的数据库的基本概要。

0.实验介绍

在这个实验中，你将在SimpleDB之上实现一个查询优化器。主要任务包括实现一个选择性估计框架和一个基于成本的优化器。你可以自由选择具体的实现方式，但我们建议使用类似于课堂上讨论的Selinger基于成本的优化器（第9讲）。

• 实现TableStats类中的方法，使其能够使用直方图（IntHistogram类提供的骨架）或你设计的其他形式的统计数据来估计过滤器的选择性和扫描的成本。
• 实现JoinOptimizer类中的方法，使其能够估计 join 的成本和选择性。
• 编写JoinOptimizer中的orderJoins方法。这个方法必须为一系列的连接产生一个最佳的顺序（可能使用Selinger算法），给定前两个步骤中计算的统计数据。

0.实验目标

实验二需要为SimpleDB编写一组操作符，用于实现表的修改（例如，插入和删除记录），选择操作，连接操作和聚合操作。这些操作将在Lab 1中所编写的基础上构建。此外，需要设计页面淘汰策略，完善缓冲池。仍不需要实现事务和锁。

可以使用提供的SQL解析器对数据库运行SQL查询。

• 实现Filter和Join操作符。这些操作符的Javadoc注释中包含了其工作细节。Project和OrderBy已实现，这可能有助于您理解其他操作符的工作方式。

0.实验目标

完成本实验后，要能通过ScanTest系统测试

• 实现管理Tuple的类，即Tuple、TupleDesc。SimpleDB 中已经实现了Field、IntField、 StringField和Type，只需要支持整数和（固定长度的）字符串字段以及固定长度的 tuples。
• 实现 Catalog 。
• 实现BufferPool构造函数和getPage()方法。
• 实现访问方法、HeapPage和HeapFile以及相关的ID类。
• 实现操作符SeqScan。

背景

• 课程：6.830/6.814: Database Systems

• Lab：simple-db-hw-2021

实现说明

• 添加了中文文档

• 将项目改为使用maven构建

• master分支下为实验源代码，dev分支下为自己实现代码

• 具体实现过程可见博客：http://www.hyeee.me/2023/10/15/SimpleDB%E9%A1%B9%E7%9B%AE%E6%80%BB%E8%A7%88/

• github链接：https://github.com/0Heeee/SimpleDB/

一、Java集合概览

​ Java 集合， 也叫作容器，主要是由两大接口派生而来：一个是 Collection接口，主要用于存放单一元素；另一个是 Map 接口，主要用于存放键值对。对于Collection 接口，下面又有三个主要的子接口：List、Set 和 Queue。

​ Java 集合框架如下图所示：