mini sql 系统详细设计说明书

1、 MiniSQL数据库系统详细设计报告文档编号：2 版 本 号：1.00文档名称 :详细设计报告 项目名称 ：MiniSQL 数据库系统设计开发时间:2001年10月-12月 开发人员:组长: 周森 3991102440 (计算机99F)组员: 郭振宇 3991102462 王淮 3991102449 韩璟璐 3991102438 何遥 3991102461指导老师: 孙建伶1. 引言 1.1 项目名称 MiniSQL 数据库系统设计与实现。1.2项目背景和内容概要 数据库系统设计与实现实验。主要目的：通过实验加深对DBMS及其内部实现技术的理解。实践系统软件开发的工程化方法。1.3相关资料、

2、缩略语、定义 MiniSQL: Mini Structural Query Language EngineAPI: application programming interface.MiniSQL用户部分Control InterfaceCmd InterpreterAPI Lib2. 系统结构 Catalog ManagerError LibMiniSQL内核部分Buffer ManagerRecord ManagerB+ Figure 12.1系统结构图Figure 1：MiniSQL数据库系统 系统结构图图中各标号简明解释：判断并接受用户字符输入，使做为解释器的输入。解释器对用户输入进

3、行翻译，产生操作数（所需API编码以及参数数组）。执行选定的API，返回用户所需的输出。BPlus、Record、Catalog类方法注册至API LIB,并整合生成适合于用户调用的API。BPlus、Record、Catalog类调用Buffer类的方法实现自己各自的方法。Buffer类方法对数据库文件进行直接操作。2.2系统目录结构MiniSQLbinincludedataDocsMiniSQL根目录可执行程序可用于二次开发的头文件系统运行相关文档,用户手册数据存放目录DB1DB2DBn数据库名称做为该数据库数据存放的根目录DATAFILE1DATAFILEnFigure 2Figure2

4、:MiniSQL数据库系统的文件结构其中bin目录下存放MiniSQL可执行文件；include目录下存放MiniSQL.h文件和相关的lib文件，可以应客户的需求进行应用级开发；Docs目录下存放一些系统开发文档，系统安装文档，系统维护文档以及版权信息文档等等。同时也提供系统对比已经商业化的DBMS，尚未开发的功能的相关文档。Data目录下存放数据文件，其下一级目录为各个数据库的名称，再下一级为各个数据库的具体数据文件。数据文件类型：对应于每一个table建立两个文件，dbf文件为具体数据存放文件，同时关于该table的目录信息亦存放于dbf文件的头信息处，idx文件为为primary ke

5、y建立的索引文件。2.3程序文件清单模块名程序文件名运行平台语言简要描述用户接口解释器Interpreter.hWindows/LinuxC/C+解释器模块头文件Interpreter.cppWindows/LinuxC/C+解释器模块实现文件API 集成Ctrl_Center.hWindows/LinuxC/C+API Lib头文件Ctrl_Center.cppWindows/LinuxC/C+API Lib实现文件异常处理Error.hWindows/LinuxC/C+Error Lib头文件Error.cppWindows/LinuxC/C+Error Lib实现文件系统内核B+树ZBt

6、ree.hWindows/LinuxC/C+B+树模块头文件ZBtree.cppWindows/LinuxC/C+B+树模块实现文件RecordRecord.hWindows/LinuxC/C+Record模块头文件Record.cppWindows/LinuxC/C+Record模块实现文件CatalogCatalog.hWindows/LinuxC/C+Catalog模块头文件Catalog.cppWindows/LinuxC/C+Catalog模块实现文件BufferBuffer.hWindows/LinuxC/C+Buffer模块头文件Buffer.cppWindows/LinuxC/

7、C+Buffer模块实现文件系统集成MainMiniSQL.hWindows/LinuxC/C+系统主程序头文件MiniSQL.cppWindows/LinuxC/C+系统主程序实现文件GvariableGlob_Var.hWindows/LinuxC/C+系统全局变量头文件Glob_Var.cppWindows/LinuxC/C+系统全局变量实现文件2.4基本设计概念1)系统目标设计并实现一个精简单用户SQL engine ，并在其中实现表定义、索引、标记录操作功能。其中：（1）表定义中列（属性）的类型至少支持三种(integer、char、float); (2 ) 每个表上要求至少建一个主

8、键上的B+树，支持多属性主键； （3）记录的插入、删除、修改等，即时更新相应的索引；（4）记录的搜索至少实现按主键查找，只是主键上的范围查找，包含遍历。2)结构清晰（1）用户模块和内核模块完全分开。（2）内核部分B+ 、Record、Catalog三个模块之间坚决不能互相调用方法和函数。（3）内核部分B+ 、Record、Catalog三个模块不能访问物理文件，而由Buffer模块实现物理文件操作的所有细节。(4）API Lib根据B+ 、Record、Catalog三个模块的方法整合生成 适合用户模块调用的API。 (5) 内核各个模块只向上负责，简化了各个模块之间的调用关系。2.5程序模块

9、说明2.5.1 Gvariable模块（系统集成子系统）1)目标：定义系统各种全局变量2)程序文件：Glob_Var.h, Glob_Var.cpp3)主要数据结构：FilePtr(由buffer模块提供)class FilePtrpublic: unsigned long FilePageID; /页编号 unsigned int Offset; /页内偏移 void Initialize(); /初始化为(0,0) void* MemAddr(); /转化为当前内存地址，由buffer负责转换 void ShiftOffset(int offset); /相对当前地址滑动offset;其他

10、全局的主要数据结构见API 集成模块。4)调用的其他模块：Buffer模块5)算法：无6)逻辑流程图：无7)测试要点：变量声明和定义，测试略。2.5.2 Main模块（系统集成子系统）1)目标：协调各其他各模块之间的关系,最终负责系统运行2)程序文件：MiniSQL.h, MiniSQL.cpp3)主要数据结构：MSG定义的是Get_Command 返回的消息 ，用于消息循环enum MSG CREATE, SELECT, INSERT, UPDATE, DELETE, DROP, QUIT msg;4)调用的其他模块：API 集成模块, Gvariable模块5)算法：参考windows消息

11、机制。6)逻辑流程图：(1)主程序流程：int main() Init_MiniSQL(); /初始化一些基本配置Run_MiniSQL(); /交互操作，是本程序的主体Exit_MiniSQL(); /先善后操作，再退出(2)Run_MiniSQL()程序流程函数采用的是类似MFC的消息循环机制，从Get_Command得到MSG消息，在调用相应的处理函数(来自API lib)。void Run_MiniSQL(); msg = SELECT; / 使得MSG不等于QUIT,进入循环 while( MSG != QUIT ) /消息循环 try msg = Get_Command(.); /

12、根据消息调用各处理 switch(msg) case CREATE : Create(.); break; 创建记录 case SELECT : Select(.); break; 选择记录 case INSERT : Insert(.); break; 插入记录 case UPDATE : Update(.); break; 更新记录 case DELETE : Delete(.); break; 删除记录 case DROP : Drop (.); break; 删除表 case QUIT : return; catch (int ERROR_CODE) /根据ERROR_CODE，打印错

13、误信息 7)测试要点：变量声明和定义，测试略。2.5.3 异常处理模块（用户接口子系统）1)目标：异常处理模块，定义系统所有可能的异常情况,并分配异常代号。2)程序文件：error.h,error.cpp3)主要数据结构：#define ErrorName ErrorCode; /异常宏定义char* ErrorMessage; /相关异常信息4)调用的其他模块：无5)算法：无6)逻辑流程图：无7)测试要点：模拟ErrorCode ,调用DispatchError(int errorcode)函数处理异常。2.5.4 API 集成模块(用户接口子系统)1)目标：根据B+ 、Record、Cat

14、alog、Interpreter四个模块所提供的方法整合生成适合于用户调用的API。此模块同时要求最终实现include目录下用于应用级开发所需的头文件。2)程序文件：Ctrl_Center.h、Ctrl_Center.cpp3)主要数据结构：见逻辑流程图4)调用的其他模块：Gvariable模块、B+模块、Record模块、Catalog模块、Interpreter模块、Gvariable模块。5)算法：在流程图里6)逻辑流程图：其中各主要操作流程（为直观计，相关的全局主要数据结构即列在一边）Figure 3Figure 4Figure 5Figure 67)测试要点：2.5.5 解释器模块

15、（用户接口子系统）1)目标：命令解释器的基本功能就是将用户的输入命令进行语法分析和语义解析并得到需要的命令参数,最后将该命令参数封装成对应命令的参数类对象,传回到APILIB模块2)程序文件：interpreter.h、interpreter.cpp3)主要数据结构：1有意字串:所谓有意字串即指一个以回车或空格或标志符来分割的有独立含义的字符串(不包括空格,回车,但标志符入” , “,” ; “视作有意字串,如一条命令create table tablename( variblename1 type1, variblename2 type2);则create ,”table”,”tablena

16、me”,”(“,”variblename1”,”type1”等都是一个有意字串2VSTR_BLK_PTR定义一个数据结构typedef struct *VSTR_BLK_PTR;typedef struct VSTR_BLKstring strValstr; / 有意字串VSTR_BLK_PTR p_vbpNext;/指向下一个有意字串的VSTR_BLK指针;该数据结构用于记录输入的有意字串,一个该变量表示一个有意字串.3.支持多类型 enum Column_Type i, c, f; /i-int c-char f-float 4支持 > >= < <= = != b

17、etweenand等关系运算符; enum Operator_Type B, BE, L, LE, E, NE,BETWEEN;4)调用的其他模块：异常处理模块本模块较为关键的几个处理：string InString()负责从用户的输入中读取一个有意字串,以构成VstringBlk的链表.5)算法:Step1.Void GetCommand()MakeVstrBlk();/利用一个读取函数将用户的所有输入整合成一个VstringBlk链表.根据VSTR_BLK链表中的第一个有意字串来调用相应的函数,封装回传的参数类;return;用户输入命令之后,给出提示要求用户键入命令,利用一个读取函数将用

18、户的所有输入(以该行最后一个字符是否” ; ”为标记)中的有意字串读入,掠过所有的空格和回车.所以在处理过程中只需一个全局变量VSTR_BLK_PTR p_vbpCmdPos表示对当前的命令的处理处于何位置,这样很容易得知控制的流程. 此时处于start state,对所输入的信息进行处理,根据命令的第一个有意字串进行分处理,如用户键入的第一个命令是”create table tablename CR”(CR 代表回车),则最终将会进入create function.逻辑流程图Figure 8所以该部分需要的函数列表如下typedef char *string;基本函数:1)string In

19、String()负责从用户的输入中读取一个有意字串, 2)MakeVstrBlkList()负责将有意字串链成链表.boolean StrCompare(string s1,string s2,boolean case)根据case值（0忽略大小写，1大小写敏感）来比较string s1和string s2，返回比较结果return value:0-string 1 string s23) TB_Create_Info& CreateProcess()进入create function,最后返回一个有关表的类TB_Create_Info(详见数据结构)4) TB_Insert_Info

20、& InsertProcess()进入insert function,最后返回一个有关表的类TB_Create_Info(详见数据结构)5) TB_Select_Info& SelectProcess()进入select function,最后返回一个有关表的类TB_Select_Info(详见数据结构)6) TB_Delete_Info& DeleteProcess()进入delete function,最后返回一个有关表的类TB_Delete_Info(详见数据结构)7) TB_Update_Info& UpdateProcess()进入update fun

21、ction,最后返回一个有关表的类TB_Update_Info(详见数据结构)Step2在进入具体的提供的5个具体功能的处理后,模块作的就是对用户的整个命令进行解析,最终给出一个封装了所有该种处理所需参数的类.如create function,TB_Create_Info& CreateProcess()检验每次输入是否符合要求直到state1.3;while(not “ ); ”)make a Create_Column;/得到一个有关列所有信息的类对象 将所得到的Create_Column对象和前面得到的的链起来;将所有的列对象封装成一个表对象信息TB_Create_Info.Re

22、turn;如下图,途中各条线代表InString()得到的输入,下面对几个要点解释一下: Figure 9a.任何状态下得到的输入和标示的不符,则记录该出错的行数,给用户一个提示, ,并throw errorcode,然后返回API控制中心;b.处理过程中, ” , “ 代表的含义是换行,所以有关行数的变量会加1,这个行数信息用于给出出错地点信息;Stept2.1逻辑流程Stept2.1.0 state1.1-state1.3均是一些常用状态,用于过渡; Stept2.1.1state1.3得到一个variablename时得到一个列名信息,此时需要对列名进行合法性检验,boolean Che

23、ckColName(string strColName)Stept2.1.2state1.4得到一个type时得到一个类型信息,需要对该类型信息进行检验,此类型信息可能含有长度信息,如char(8),所以还要对类型信息进行处理,利用一个函数boolean GetTypeInfo(column_type ctColType, int iColLength)Stept2.1.3由于一个列信息可能有可能还含有约束条件(如在列类型信息后不是紧跟”,”则之间必只是约束条件),但为了处理方便,将实际上并没有约束条件的情况视作有约束条件但该条件为空,所以在state1.5还必须要对列类型后的有意字串进行解析

24、,需要考虑的约束条件只有typedef struct CONSTRAINTCONDint min; /下限，如例中的00000000intmax; /上限，如例中的12345678 Operator_Type Oper_Type; /关系运算符类型，如<, >=, =等等boolnotnull; /isnull1，则此字段有is null的限制boolisprimary;所以还需要一个约束条件检验函数,CONSTRAINTCOND& GetStraintInfo( )Stept2.1.4state1.6要对每一行进行处理,这些每一行都代表一条列信息,所以在state1.6中

25、需要对该行读到的列名,列类型,约束信息进行封装处理成一个Create_Column 类将它连接到上一个Create_Column类对象上state1.6可能直接碰到 ); (意即连续的两个有意字串是” ) “和 “ ; “),则可直接跳入该过程的最终状态state1.7,在该状态中将所有的已连好的Create_Column类对象封装成一个TB_Create_Info对象,传出去至此,该CreateProcess()过程结束.而对于其他几个function如TB_Insert_Info& InsertProcess()TB_Insert_Info& SelectProcess()

26、TB_Delete_Info& DeleteProcess()TB_Update_Info& UpdateProcess()其基本过程一致,下面给出状态图,其流程不再详述.Figure 10Figure 11Figure 12Figure 136)测试要点：1) 注意程序的健壮性,对用户的各种输入错误都要有很好的检测,并检验errorcode有无失误;2) 本程序对空格和回车选择了视而不见的处理方式将其略去不管,所以测试要证明这种做法不会对程序的正确性和健壮性产生影响;2.5.6 B+树模块（系统内核子系统）1)目标：提供数据库快速检索功能，并实现B树自身调整。2)程序文件：Z

27、BTree.h、ZBTree.cpp3)主要数据结构：索引文件头信息Typedef struct FilePtr FirstEmptyBlock; / the address of the first empty block FilePtr LastEmptyBlock; / the address of the last empty block FilePtr FirstNewBlock; / the address of the first new block FilePtr root; / the address of the root FilePtr start; / the addr

28、ess of the most left node int KeyAttrNum; / the number of fields(attributes) in primary key int KeySize; / sizeof(Key_Attr) * KeyAttrNum int MaxItemNum; / the max number of keys in a nodeIndex_Head; ZBTree_Index是一个管理索引文件的类,定义如下:class ZBTree_Index public: ZBTree_Index(); ZBTree_Index(); void Create_H

29、ead(char* KeyStr); / produce the information in the IdxHead void WriteHeadToFile(); / write the information to the head of the file void ReadHeadFromFile(); / read the information form the head of the file void SetKeyInfo(char* Key_Info); / calculate the Keysize and KeyAttrNum FilePtr GetRoot(); / g

30、et FilePtr of the root FilePtr GetStartNode(); / get FilePtr of the leftmost node int GetKeySize(); / get the size of a key int GetKeyAttrNum(); / get the key attribute number in a key int GetMaxItemNum(); / get the max number of items in a key char* GetKeyInfo(); / get the key information private:

31、Index_Head IdxHead; / the head of the index file for B+ tree char* KeyInfo; / a string record the information of the key ;Block里的数据，放在block中的尾部,Block为空时，此数据有效，如图 FileAttr NextBlock; / point the previous empty blockB+Tree 的节点信息（主键内容，指针） Next_Block主键是由Key_Attr结构的链表组成,如右图：typedef struct Key_Attr *pKey_

32、Attr;Key_Arrttypedef struct Key_AttrKey_Arrt Limit_Value value; pKey_Attr next;Figure 14;Index文件的结构类似于record，空闲块用指针连起来，用两个指针管理空闲块链表的头和尾。 节点结构：IsLeaf |ItemOnNode | p0,k0,p1,k1,.,pMaxItemNum-1,kMaxItemNum-1,pMaxItemNum 节点类型（叶/非叶）儿子个数P1K1P2K2Pn-1Kn-1PnFigure 15节点类：class ZBTreeNode public: ZBTreeNode()

33、p = new FilePtrMaxItemNum+1; k = new pKey_AttrMaxItemNum; ZBTreeNode(); GatherInBlock(); 将节点的分散空间合在一个连续的block SepaFormBlock(); 将一个连续的block分散到ZBTreeNode中 private: bool IsLeaf; 是否是叶节点 int ItemOnNode; 有效的key数 FilePtr *p; 指向子节点的指针 pKey_Attr *k; key的指针数组int MaxItem; 节点能容纳的最大key的数;key的位置typedef struct Key

34、_Location* pKey_Location;typedef struct Key_Location FilePtr pNode ; 节点指针 int offset; 所在节点的第几个key;B+Tree的类:管理b+树的的操作:class ZBTree public: ZBTree(); ZBTree(); Create(int); 初始化 ZBTreeNode* GetRoot(); 得到根结点 ZBTreeNode* GetStartNode(); 得到第一个叶节点 FilePtr GetCurRec(Key_Location); 得到当前的Record指针 Bool MoveToN

35、ext(Key_Location); 使Key_Location移到next bool Compare_Key(pKey_Attr,pKey_Attr); 比较两个key的大小 ZBTreeNode* GetSonnode(FilePtr); 得到内存中的字节点 ZBTreeNode* GetParentnode(ZBTreeNode*); 得到父节点 pNode_Key * Search_Key(pKey_Attr); 定位到某个key void Select(Condition_Info&,); void Delete(pKey_Attr,int); 在BTree中删除key和指针

36、 void Insert(pKey_Attr,int); 在BTree中插入key和指针 void Delete_Entry(ZBTreeNode*,pKey_Attr,int); 在某个节点中删除key和指针 void Insert_Entry(ZBTreeNode*,pKey_Attr,int); 在某个节点中插入key和指针 private: ZBTreeNode *root; 根节点 ZBTreeNode *start; 第一个叶节点;4) 算法当创建talbe的时候,调用b+数的ZBTree:Create()->ZBTree_Index:Create_Head(char*)&#

37、224; ZBTree_Index:WriteHeadToFile(),计算b+数的一些必要信息,并写到文件中去.Search 算法描述:pNode_Key * Search(pKey_Attr SearchKey); 定位到某个key for(;) get the current node; /compare Key with the key in the current node; for(;) get the current key;compare the key with SearchKey; if ( = ) return the address of the key; else (

38、 < ) goto the next key; else if (reach the end of the current node) break; if (reach the leaf) break; return NULL; / the Search isnt existed部分完成的函数的源代码:void ZBTree_Index:Create_Head(char* KeyStr) SetKeyInfo(KeyStr); / calculate the Keysize and KeyAttrNum / calculate the MaxItemNum in a node IdxHe

39、ad.MaxItemNum = ( BTreeNodeSize - sizeof(bool) - sizeof(int) - sizeof(FilePtr) ) / ( sizeof(FilePtr) + IdxHead.KeySize ); /no empty block IdxHead.FirstEmptyBlock.FilePageID = 0; IdxHead.FirstEmptyBlock.Offset = 0; IdxHead.LastEmptyBlock.FilePageID = 0; IdxHead.LastEmptyBlock.Offset = 0; /the first a

40、ddress of the BTree node IdxHead.FirstNewBlock.FilePageID = 1; IdxHead.FirstNewBlock.Offset = SizeOfPageHead; / the root isn't existed IdxHead.root.FilePageID = 0; IdxHead.root.Offset = 0; / the start node isn't existed IdxHead.start.FilePageID = 0; IdxHead.start.Offset = 0; / the key inform

41、ation KeyInfo = KeyStr;/ write the infomation to the head of the btree index filevoid ZBTree_Index:WriteHeadToFile() / get the start address which store the head char address256; strcpy(address,CurLocation); strcat(address,CurRelationName); strcat(address,".idx"); Table test = MyDBaddress;

42、 FilePtr ptr = test.GetIdxPoint(); / write IdxHead void* temp = (void*)&IdxHead; FilePtr next; next = MemWrite( temp,sizeof(Index_Head),&ptr); / write Key information temp = (void*)KeyInfo; MemWrite(temp,strlen(KeyInfo) + 1,&next);/ read the infomation from the head of the btree index fi

43、levoid ZBTree_Index:ReadHeadFromFile() / get the start address which store the head char address256; strcpy(address,CurLocation); strcat(address,CurRelationName); strcat(address,".idx"); Table test = MyDBaddress; FilePtr ptr = test.GetIdxPoint(); / read IdxHead Index_Head* temp; temp = (In

44、dex_Head*) ( ptr.MemAddr() ); IdxHead = *temp; / read key jnformation ptr.ShiftOffset(sizeof(Index_Head); KeyInfo = (char*) (ptr.MemAddr();插入和删除算法在书上以详述，这里不再叙述。5)调用的其他模块：Buffer模块、异常处理模块6)逻辑流程图：无7)测试要点：写驱动程序,先跟buffer模块结合,提供连续的key,作为输入,检查B+Tree 的各个流程,提供各种异常处理信息.2.5.7 Record模块（系统内核子系统）1)目标：实现单条记录的所有操作，

45、包含插入、删除、更新、选取、打印等。2)程序文件：record.h、record.cpp3)主要数据结构：int ErrorCode; /异常代号char* ErrorMessage; /相关异常信息class record public:Select();Insert();Updata();Delete();Print();Printhead();private: FIlePtr DelFirst; FilePtr DelLast ; FilePtr InsertLast;4)调用的其他模块：Buffer模块、异常处理模块5)算法：FilePtr record:Insert (Rec_Inf

46、o& a)temp a.head;FilePtr InsertPlace =PlaceFind();Void* ptr2write = (void*)InsertPlace; Int * i =&(temp->value);Memwrite( (void*)insert_place,sizeof(FilePtr) ,ptr2write);Ptr2write += sizeof(FilePtr);while(temp)MemWrite( i，temp->column_length ,prtr2write);Switch(ColType) case i: Ptr2wri

47、te += temp->ColLength; break; case f: Ptr2write += temp->ColLength; break; case c:Ptr2write=Ptr2write+temp->ColLength+1; temp = temp->next;return InsertPlace;传出的是插入记录的地址） PlaceFind()if (del_first=del_last=0)(这里需要考虑一下块的空闲地方的大小是否小于所要插入的记录的大小)Switch(ColType) case i: InsertPlace=InsertLast+T

48、otalLength+sizeof(FilePtr); break; case f: InsertPlace=InsertLast+TotalLength+sizeof(FilePtr); break; case c: InsertPlace=InsertLast+TotalLength+1+sizeof(FilePtr); InsertPlace=InsertLast+TotalLength+sizeof(FilePtr);ElseInsertPlace=DelFirst; DelFirst=DelFirst->FilePtr;return InsertPlace;record:Delete (FilePtr&DelTarget) FilePtr * temp=(FilePtr *) DelTarget.Memaddr(); if(DelFirst=DelLast=0)DelFirst=temp; DelLast_=temp; temp->Page