- 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
因为被交换出缓存队列而失效。
文件系统中涉及的所有编号均从
文件系统的使用样例可参见 tests/fs-test.cpp
。
MyDBMS
的数据库文件布局基本遵循实验指导书上的约定,即每个数据库对应一个目录,每张表存储在单独的文件中。
rs
目录下实现了一个支持变长记录的记录管理系统。它由两个类(RecordSystem
、RecordFile
)和两个结构(RecordFileMeta
、RecordPageHeader
)构成,呈现出如下架构:
RecordSystem
是整个记录管理系统的入口类。它包含一个文件系统Filesystem
对象。所有记录文件都必须通过RecordSystem
创建,因为通过这种方式创建的文件会包含一些记录文件的元信息。RecordFile
类包含了一个File
对象。它在File
类的基础上进一步封装,提供了一些读写记录相关的方法。在更上层的模块中,一个RecordFile
对象将会对应一张表。RecordFileMeta
结构用于描述记录文件的元信息,各字段的含义见代码注释。RecordPageHeader
结构用于描述记录文件中数据页的页头,各字段的含义见代码注释。
除非特殊说明,记录管理系统中涉及的所有编号均从
记录管理系统的使用样例可参见 tests/rs-test.cpp
。
定义
-
$Page(0)$ 为元信息页。该页的数据格式与RecordFileMeta
结构一致。 -
$Page(n(K+1)+1)$ 为空闲空间信息页。该页存储了一个包含$K$ 个页节点和$K-1$ 个非页节点的满二叉树,每个节点占用$1$ 字节的空间。二叉树的根节点编号为$1$ 。二叉树第$k$ 个节点的两个页节点编号分别为$2k$ 和$2k+1$ 。出于实现方便考虑,该页的首个字节不予使用,从下一个字节开始存放二叉树。约定空页的空闲空间情况用0xFF
表示。 - 其余页为数据页。每个数据页的前
$64$ 个字节保留给页头数据使用,页头的数据格式与RecordPageHeader
结构一致。随后是每个数据页的数据部分,从前向后存储记录,从后向前存储槽目录。记录储存格式与实验指导书上所述一致。槽目录数据按照自然数编号从后往前存储,每$2$ 字节依次表示对应记录的字节偏移量。无效槽的字节偏移量约定为$0$ 。
定义
本系统采用大根堆二叉树的数据结构来维护空闲空间信息。出于实现方便考虑,本系统将空闲空间信息页与数据页放在同一个记录文件中进行管理。
每一个空闲空间信息页可以维护一棵包含
只进行到这里,本系统能够支持的最大的记录表也就只有 RecordFileMeta
结构中的 fsp_cnt
和 fsp_data
的含义。本系统约定,单个记录文件中至多有
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