一 开发说明

1.1 总体说明

本次项目以c++语言编写简易数据库，数据库为<key:value>的简单形式，在本项目中，限定key为整数且不考虑溢出问题，value为字符串类型，不可为空，长度最长为19（其中第20位为字符）。主体程序面向用户提供四种主要操作，分别为查找、添加、删除和修改。文件中数据结构主要采用B+树，实现了对删除的结点的空间回收。数据库cache模拟系统中的cache以利用文件读取的局部性来增加读写速度。文件以二进制形式打开以便于管理。

1.2 文件设计说明

1.2.1 索引文件设计说明

索引文件前4个字节为根节点所在地址，若为0则树为空，初始时。接着8个字节为第一个空白位置，初始时为8，即文件尾。然后依次是每个节点。每个节点分为三个部分，第一部分为12个字节，四个整数，分别是父节点地址、父节点在节点中的位置（从1开始）和当前节点关键码的个数，根节点父节点地址为0。第二部分为当前节点的关键码和其孩子的地址，若节点为叶节点，则为当前节点的关键码和关键码对应的值在数据文件中的地址的负数（因此可以根据孩子地址的正负来直接区别内部节点和叶子结点）。第三部分为下一个叶子节点的地址，若节点为内部节点，则该部分无意义。空白位置组成单项链表，最后一项始终为文件末尾。删除节点后将地址链接到链表头部。

1.2.2 数据文件设计说明

数据文件前四个字节为第一个空白位置，初始时为4。之后为数据，每条数据占用20个字节。空白位置组成单项链表，最后一项始终为文件末尾。删除节点后将地址链接到链表头部。

参考文档和完整的文档和源码下载地址：

https://www.write-bug.com/article/128.html