摘要：這個(gè)實(shí)際上給出了通過(guò)集合代數(shù)發(fā)展出來(lái)的關(guān)系型數(shù)據(jù)庫(kù)怎么進(jìn)行數(shù)據(jù)操作和檢索的。

本篇趟個(gè)雷，把數(shù)據(jù)庫(kù)納入到輪子中了，前面說(shuō)到了數(shù)據(jù)庫(kù)其實(shí)不算輪子，也說(shuō)到了其實(shí)我寫(xiě)不出來(lái)數(shù)據(jù)庫(kù)，這里所說(shuō)的數(shù)據(jù)庫(kù)嚴(yán)格來(lái)說(shuō)是關(guān)系型數(shù)據(jù)庫(kù)，他比輪子復(fù)雜多了，是一個(gè)和操作系統(tǒng)差不多復(fù)雜度的東西，所以才能通過(guò)一個(gè)oralce養(yǎng)活一家全球50強(qiáng)的公司，其次，數(shù)據(jù)庫(kù)太復(fù)雜了，要寫(xiě)出來(lái)實(shí)在是力所不能及，但是后來(lái)有想了一下，如果我們從另外一個(gè)角度來(lái)審視數(shù)據(jù)庫(kù)，那么也有比較容易的實(shí)現(xiàn)辦法，那么，這一篇，我們來(lái)造個(gè)數(shù)據(jù)庫(kù)吧，看吧，把關(guān)系型去掉了，因?yàn)?，有?b>關(guān)系型幾個(gè)字，數(shù)據(jù)庫(kù)就變得復(fù)雜多了。

關(guān)系型數(shù)據(jù)庫(kù)（Relational Database）是一個(gè)偉大的發(fā)明，一般的數(shù)據(jù)庫(kù)的理論，大概會(huì)分成以下三個(gè)部分。

首先，數(shù)據(jù)庫(kù)是建立在關(guān)系模型基礎(chǔ)上的，并且從理論上來(lái)講，是有完備的數(shù)學(xué)模型，也就是集合代數(shù)來(lái)做支撐的，他把我們真實(shí)世界中的聯(lián)系和實(shí)體抽象成了關(guān)系模型，并用這個(gè)發(fā)展出了數(shù)據(jù)庫(kù)理論，這是數(shù)據(jù)庫(kù)的理論基礎(chǔ)。

其次，也有人通過(guò)這個(gè)關(guān)系模型，發(fā)明了SQL這種進(jìn)行關(guān)系查詢的編程語(yǔ)言，用來(lái)對(duì)這個(gè)關(guān)系型的數(shù)據(jù)集合進(jìn)行操作。這個(gè)實(shí)際上給出了通過(guò)集合代數(shù)發(fā)展出來(lái)的關(guān)系型數(shù)據(jù)庫(kù)怎么進(jìn)行數(shù)據(jù)操作和檢索的。

還有人，發(fā)展出了數(shù)據(jù)庫(kù)設(shè)計(jì)的理論，也就是大家所熟悉的數(shù)據(jù)庫(kù)三大范式【應(yīng)該是5大范式】，用來(lái)教我們?cè)趯?shí)際場(chǎng)景中怎么設(shè)計(jì)一個(gè)數(shù)據(jù)庫(kù)，幾大范式實(shí)際上是把關(guān)系模型這個(gè)抽象的概念變成了幾條規(guī)則，按照這幾條規(guī)則去設(shè)計(jì)數(shù)據(jù)庫(kù)，就能產(chǎn)生最少的數(shù)據(jù)冗余，最能體現(xiàn)出關(guān)系這個(gè)模型的核心。

我們發(fā)現(xiàn)，上面三個(gè)大的部分都是數(shù)據(jù)庫(kù)的理論知識(shí)，其實(shí)并沒(méi)有人告訴我們?cè)趺磥?lái)用代碼實(shí)現(xiàn)一個(gè)數(shù)據(jù)庫(kù)，因?yàn)榭茖W(xué)家們認(rèn)為實(shí)現(xiàn)它并不重要，那是工程師要考慮的事情，Too Simple，科學(xué)家只負(fù)責(zé)搞出理論，反正我們也不是科學(xué)家，那么我們就來(lái)做做工程師吧。

既然是工程師，首先想到的就是如何來(lái)實(shí)現(xiàn)一個(gè)數(shù)據(jù)庫(kù)了，一個(gè)標(biāo)準(zhǔn)的數(shù)據(jù)庫(kù)大概主要會(huì)包含以下幾個(gè)大的模塊。

底層的存儲(chǔ)層，這個(gè)是必不可少的，他是整個(gè)數(shù)據(jù)庫(kù)的核心數(shù)據(jù)結(jié)構(gòu)，也就是數(shù)據(jù)是如何保存的，一般提供最簡(jiǎn)單的原子增刪改查。

存儲(chǔ)層上面就是引擎層了，這里會(huì)對(duì)底層的存儲(chǔ)層進(jìn)行各種組合型的操作用來(lái)滿足查詢的需求之類的，而且數(shù)據(jù)庫(kù)的事務(wù)支持也在這一層，我們熟悉的innoDB就是一個(gè)數(shù)據(jù)庫(kù)的存儲(chǔ)引擎，他其實(shí)包含的就是這個(gè)引擎層和存儲(chǔ)層了，引擎層提供對(duì)數(shù)據(jù)層的操作方法集合。

在引擎層之上還有個(gè)SQL的解析層，主要用來(lái)對(duì)SQL語(yǔ)句進(jìn)行解析，分析，優(yōu)化了，然后把SQL語(yǔ)句轉(zhuǎn)化成引擎層的接口，進(jìn)行具體的數(shù)據(jù)操作。

最上面就是對(duì)外的UI了，也就是用戶交互層了，一般我們熟悉的就是網(wǎng)絡(luò)交互了。

雖然看起來(lái)好像挺簡(jiǎn)單，就是這么三層，但是實(shí)際的數(shù)據(jù)庫(kù)是非常非常復(fù)雜的，除了這些以外還有很多其他模塊，比如用戶權(quán)限管理，緩存模塊，日志模塊，備份模塊等等等等，大家可以仔細(xì)去看看innoDB的書(shū)籍或者innoDB的代碼，光一個(gè)binlog就特別麻煩。

其實(shí)要保存數(shù)據(jù)，搜索系統(tǒng)也能保存數(shù)據(jù)，而且檢索起來(lái)更快，并且兩者的底層數(shù)據(jù)結(jié)構(gòu)其實(shí)差別不是很大，但為什么用數(shù)據(jù)庫(kù)呢？因?yàn)閿?shù)據(jù)庫(kù)的核心是可靠，這個(gè)可靠就是考數(shù)據(jù)庫(kù)的引擎層來(lái)保證的，完整的binlog記錄，崩潰后完整的重放機(jī)制，數(shù)據(jù)雙寫(xiě)，內(nèi)存數(shù)據(jù)定時(shí)刷新到磁盤，所有的這些都是為了保證數(shù)據(jù)的可靠，不會(huì)丟失數(shù)據(jù)。

而上面說(shuō)的每一個(gè)功能，都能多帶帶的寫(xiě)一篇長(zhǎng)文，所以說(shuō)要實(shí)現(xiàn)一個(gè)數(shù)據(jù)庫(kù)其實(shí)是很麻煩的，因?yàn)闉榱俗龅?b>可靠，必然會(huì)有很多冗余的數(shù)據(jù)或者冗余的操作來(lái)保證可靠，但作為一個(gè)成熟的產(chǎn)品，還需要考慮到產(chǎn)品的性能，所以，如何既可靠又性能優(yōu)良，就變成了一個(gè)衡量數(shù)據(jù)庫(kù)好壞的標(biāo)準(zhǔn)，當(dāng)然，在這兩點(diǎn)上，目前沒(méi)人能干過(guò)oracle了。

數(shù)據(jù)庫(kù)如此之復(fù)雜，我們?nèi)绾螌?duì)他進(jìn)行瘦身 ，來(lái)實(shí)現(xiàn)一個(gè)最小的數(shù)據(jù)庫(kù)系統(tǒng)呢？我們可以從另外一個(gè)角度想想，就是我們拿數(shù)據(jù)庫(kù)是干什么的？那就是存儲(chǔ)和查詢數(shù)據(jù)，如果這么來(lái)想的話，就能簡(jiǎn)單不少。

首先，我們知道數(shù)據(jù)庫(kù)最重要的功能就是存儲(chǔ)數(shù)據(jù)，那么底層的存儲(chǔ)部分是不能少的，其次，存儲(chǔ)的數(shù)據(jù)要提供查詢功能，不然存了就沒(méi)意義了，這也是不能少的，第三，需要提供一個(gè)對(duì)外的接口可以和用戶交互，不然就既不能存也不能查了。

所以，一個(gè)最最基本的數(shù)據(jù)庫(kù)至少應(yīng)該包含數(shù)據(jù)層，查詢層（引擎層）和UI（用戶接口）層三層，那么我們就用幾個(gè)簡(jiǎn)單的文件來(lái)實(shí)現(xiàn)這三層，完成一個(gè)最小的數(shù)據(jù)庫(kù)吧。

數(shù)據(jù)庫(kù)的基本單位是列，再上一級(jí)的基本單位就是表了，而且我們?cè)诮ū淼臅r(shí)候都會(huì)指定列的名稱，類型，長(zhǎng)度這三個(gè)最基本的屬性，如果所有列都有這三個(gè)屬性，那么其實(shí)我們是知道每一行數(shù)據(jù)最多有多少字節(jié)的，所以，我們可以設(shè)定沒(méi)一行數(shù)據(jù)的長(zhǎng)度都是定長(zhǎng)的，那么整個(gè)表的長(zhǎng)度也是定長(zhǎng)的了，這樣查詢的時(shí)候可以根據(jù)行的長(zhǎng)度進(jìn)行快速定位數(shù)據(jù)，所以，我們的最底層數(shù)據(jù)就是一個(gè)定長(zhǎng)的表格了，每一列存儲(chǔ)的時(shí)候就像下面這樣，然后有個(gè)meta信息來(lái)存儲(chǔ)列的屬性

這個(gè)看上去很簡(jiǎn)單吧？也容易實(shí)現(xiàn)吧，其實(shí)很多數(shù)據(jù)庫(kù)也基本上確實(shí)是這么實(shí)現(xiàn)的，并不難理解吧？稍微注意一下的是每一列存儲(chǔ)的時(shí)候，每個(gè)字段的前四個(gè)字節(jié)保存的是這個(gè)字段的實(shí)際長(zhǎng)度，然后才是字段的實(shí)際內(nèi)容，如果長(zhǎng)度小于建表時(shí)的設(shè)定長(zhǎng)度，那么有一部分空間是浪費(fèi)掉的，雖然是浪費(fèi)了，但還是值得的，因?yàn)榭梢宰尣樵兊臅r(shí)候省不少事。

這么下來(lái)，每行記錄就是一個(gè)定長(zhǎng)的，而一個(gè)數(shù)據(jù)庫(kù)的表就是一個(gè)二進(jìn)制文件了，但僅僅是這樣還是不夠的，因?yàn)檫@樣結(jié)構(gòu)，無(wú)論什么查詢都需要掃描全表，依次進(jìn)行判斷，而我們?cè)诮ū淼臅r(shí)候都會(huì)建立索引，為了建立索引，我們還得實(shí)現(xiàn)一個(gè)B+樹(shù)來(lái)存儲(chǔ)索引，而B+樹(shù)基本上是所有數(shù)據(jù)庫(kù)的索引保存的數(shù)據(jù)結(jié)構(gòu)，這里我們也有實(shí)現(xiàn)，如果對(duì)B+樹(shù)感興趣，可以看我之前的一篇文章，那篇有詳細(xì)的B+樹(shù)的實(shí)現(xiàn)方式，文章后有那篇文章的鏈接。

總之，數(shù)據(jù)底層我們就用了一個(gè)定長(zhǎng)的二進(jìn)制文件和幾棵B+樹(shù)，再加上一個(gè)meta信息文件來(lái)實(shí)現(xiàn)了一個(gè)數(shù)據(jù)庫(kù)的底層數(shù)據(jù)層，很簡(jiǎn)單哈，但基本上包括了數(shù)據(jù)庫(kù)真實(shí)的底層，雖然真正的數(shù)據(jù)庫(kù)比這復(fù)雜多了，但也跑不掉這幾個(gè)數(shù)據(jù)結(jié)構(gòu)，整個(gè)看下來(lái)，數(shù)據(jù)層的數(shù)據(jù)結(jié)構(gòu)大體上長(zhǎng)這樣子。

當(dāng)然，數(shù)據(jù)層實(shí)現(xiàn)完了以后，還需要對(duì)上提供幾個(gè)簡(jiǎn)單的接口，比如

建表接口 CreateTable( []FieldInfo )，參數(shù)是每個(gè)字段的信息，包括字段的名稱，長(zhǎng)度，類型

數(shù)據(jù)插入接口 AddData(map[string]string) ，參數(shù)是一個(gè)map，key是字段名稱，value是字段內(nèi)容

單字段查詢接口 Find(fieldname,fieldvalue,op)，參數(shù)是字段名稱，字段值，操作類型（大于，小于，等于）

數(shù)據(jù)獲取接口 GetData(docid)，參數(shù)是docid，用來(lái)計(jì)算在文件中的偏移

底層已經(jīng)有了，接下來(lái)就是上面的查詢層（引擎層）了，這里我沒(méi)用引擎兩個(gè)字，是因?yàn)樽钚?shù)據(jù)庫(kù)的實(shí)現(xiàn)上，實(shí)在算不上一個(gè)引擎系統(tǒng)，我們實(shí)現(xiàn)最簡(jiǎn)單的基本查詢SQL（建表sql，插入數(shù)據(jù)sql，單表查詢sql）的解析，在實(shí)際中，SQL的解析是一個(gè)異常復(fù)雜的工程，涉及到語(yǔ)法分析，預(yù)處理，優(yōu)化查詢等幾個(gè)大的部分，因?yàn)镾QL其實(shí)是一門編程語(yǔ)言，要解析一門編程語(yǔ)言，那么編譯原理那一套基本上都會(huì)用得到。

這里我們換條路子，因?yàn)橹粚?shí)現(xiàn)三種簡(jiǎn)單的SQL語(yǔ)句，那么我們直接用正則和字符串的匹配來(lái)對(duì)SQL進(jìn)行解析，解析完成以后變成一個(gè)個(gè)數(shù)據(jù)層的對(duì)外接口，建表和插入數(shù)據(jù)都比較簡(jiǎn)單，解析了SQL以后直接調(diào)用上面的第一和第二接口就行了。

數(shù)據(jù)查詢的時(shí)候，對(duì)查詢SQL的WHERE之后的部分，用了個(gè)小算法，就是逆波蘭表達(dá)式來(lái)對(duì)WHERE之后的語(yǔ)句進(jìn)行解析，變成一個(gè)棧結(jié)構(gòu)來(lái)存儲(chǔ)查詢的內(nèi)容，然后通過(guò)彈棧的方式一個(gè)一個(gè)調(diào)用接口三，并且對(duì)結(jié)果進(jìn)行求交和求并的操作，最后得到結(jié)果以后，再依次調(diào)用接口四獲取最后的結(jié)果，如果對(duì)逆波蘭表達(dá)式不了解，那么請(qǐng)自行百度一下，很簡(jiǎn)單的，主要用在對(duì)四則運(yùn)算的優(yōu)先級(jí)的解析中。

查詢層的輸入輸出很簡(jiǎn)單，他對(duì)外實(shí)際上只提供一個(gè)接口。ExecSqlSentence( Sql ) string，都是字符串，輸入是一條條的sql語(yǔ)句，輸出是數(shù)據(jù)。

對(duì)于用戶的接口層就更加簡(jiǎn)單了，我們只需要提供一個(gè)TCP服務(wù)就行了，用;分號(hào)來(lái)分割每次用戶的輸入，也就是說(shuō)，我們telnet上我們這個(gè)數(shù)據(jù)庫(kù)，然后輸入sql，數(shù)據(jù)庫(kù)就會(huì)返回?cái)?shù)據(jù)了。

我在github上建立了一個(gè)新的工程叫SparrowSys，麻雀工程，意思很明顯，這是一個(gè)后端的麻雀，是最簡(jiǎn)單的后端輪子，目前我也已經(jīng)提交了一部分代碼，數(shù)據(jù)庫(kù)的還沒(méi)有寫(xiě)完，后面會(huì)補(bǔ)上的。

數(shù)據(jù)庫(kù)的部分在src下的SparrowDB里面，很明顯的看到里面有DataLayer,EngineLayer,NetLayer，對(duì)應(yīng)的就是上面的三層，每層里面有一到兩個(gè)文件，都很簡(jiǎn)單，目前DataLayer基本完成了，后面會(huì)把EngineLayer和NetLayer補(bǔ)上，后面的文章會(huì)說(shuō)說(shuō)使用，utils文件夾中是一些公共的東西，后面的其他輪子會(huì)用到的，比如B+樹(shù)就在utils里面。

目前這個(gè)工程里面東西不多，不建議看，后面我補(bǔ)全以后會(huì)說(shuō)明，歡迎大家提交你的實(shí)現(xiàn)來(lái)代替我的。接受任何pull request。

十天沒(méi)有更新了，主要是代碼沒(méi)時(shí)間寫(xiě)，所以沒(méi)有測(cè)試結(jié)果可看，本來(lái)準(zhǔn)備等代碼都寫(xiě)完了再來(lái)更新文章，但最近實(shí)在是太忙了，沒(méi)時(shí)間寫(xiě)代碼，那先放出文章，等代碼補(bǔ)充完整了再說(shuō)說(shuō)測(cè)試效果吧。

代碼地址：https://github.com/wyh267/SparrowSys

B+樹(shù)文章

如果你覺(jué)得不錯(cuò)，歡迎轉(zhuǎn)發(fā)給更多人看到，也歡迎關(guān)注我的公眾號(hào)，主要聊聊搜索，推薦，廣告技術(shù)，還有瞎扯。。文章會(huì)在這里首先發(fā)出來(lái)：）掃描或者搜索微信號(hào)XJJ267或者搜索西加加語(yǔ)言就行