微型数据库开发记录
前言
近三周应小学期老师要求,和4位队友合作开发了一个微型数据库系统。由于耗费了许多的精力,我想将开发过程记录在这个博客上。
功能性需求:
- 创建数据库和表,能够以文件形式保存在磁盘上(操作系统的文 件、进程管理,数据结构 的 B树)
- 支持表的增删改查(数据库 中SQL形式,编译的词法语法检查)
- SQL中支持通配符(数据结构的查找)、多表连接(操作系统 的 文件管理)
- 支持整数、实数、字符(串)、日期等数据类型
- 支持索引(数据库、数据结构 )
性能性需求
- 单表记录最大行数不少于10万行,不少于10 列
- 单表响应时间不多于 1秒(普通笔记本)
- 主表不少于5000行,子表不少于20000行时,连接操作响应时 间不多于 2 秒
痛苦的开端
最初的迷茫
开始的时候确实是啥也不知道,一堆人在教室里商量了半天也没想明白该干些什么,就留了两天各自查资料。等大家查完,在教室里一讨论,就发现任务极其重大。由于要实现5000*20000级别的表连接,还有100 000级别的数据插入,因此我们需要考虑底层的文件存储,但由于开发经验的不足和工期较短,我们在讨论中断定,凭空实现完全的页面管理对我们来说是不可能的,因此决定退而求其次,找一份有页面管理的借鉴一下。
因此,我们翻看了sqlite的源码,还通篇学习了一门斯坦福的课程(代码仓库叫redbase),在途中,还重新确定了我们要实现的关键字等需求。
借鉴都借鉴不明白
然后就出现了问题,我们找到了一份很好的页面管理代码,但光页面管理(包括缓冲区管理)的代码量就直接超过了8000行,为了实现它我们需要做的工作过于繁复(虽然我们确实尝试了一天)。
同时,Linux开发也对我们组造成了较大的麻烦,因为有开发经验的仅有一人,其他人光环境配置就花了很长时间。后来采用先富带后富的方式,总算是搞定了整组的环境。
借鉴不了,想一个自己的框架吧!
最后,我们发现,我们的这种特种需求,只有我们自己琢磨一个框架来才能够满足3周内开发完成,且能够实现一定的文件管理和查询优化。
这里用文字形容一下我们初步商量的框架
顶层:词法分析->语法分析,产出一棵抽象语法树
中层:语义分析,并实现一系列数据库操作函数
底层:B+树代码和物理存储管理代码,存储二进制数据。
中层咱暂时实在想不明白,就先大致写了一点儿,之后先把顶层和底层开发出来,到时候再看中层该怎么搞。
辛苦又充满成长的开发过程
经历了鸡飞狗跳,还有一堆学校其他杂事(搬家,做华为云实验)的一周之后,我们正式开始开发。
顶层
顶层被我们归类为最困难的工作,我们想了些取巧的办法让它稍微简单一点儿。这块儿是组里大佬写的,我也只是有所了解。
参考redbase的顶层(就算是斯坦福的课,顶层代码也是预先写好,不用学生写的),我们按照自己的需求写了一份语法文件,并用yacc(应该)生成分析代码。
底层
第二周折腾了老半天,把一份B+树代码折腾出来了,它还满足我们的要求(改泛型改了一个周末):能够存储int,float和string类型的数据(本来还有个要求是,一级索引将和纯数据文件放在一起,方便存取,但泛型这东西实在不是一个初学c++的同志能整的这么明白的,就没实现)
数据文件(初版)
这里给出示例文件框架
save
-table1 示例表名
–table1.data存放二进制数据文件
—-table1.meta存放表说明文件
—-IND//存放索引
——-table1//自增主键索引
—其他索引