干貨：聽“小碼哥”教你如何從0開始打造一個最小系統(tǒng)的數(shù)據(jù)庫

數(shù)據(jù)庫數(shù)據(jù)分析編程語言大數(shù)據(jù)

小碼哥 | 2016-08-04 14:54

【數(shù)據(jù)猿導(dǎo)讀】本篇趟個雷，把數(shù)據(jù)庫納入到輪子中，在我看來，數(shù)據(jù)庫比輪子復(fù)雜多了，是一個和操作系統(tǒng)差不多復(fù)雜度的東西，所以才能通過一個Oracle養(yǎng)活一家全球50強的公司。本文為后端輪子系列的第一篇，我們先來談?wù)勅绾卧靷€數(shù)據(jù)庫吧

干貨：聽“小碼哥”教你如何從0開始打造一個最小系統(tǒng)的數(shù)據(jù)庫

先來聊聊關(guān)系型數(shù)據(jù)庫

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

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

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

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

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

工程師眼中的數(shù)據(jù)庫系統(tǒng)

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

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

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

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

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

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

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

而上面說的每一個功能，都能單獨的寫一篇長文，所以說要實現(xiàn)一個數(shù)據(jù)庫其實是很麻煩的，因為為了做到可靠，必然會有很多冗余的數(shù)據(jù)或者冗余的操作來保證可靠，但作為一個成熟的產(chǎn)品，還需要考慮到產(chǎn)品的性能，所以，如何既可靠又性能優(yōu)良，就變成了一個衡量數(shù)據(jù)庫好壞的標(biāo)準(zhǔn)，當(dāng)然，在這兩點上，目前沒人能干過Oracle了。

最小系統(tǒng)的數(shù)據(jù)庫

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

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

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

存儲層

數(shù)據(jù)庫的基本單位是列，再上一級的基本單位就是表了，而且我們在建表的時候都會指定列的名稱、類型、長度這三個最基本的屬性，如果所有列都有這三個屬性，那么其實我們是知道每一行數(shù)據(jù)最多有多少字節(jié)的。所以，我們可以設(shè)定沒一行數(shù)據(jù)的長度都是定長的，那么整個表的長度也是定長的了，這樣查詢的時候可以根據(jù)行的長度進行快速定位數(shù)據(jù)，所以，我們的最底層數(shù)據(jù)就是一個定長的表格了，每一列存儲的時候就像下面這樣，然后有個meta信息來存儲列的屬性：

這個看上去很簡單吧?也容易實現(xiàn)吧，其實很多數(shù)據(jù)庫也基本上確實是這么實現(xiàn)的，并不難理解吧?稍微注意一下的是每一列存儲的時候，每個字段的前四個字節(jié)保存的是這個字段的實際長度，然后才是字段的實際內(nèi)容，如果長度小于建表時的設(shè)定長度，那么有一部分空間是浪費掉的，雖然是浪費了，但還是值得的，因為可以讓查詢的時候省不少事。

這么下來，每行記錄就是一個定長的，而一個數(shù)據(jù)庫的表就是一個二進制文件了，但僅僅是這樣還是不夠的，因為這樣結(jié)構(gòu)，無論什么查詢都需要掃描全表，依次進行判斷，而我們在建表的時候都會建立索引，為了建立索引，我們還得實現(xiàn)一個 B+樹來存儲索引，而B+樹基本上是所有數(shù)據(jù)庫的索引保存的數(shù)據(jù)結(jié)構(gòu)，這里我們也有實現(xiàn)。

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

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

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

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

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

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

查詢層

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

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

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

查詢層的輸入輸出很簡單，他對外實際上只提供一個接口。 ExecSqlSentence( Sql ) string ，都是字符串，輸入是一條條的SQL語句，輸出是數(shù)據(jù)。

UI層(用戶接口層)

對于用戶的接口層就更加簡單了，我們只需要提供一個TCP服務(wù)就行了，用分號來分割每次用戶的輸入，也就是說，我們telnet上我們這個數(shù)據(jù)庫，然后輸入SQL，數(shù)據(jù)庫就會返回數(shù)據(jù)了。

具體實現(xiàn)

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

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

目前這個工程里面東西不多，不建議看，后面我補全以后會說明，歡迎大家提交你的實現(xiàn)來代替我的。接受任何pull request。

最近比較忙，沒時間寫代碼，先放出文章，等代碼補充完整了再說說測試效果。點擊后面網(wǎng)址，可跳到github代碼庫。https://github.com/wyh267/SparrowSys

來源：運維派

收藏分享

聲明：數(shù)據(jù)猿尊重媒體行業(yè)規(guī)范，相關(guān)內(nèi)容都會注明來源與作者；轉(zhuǎn)載我們原創(chuàng)內(nèi)容時，也請務(wù)必注明“來源：數(shù)據(jù)猿”與作者名稱，否則將會受到數(shù)據(jù)猿追責(zé)。