• C++ 20
• CMake

cmake .
make
./bin/my_dbms

fs 目录下实现了一个简单的页式文件管理系统。它由三个类（Filesystem、File、BufferManager）和一个结构（BufferPage）构成，呈现出如下架构：

• Filesystem 是整个文件系统的入口类。它负责管理文件系统中用到的所有 File 对象，并维护了一个缓存管理器 BufferManager。一个文件系统中的所有 File 共享一个 BufferManager 的引用。
• File 类封装了文件读写相关的系统函数。由于这是一个页式文件管理系统，File 类对外暴露的只有 get_page 和 close 方法，其它文件操作相关的方法或者不提供，或者由 Filesystem 类统一管理。
• BufferManager 是一个基于 LRU 算法的缓存管理系统，用于对页进行缓存管理。每当一个 File 对象希望获取一个页时，它不会立即进行文件读写，而是会先尝试从 BufferManager 寻找缓存，并根据是否命中的情况考虑是否进行文件读写。此外，当一个 File 对象关闭时，它也会从 BufferManager 中获取所有属于它的脏页，并进行写回。
• BufferPage 结构用于描述一个缓存页。调用 File::get_page 方法将会得到一个 BufferPage 的指针。如果需要对 BufferPage 进行写操作，用户需自行将 dirty 字段改为 true；当这片缓存被交换或文件被关闭时，脏缓存页的内容会被写回。一旦通过 File::get_page 方法获得了一个 BufferPage 引用，调用者应尽快使用，以防该 BufferPage 因为被交换出缓存队列而失效。

文件系统中涉及的所有编号均从 $0$ 开始。

文件系统的使用样例可参见 tests/fs-test.cpp。

MyDBMS 的数据库文件布局基本遵循实验指导书上的约定，即每个数据库对应一个目录，每张表存储在单独的文件中。

rs 目录下实现了一个支持变长记录的记录管理系统。它由两个类（RecordSystem、RecordFile）和两个结构（RecordFileMeta、RecordPageHeader）构成，呈现出如下架构：

• RecordSystem 是整个记录管理系统的入口类。它包含一个文件系统 Filesystem 对象。所有记录文件都必须通过 RecordSystem 创建，因为通过这种方式创建的文件会包含一些记录文件的元信息。
• RecordFile 类包含了一个 File 对象。它在 File 类的基础上进一步封装，提供了一些读写记录相关的方法。在更上层的模块中，一个 RecordFile 对象将会对应一张表。
• RecordFileMeta 结构用于描述记录文件的元信息，各字段的含义见代码注释。
• RecordPageHeader 结构用于描述记录文件中数据页的页头，各字段的含义见代码注释。

除非特殊说明，记录管理系统中涉及的所有编号均从 $0$ 开始。

记录管理系统的使用样例可参见 tests/rs-test.cpp。

定义 $K=4096$。

• $Page(0)$ 为元信息页。该页的数据格式与 RecordFileMeta 结构一致。
• $Page(n(K+1)+1)$ 为空闲空间信息页。该页存储了一个包含 $K$ 个页节点和 $K-1$ 个非页节点的满二叉树，每个节点占用 $1$ 字节的空间。二叉树的根节点编号为 $1$。二叉树第 $k$ 个节点的两个页节点编号分别为 $2k$ 和 $2k+1$。出于实现方便考虑，该页的首个字节不予使用，从下一个字节开始存放二叉树。约定空页的空闲空间情况用 0xFF 表示。
• 其余页为数据页。每个数据页的前 $64$ 个字节保留给页头数据使用，页头的数据格式与 RecordPageHeader 结构一致。随后是每个数据页的数据部分，从前向后存储记录，从后向前存储槽目录。记录储存格式与实验指导书上所述一致。槽目录数据按照自然数编号从后往前存储，每 $2$ 字节依次表示对应记录的字节偏移量。无效槽的字节偏移量约定为 $0$。

定义 $K=4096$，即本系统一页字节数的一半。

本系统采用大根堆二叉树的数据结构来维护空闲空间信息。出于实现方便考虑，本系统将空闲空间信息页与数据页放在同一个记录文件中进行管理。

每一个空闲空间信息页可以维护一棵包含 $K$ 个页节点的满二叉树，其中每个节点占用 $1$ 字节的空间。每个节点代表一个数据页的空闲空间情况（这里需要将空闲空间大小分成 $256$ 个级别，这样每个节点即可仅占用 $1$ 字节的空间），因此每一个空闲空间信息页可以维护 $K$ 个数据页的空闲信息。

只进行到这里，本系统能够支持的最大的记录表也就只有 $K$ 个数据页了。为了能够提供更大的可拓展性，本系统采用两级空闲空间信息页来维护空闲空间信息。具体而言，本系统允许一个记录表中存在多个空闲空间信息页，每个空闲空间信息页根节点的数值则连续存放在文件的元信息页中。这也解释了 RecordFileMeta 结构中的 fsp_cnt 和 fsp_data 的含义。本系统约定，单个记录文件中至多有 $63$ 个空闲空间信息页。至此，本系统能够支持的单张表数据容量的理论上限为 $63\times4096\times8K\approx2G$，这已超过最终测试的总数据量。

MyDBMS 的索引同样是以一个文件的形式保存，约定表名为 tableName 的列 columnName 的索引文件命名为 tableName_columnName ，一张表可以拥有多个索引文件。

目前 MyDBMS 只能对范围在[0, 100000000) 的整型单列做索引。

is 目录下实现了一个基于 B+ 树的索引管理系统。它由两个类（IndexSystem、IndexFile）和两个结构（IndexFileMeta、IndexPageHeader）构成，呈现出如下架构：

• IndexSystem 是整个索引管理系统的入口类。它包含一个文件系统 Filesystem 对象。所有索引文件都必须通过 IndexSystem 创建，因为通过这种方式创建的文件会包含一些索引文件的元信息。
• IndexFile 类包含了一个 File 对象。它在 File 类的基础上进一步封装，提供了一些读写索引相关的方法。在更上层的模块中，一个 IndexFile 对象将会对应一张表的一个索引。
• IndexFileMeta 结构用于描述索引文件的元信息，各字段的含义见代码注释。
• IndexPageHeader 结构用于描述索引文件中数据页的页头，各字段的含义见代码注释。

B+ 树的参数 m 保存在元信息页里，如果实例化时没有设置，默认设置为 255 ，且 255 是 m 可以设置的最大值。

索引管理系统的使用样例可参见 tests/is-test.cpp。

为了尽快完成 demo 数据库，目前还没有进行特别大强度的测试（插删交替），因此除了插入和查询以外的接口暂时不一定可靠。

第 0 页为元信息页。该页的数据格式与 IndexFileMeta 结构一致。

（没详细写，赶时间）

其余页每页代表一个 B+ 树结点，每个数据页的前 64 个字节保留给页头数据使用，页头的数据格式与 IndexPageHeader 结构一致。随后是数据部分，数据部分将从前往后放置键值对，一个关键码占用 8 字节。从后往前放置链表信息，一个关键码占用 2 字节。

为了方便处理，每个数据页初始时就含有一个编号为 0 的关键码，其键值为 100000000 ，即正无穷。对于非叶节点，该编号关键码可以用来存储整个节点最右边的子树。

实现在目录 qs 下，见飞书文档

实现在目录 ms 下，见飞书文档

实现在目录 src 下，同时也是 MyDBMS 的入口，该目录下含有 main.cpp 。

可以接收用户输入 sql 语句，完成对应操作，并给出一些反应。

伪指令 EXIT; 可以退出程序。

可以用 tests/test_sql 作为输入进行测试。

$ ./bin/my_dbms < tests/test_sql

实现在目录 script 下。

首先，请先将数据库创建，并导入表创建：

$ ./bin/my_dbms < tests/my_create.sql