下学期的小学期要做一个数据库管理系统 DBMS ,因为觉得很有意思所以打算提前写一写。

一些想法

首先是想试试 Typescript + Electron 的开发模式。 Javascript 几乎是我目前最喜欢的编程语言,语法类似于 C/C++ 写起来很舒服,没有 Python 那么让人不自在的缩进;还是一个真正的跨平台语言,有浏览器的地方就能跑,而且借助 Electron 可以轻松实现跨平台客户端,打起包来也比 Python / C++ 轻松很多;面向对象和函数式都有一定的支持,尤其是 Typescript 为它带来了静态类型检查;语言自带的单线程/事件机制使得它天生就是异步的,用来做用户界面很方便;新技术也使得 JS 的运行效率越来越高。 不过在这里选择用 JS 也有一定的缺点, JS 的生态主要是在前端,用它来做这种偏底层的系统可能会缺少一些包。 最终选择 JS 也是因为这只是一个课程设计,不会有很高的性能与可靠性需求。

其次是关于可视化的一些东西,我特别希望能把 DBMS 的工作过程直观的展示出来,尤其是 SQL 解析那一块,可以画抽象语法树之类的,还能把表结构、元信息等画出来,想到这些就有点激动,这是驱使我做它的一大动力。

或许项目完成之后可以不仅仅是一个课程设计,如果逻辑与可视化做得比较好完全可以拿给老师教学用,直观的展示 SQL 的解析、生成关系代数、优化的内容,还有很多东西可以做动态展示,比如多粒度锁、基于日志的恢复,当然这些是后话了。

最后,完成这个项目是一个渐进的过程(比如先支持一小部分表达式,后面发现需要再增加),但文章也这么写的话结构就比较乱,因此在项目过程中所有文章都会随时更新。

设计与评估

DBMS 还是一个相当大的系统,老师说到时候只让我们实现一小部分功能,不过我现在提前做就要自己规划要实现哪些部分了。 这样要列出所有的模块/功能,划分一下依赖关系,评估一下实现的方案与难度,最后决定要实现的部分。

下面是一个数据库系统结构的图:

dbms

数据结构

关系型数据库的表使用二维数组存储。 一个 database 包含很多张表,而一个 dbms 的实例可以包含许多个 database 。 这里的每一级都会有一些 metadata 需要存储,初步想法是 metadata 同样使用表结构存储,这样更方便为用户提供编辑界面。

文件系统

比较难受的一点是,我要实现的是一个玩具模型,必然不会有大量数据的需求,最多也就是 MB 级别的数据量,这时文件系统只是作为一个持久化方案,而不是以之为中心。 对于这么少的数据完全可以全部放入内存,文件管理与缓冲区管理就显得没有什么意义。 那么实现 buffer 机制实属费力不讨好了,所以先实现一个基于内存的数据库管理系统,数据的存取直接通过序列化与反序列化实现。

还有一点是,之所以索引会采用b+树实现,是因为b+树对磁盘操作更亲和,需要的读写比较小,既然所有内容都在内存里,用其它平衡查找树代替b+树没准反而更快。

SQL 的解析与执行

DBMS 提供给用户的界面是 SQL (DDL + DML),对一个小的 DBMS 来说,这也是最复杂的部分。 SQL 文法属于 LALR(1) 文法这里有几个标准 SQL 的 BNF 声明和 HTML 版本可以看一下,十分巨大。 要从文法生成 parser 的话,需要一个 parser generator , Lex 与 Yacc 只能用于 C/C++ ,查了一下发现 JS 有个移植版,叫做 Jison (Bison in Javascript),用起来没有什么问题。 完整的 SQL 太大了,它的语法制导定义也不是我一己之力能够完成的,所以要实现它的一个子集。 很幸运,我在一个烂尾的项目中找到一份能用于 jison 的语法制导定义,要做的是在它的基础上进行精简或重构。

参考

在系统的结构设计上,参考了 redbase 数据库,它包含了文件系统、系统管理、语言执行、索引四个主要模块,在执行 SQL 时生成了物理计划,并没有逻辑计划, minidb 没有文件系统部分,索引还没有实现,其它的结构都与 redbase 相似。

物理计划的划分主要参考了 SQL Server 的文档

下一步

到目前为止,实现了SQL的解析、语义检查、执行功能,能够进行增删改查操作,可以创建、删除、切换数据库以及持久化数据。 不过只是实现了主要流程上的操作,如果有违规操作还是会漏洞百出。 下一步要做的是物理计划可视化,加入类型检查、数据完整性约束,再往后是索引。

目前的成果:

cur


Blog Comments powered by Isso.