实现自己的数据库一

　　一前言
　　从上篇原创文章到现在又是新的一年，今天是2023年的大年初三，先在这里祝各位亲爱的老铁们新年快乐，身体健康，在新的一年里更帅气、更漂亮，都能完成自己的小目标。
　　一直以来，我对数据存储还是比较感兴趣的，计算机从大的抽象层次来说，只干了三件事情，存入数据，计算，输出数据。所以数据的存储和搜索可以说是占据计算机的大半功能了。在工作中，也自己设计过一些存储和索引，不过是简单的哈希表的结构存储，对以B树为核心的数据库一直挺有兴趣，所以翻找了一些原理文章和源码研究了下，虽然原理看的不少，但是总觉得没有动手亲自写过还是学习的不够深刻，同时在github上找到了一步步写简单db的项目，于是开始借鉴学习后（代码参考后有所改进）有了这一系列文章。
　　这次也不定啥目标了，怕坑挖大了，填不完，能写多少就写多少吧，同时希望自己写的这个开源，并将自己以后所学所知的一些优化的技巧应用在这上面，当一个练手的小项目吧，不要相信题目，题目只是吸引大家进来的，请原谅我厚着脸皮起的这么大的题目。二开始2。1名字和设计原则名字这是个练手的小的不能再小的数据库，最终很可能会基于B树来构建，至于后续的谁知道那，所以起了个名叫microdb，会用纯c开发，希望用标准的C开发，仿照sqlite，不会考虑多系统的兼容性，这是小玩具，仅此而已。设计原则简单！简单！简单！2。2关于数据库存储的疑问
　　在设计需要持久化到硬盘索引的时候，觉得写的不够好，数据结构还有存储格式有很大的优化空间。总在想在Mysql等数据库上，上亿条记录最多通过四次的磁盘读就搜寻到了需要的数据，这个是怎么实现的？内存对应的数据是何时持久化到磁盘上的？B树上每个分支的指针怎么保存，内存里面就是地址，B树持久化到磁盘上，这个指针是磁盘块的地址吗？2。3sqlite
　　只所以仿照sqlite，原因无非是它够小，只有一个c文件，功能少模仿简单。
　　说明：整体来说sqlite将sql命令通过分词、解析和代码生成器最后生成字节码，在虚拟机上运行，直到它完成或返回结果、或遇到致命错误、或中断。2。3第一个版本
　　主要开发工具vscode，采用xmake做c的构建工具，主要是比较简单和方便，可以跨平台使用，不了解的可以参考我的xmake构建工具的文章。新建个项目，最终展示如下：
　　先来仿照sqlite的命令行实现个简单的解释器，它会循环执行：读取用户输入执行命令输出结果继续等待用户输出。关键代码如下：intmain（intargc，charargv）｛InputBufferinputbuffernewinputbuffer（）；while（true）｛printprompt（）；readinput（inputbuffer）；if（strcmp（inputbufferbuffer，。exit）0）｛closeinputbuffer（inputbuffer）；exit（EXITSUCCESS）；｝else｛printf（unkowncommand：s。，inputbufferbuffer）；｝｝return0；｝
　　其中InputBuffer为自定义的保存用户输入的缓冲区，读取一行数据后判断命令是否为。exit命令，不是退出命令则打印不识别命令，是退出命令则退出，非常简单：typedefstruct｛charbuffer；sizetbufferlength；ssizetinputlength；｝InputBuffer；intgetlinemy（charbuffer，intlength，FILEfd）｛inti0；charch；charbuf〔MAXLEN〕｛0｝；while（（chfgetc（fd））！EOFch！）｛if（MAXLEN1i）｛break；｝buf〔i〕ch；｝lengthi；buf〔i〕；buffer（char）malloc（sizeof（char）（i1））；assert（buffer！NULL）；strncpy（buffer，buf，i1）；returni；｝voidreadinput（InputBufferinputbuffer）｛ssizetbytesreadgetlinemy（（inputbufferbuffer），（inputbufferbufferlength），stdin）；if（bytesread0）｛printf（Errorreadinginput）；exit（EXITFAILURE）；｝inputbufferinputlengthbytesread；inputbufferbuffer〔bytesread〕0；｝
　　运行提示行：F：ccodemicrodbmybuildwindowsdebugmicrodbmy。exemicrodb。testunkowncommand：。test。microdb。helpunkowncommand：。help。microdb。exit三小小的改进版本3。1支持语句识别
　　上个版本的功能除了识别。exit退出外，没啥其他有用的功能，这个版本先添加对语句的支持，另外我们区分下点号开头的表示是元命令，否则就是正常的sql语句，需要我们解析执行的先不管怎么解析和执行。第2版的main函数，内容如下：intmain（intargc，charargv）｛InputBufferinputbuffernewinputbuffer（）；while（true）｛printprompt（）；readinput（inputbuffer）；if（inputbufferbuffer〔0〕。）｛switch（dometacommand（inputbuffer））｛case（METACOMMANDSUCCESS）：continue；case（METACOMMANDUNRECOGNIZEDCOMMAND）：printf（Unrecognizedcommands，inputbufferbuffer）；continue；｝｝else｛Statementstatement；switch（preparestatement（inputbuffer，statement））｛case（PREPARESUCCESS）：break；case（PREPAREUNRECOGNIZEDSTATEMENT）：printf（Unrecognizedkeywordatstartofs。，inputbufferbuffer）；continue；｝executestatement（statement）；printf（Executed。）；｝｝return0；｝
　　将整个输入分成两个部分，以点号开头的表示元命令，不然就当成sql语句进行处理，解析好语句后，就执行，执行只是打印个输出内容：F：ccodemicrodbmybuildwindowsdebugmicrodbmy。exemicrodb。testUnrecognizedcommand。testmicrodb。helpUnrecognizedcommand。helpmicrodbinsertaThisiswherewewoulddoaninsert。Executed。microdbselectaThisiswherewewoulddoaselect。Executed。microdb。exit
　　关于语句和解析语句的定义如下：typedefenum｛METACOMMANDSUCCESS，METACOMMANDUNRECOGNIZEDCOMMAND｝MetaCommandResult；typedefenum｛STATEMENTINSERT，STATEMENTSELECT｝StatementType；typedefenum｛PREPARESUCCESS，PREPAREUNRECOGNIZEDSTATEMENT｝PrepareResult；typedefstruct｛StatementTypetype；｝Statement；MetaCommandResultdometacommand（InputBufferinputbuffer）｛if（strcmp（inputbufferbuffer，。exit）0）｛closeinputbuffer（inputbuffer）；exit（EXITSUCCESS）；｝else｛returnMETACOMMANDUNRECOGNIZEDCOMMAND；｝｝PrepareResultpreparestatement（InputBufferinputbuffer，Statementstatement）｛if（strncmp（inputbufferbuffer，insert，6）0）｛statementtypeSTATEMENTINSERT；returnPREPARESUCCESS；｝elseif（strncmp（inputbufferbuffer，select，6）0）｛statementtypeSTATEMENTSELECT；returnPREPARESUCCESS；｝returnPREPAREUNRECOGNIZEDSTATEMENT；｝voidexecutestatement（Statementstatement）｛switch（statementtype）｛case（STATEMENTINSERT）：printf（Thisiswherewewoulddoaninsert。）；break；case（STATEMENTSELECT）：printf（Thisiswherewewoulddoaselect。）；break；｝｝3。2支持在内存中插入和查询语句
　　首先数据保存在内存中，采用硬编码的方式来保存用户信息，用户信息如下表：
　　插入语句和查询语句的语法也进行了简化，插入语句如下：insert1cstackfoobar。comselect
　　整体实现思路如下：扩展解析功能，将插入的数据以行为基本单元保存在称为页的一块内存中。每个页面有很多行组成，行紧凑排列。整个系统会根据需要申请多个页面，所有的页面都保存在一个大数组里面。
　　对row的定义如下：typedefstruct｛uint32tid；charusername〔COLUMNUSERNAMESIZE〕；charemail〔COLUMNEMAILSIZE〕；｝Row；判断数据类型的长度，（Struct）0是把null强转为Struct指针，后获取属性，这里面只获取类型所以不会报错definesizeofattribute（Struct，Attribute）sizeof（（（Struct）0）Attribute）获取ID的属性的长度constuint32tIDSIZEsizeofattribute（Row，id）；获取用户名的长度constuint32tUSERNAMESIZEsizeofattribute（Row，username）；获取邮箱的长度constuint32tEMAILSIZEsizeofattribute（Row，email）；ID偏移量constuint32tIDOFFSET0；用户名偏移量constuint32tUSERNAMEOFFSETIDOFFSETIDSIZE；邮箱的偏移量constuint32tEMAILOFFSETUSERNAMEOFFSETUSERNAMESIZE；整行长度constuint32tROWSIZEIDSIZEUSERNAMESIZEEMAILSIZE；
　　列的长度和偏移量
　　下面两个函数比较关键，即序列化列和反序列化列，这里面序列化并没有把数据写入到磁盘，只是放入一块连续的平铺的内存中而已，不过这个却是可以方便持久化到磁盘上。序列化行，将row信息放入连续内存行中voidserializerow（Rowsource，voiddestination）｛memcpy（destinationIDOFFSET，（sourceid），IDSIZE）；memcpy（destinationUSERNAMEOFFSET，（sourceusername），USERNAMESIZE）；memcpy（destinationEMAILOFFSET，（sourceemail），EMAILSIZE）；｝反序列化，将内存块行转成rowvoiddeserializerow（voidsource，Rowdestination）｛memcpy（（destinationid），sourceIDOFFSET，IDSIZE）；memcpy（（destinationusername），sourceUSERNAMEOFFSET，USERNAMESIZE）；memcpy（（destinationemail），sourceEMAILOFFSET，EMAILSIZE）；｝
　　定义一个页面为4KB大小，然后定义最大只能保存100个页面，每个页面再按照每个用户总的字节数大小进行划分，具体如下：总页数defineTABLEMAXPAGES100每页的大小constuint32tPAGESIZE4096；每页可以保存row的总量constuint32tROWSPERPAGEPAGESIZEROWSIZE；整个表可以保存的总的数据量constuint32tTABLEMAXROWSROWSPERPAGETABLEMAXPAGES；typedefstruct｛uint32tnumrows；voidpages〔TABLEMAXPAGES〕；｝Table；
　　行不跨页，每页会有些浪费空间。定位行的算法也是常用在布隆过滤器的算法，如下：voidrowslot（Tabletable，uint32trownum）｛uint32tpagenumrownumROWSPERPAGE；voidpagetablepages〔pagenum〕；if（pageNULL）｛pagetablepages〔pagenum〕malloc（PAGESIZE）；｝uint32trowoffsetrownumROWSPERPAGE；uint32tbyteoffsetrowoffsetROWSIZE；return（char）pagebyteoffset；｝
　　通过：uint32tpagenumrownumROWSPERPAGE；来定位具体的页，通过uint32trowoffsetrownumROWSPERPAGE；来定位具体的row，然后通过offset来定义在页面的具体偏移量。uint32tbyteoffsetrowoffsetROWSIZE；return（char）pagebyteoffset；
　　插入和查询函数定义如下：ExecuteResultexecuteinsert（Statementstatement，Tabletable）｛if（tablenumrowsTABLEMAXROWS）｛returnEXECUTETABLEFULL；｝Rowrowtoinsert（statementrowtoinsert）；serializerow（rowtoinsert，rowslot（table，tablenumrows））；tablenumrows1；returnEXECUTESUCCESS；｝ExecuteResultexecuteselect（Statementstatement，Tabletable）｛Rowrow；for（uint32ti0；itablenumrows；i）｛deserializerow（rowslot（table，i），row）；printrow（row）；｝returnEXECUTESUCCESS；｝
　　插入比较简单，关键是定位到具体的页面的偏移量，将row的内容持久化到内存块中。查询是每次都是全部查询没有查询全部的功能。四第一个正式版本
　　代码一共320行，要定义为main。cpp，用c编译器编译才可以，虽然大部分是c的语法，但是定义const外部产量原因，c编译器无法通过。代码实现了内存一个固定表格的插入和查询功能，和一个交互界面，下一阶段是实现文件的持久化和B树的存储功能。includestdio。hifdefined（MSCVER）includeBaseTsd。htypedefSSIZETssizet；endifincludestdint。hincludestring。hincludemalloc。hincludecstdlibifndeftruedefinetrue1definefalse0endifdefineEXITSUCCESS0defineMAXLEN1024pragmawarning（disable：4819）defineCOLUMNUSERNAMESIZE32defineCOLUMNEMAILSIZE255defineTABLEMAXPAGES100元命令的解析结果typedefenum｛METACOMMANDSUCCESS，METACOMMANDUNRECOGNIZEDCOMMAND｝MetaCommandResult；插入和查询语句typedefenum｛STATEMENTINSERT，STATEMENTSELECT｝StatementType；解析命令结果typedefenum｛PREPARESUCCESS，PREPAREUNRECOGNIZEDSTATEMENT，PREPARENEGATIVEID，PREPARESTRINGTOOLONG，PREPARENEGATIVEID，PREPARESYNTAXERROR｝PrepareResult；执行结果typedefenum｛EXECUTESUCCESS，EXECUTETABLEFULL｝ExecuteResult；行定义typedefstruct｛uint32tid；charusername〔COLUMNUSERNAMESIZE1〕；charemail〔COLUMNEMAILSIZE1〕；｝Row；表的定义typedefstruct｛uint32tnumrows；voidpages〔TABLEMAXPAGES〕；｝Table；语句定义typedefstruct｛StatementTypetype；Rowrowtoinsert；｝Statement；缓冲区定义typedefstruct｛charbuffer；sizetbufferlength；ssizetinputlength；｝InputBuffer；definesizeofattribute（Struct，Attribute）sizeof（（（Struct）0）Attribute）constuint32tIDSIZEsizeofattribute（Row，id）；constuint32tUSERNAMESIZEsizeofattribute（Row，username）；constuint32tEMAILSIZEsizeofattribute（Row，email）；偏移量constuint32tIDOFFSET0；constuint32tUSERNAMEOFFSETIDOFFSETIDSIZE；constuint32tEMAILOFFSETUSERNAMEOFFSETUSERNAMESIZE；constuint32tROWSIZEIDSIZEUSERNAMESIZEEMAILSIZE；constuint32tPAGESIZE4096；constuint32tROWSPERPAGEPAGESIZEROWSIZE；constuint32tTABLEMAXROWSROWSPERPAGETABLEMAXPAGES；InputBuffernewinputbuffer（）｛InputBufferinputbuffer（InputBuffer）malloc（sizeof（InputBuffer））；inputbufferbufferNULL；inputbufferbufferlength0；inputbufferinputlength0；returninputbuffer；｝intgetlinemy（charbuffer，sizetlength，FILEfd）｛inti0；charch；charbuf〔MAXLEN〕｛0｝；while（（chfgetc（fd））！EOFch！）｛if（MAXLEN1i）｛break；｝buf〔i〕ch；｝lengthi；buf〔i〕；buffer（char）malloc（sizeof（char）（i1））；strncpy（buffer，buf，i1）；returni；｝voidprintrow（Rowrow）｛printf（（d，s，s），rowid，rowusername，rowemail）；｝从命令行读取一行命令voidreadinput（InputBufferinputbuffer）｛ssizetbytesreadgetlinemy（（inputbufferbuffer），（inputbufferbufferlength），stdin）；if（bytesread0）｛printf（Errorreadinginput）；exit（EXITFAILURE）；｝inputbufferinputlengthbytesread；inputbufferbuffer〔bytesread〕0；｝voidcloseinputbuffer（InputBufferinputbuffer）｛free（inputbufferbuffer）；free（inputbuffer）；inputbufferNULL；｝解析元命令MetaCommandResultdometacommand（InputBufferinputbuffer）｛if（strcmp（inputbufferbuffer，。exit）0）｛closeinputbuffer（inputbuffer）；exit（EXITSUCCESS）；｝else｛returnMETACOMMANDUNRECOGNIZEDCOMMAND；｝｝解析插入语句PrepareResultprepareinsert（InputBufferinputbuffer，Statementstatement）｛statementtypeSTATEMENTINSERT；charkeywordstrtok（inputbufferbuffer，）；charidstringstrtok（NULL，）；charusernamestrtok（NULL，）；charemailstrtok（NULL，）；if（idstringNULLusernameNULLemailNULL）｛returnPREPARESYNTAXERROR；｝intidatoi（idstring）；if（id0）｛returnPREPARENEGATIVEID；｝if（strlen（username）COLUMNUSERNAMESIZE）｛returnPREPARESTRINGTOOLONG；｝if（strlen（email）COLUMNEMAILSIZE）｛returnPREPARESTRINGTOOLONG；｝statementrowtoinsert。idid；strcpy（statementrowtoinsert。username，username）；strcpy（statementrowtoinsert。email，email）；returnPREPARESUCCESS；｝语句的解析PrepareResultpreparestatement（InputBufferinputbuffer，Statementstatement）｛if（strncmp（inputbufferbuffer，insert，6）0）｛returnprepareinsert（inputbuffer，statement）；｝elseif（strncmp（inputbufferbuffer，select，6）0）｛statementtypeSTATEMENTSELECT；returnPREPARESUCCESS；｝returnPREPAREUNRECOGNIZEDSTATEMENT；｝持久化rowvoidserializerow（Rowsource，voiddestination）｛memcpy（（char）destinationIDOFFSET，（sourceid），IDSIZE）；memcpy（（char）destinationUSERNAMEOFFSET，（sourceusername），USERNAMESIZE）；memcpy（（char）destinationEMAILOFFSET，（sourceemail），EMAILSIZE）；｝反持久化rowvoiddeserializerow（voidsource，Rowdestination）｛memcpy（（destinationid），（char）sourceIDOFFSET，IDSIZE）；memcpy（（destinationusername），（char）sourceUSERNAMEOFFSET，USERNAMESIZE）；memcpy（（destinationemail），（char）sourceEMAILOFFSET，EMAILSIZE）；｝核心row的定位voidrowslot（Tabletable，uint32trownum）｛uint32tpagenumrownumROWSPERPAGE；voidpagetablepages〔pagenum〕；if（pageNULL）｛pagetablepages〔pagenum〕malloc（PAGESIZE）；｝uint32trowoffsetrownumROWSPERPAGE；uint32tbyteoffsetrowoffsetROWSIZE；return（char）pagebyteoffset；｝核心定位row之后持久化ExecuteResultexecuteinsert（Statementstatement，Tabletable）｛if（tablenumrowsTABLEMAXROWS）｛returnEXECUTETABLEFULL；｝Rowrowtoinsert（statementrowtoinsert）；serializerow（rowtoinsert，rowslot（table，tablenumrows））；tablenumrows1；returnEXECUTESUCCESS；｝查询语句执行ExecuteResultexecuteselect（Statementstatement，Tabletable）｛Rowrow；for（uint32ti0；itablenumrows；i）｛deserializerow（rowslot（table，i），row）；printrow（row）；｝returnEXECUTESUCCESS；｝ExecuteResultexecutestatement（Statementstatement，Tabletable）｛switch（statementtype）｛case（STATEMENTINSERT）：returnexecuteinsert（statement，table）；case（STATEMENTSELECT）：returnexecuteselect（statement，table）；｝｝Tablenewtable（）｛Tabletable（Table）malloc（sizeof（Table））；tablenumrows0；for（uint32ti0；iTABLEMAXPAGES；i）｛tablepages〔i〕NULL；｝returntable；｝voidfreetable（Tabletable）｛for（inti0；tablepages〔i〕；i）｛free（tablepages〔i〕）；｝free（table）；｝voidprintprompt（）｛printf（microdb）；｝intmain（intargc，charargv）｛InputBufferinputbuffernewinputbuffer（）；Tabletablenewtable（）；while（true）｛printprompt（）；readinput（inputbuffer）；if（inputbufferbuffer〔0〕。）｛switch（dometacommand（inputbuffer））｛case（METACOMMANDSUCCESS）：continue；case（METACOMMANDUNRECOGNIZEDCOMMAND）：printf（Unrecognizedcommands，inputbufferbuffer）；continue；｝｝else｛Statementstatement；switch（preparestatement（inputbuffer，statement））｛case（PREPARESUCCESS）：break；case（PREPARESTRINGTOOLONG）：printf（Stringistoolong。）；continue；case（PREPARENEGATIVEID）：printf（IDmustbepositive。）；continue；case（PREPARESYNTAXERROR）：printf（Syntaxerror。Couldnotparsestatement。）；continue；case（PREPAREUNRECOGNIZEDSTATEMENT）：printf（Unrecognizedkeywordatstartofs。，inputbufferbuffer）；continue；｝switch（executestatement（statement，table））｛caseEXECUTESUCCESS：printf（Executed。）；break；caseEXECUTETABLEFULL：printf（Error：Tablefull。）；break；｝｝｝return0；｝