一 开发说明
本次项目以c++语言编写简易数据库，数据库为<key:value>的简单形式，在本项目中，限定key为整数且不考虑溢出问题，value为字符串类型，不可为空，长度最长为19（其中第20位为\0字符）。主体程序面向用户提供四种主要操作，分别为查找、添加、删除和修改。文件中数据结构主要采用B+树，实现了对删除的结点的空间回收。数据库cache模拟系统中的cache以利用文件读取的局部性来增加读写速度。文件以二进制形式打开以便于管理。
索引文件前4个字节为根节点所在地址，若为0则树为空，初始时。接着8个字节为第一个空白位置，初始时为8，即文件尾。然后依次是每个节点。每个节点分为三个部分，第一部分为12个字节，四个整数，分别是父节点地址、父节点在节点中的位置（从1开始）和当前节点关键码的个数，根节点父节点地址为0。第二部分为当前节点的关键码和其孩子的地址，若节点为叶节点，则为当前节点的关键码和关键码对应的值在数据文件中的地址的负数（因此可以根据孩子地址的正负来直接区别内部节点和叶子结点）。第三部分为下一个叶子节点的地址，若节点为内部节点，则该部分无意义。空白位置组成单项链表，最后一项始终为文件末尾。删除节点后将地址链接到链表头部。
数据文件前四个字节为第一个空白位置，初始时为4。之后为数据，每条数据占用20个字节。空白位置组成单项链表，最后一项始终为文件末尾。删除节点后将地址链接到链表头部。
用户版和正确性测试版中每次操作会将相关信息写入日志文件，主要用于程序调试。
文件第一个数字为需要进行的操作，数字1、2、3的含义与用户版对应，其后是需要操作的key，根据操作种类确定后面是否有value。正确性测试文件中4的含义为测试所有key。性能测试文件名最后数字问测试循环单位，而非测试数据量。
cache类模拟系统中的cache，将最近使用过的数据放入其中，利用局部性加快数据的读写速度。cache大小固定，为16384，即2^14。cache中每个数据有四个值：int key、string value、bool dirty、bool valid。其中valid表示这个数据是否有效，dirty表示这个key对应的值是否被修改过。
网友评论