摘要：這個實際上給出了通過集合代數發展出來的關系型數據庫怎么進行數據操作和檢索的。

本篇趟個雷，把數據庫納入到輪子中了，前面說到了數據庫其實不算輪子，也說到了其實我寫不出來數據庫，這里所說的數據庫嚴格來說是關系型數據庫，他比輪子復雜多了，是一個和操作系統差不多復雜度的東西，所以才能通過一個oralce養活一家全球50強的公司，其次，數據庫太復雜了，要寫出來實在是力所不能及，但是后來有想了一下，如果我們從另外一個角度來審視數據庫，那么也有比較容易的實現辦法，那么，這一篇，我們來造個數據庫吧，看吧，把關系型去掉了，因為，有了關系型幾個字，數據庫就變得復雜多了。

關系型數據庫（Relational Database）是一個偉大的發明，一般的數據庫的理論，大概會分成以下三個部分。

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

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

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

我們發現，上面三個大的部分都是數據庫的理論知識，其實并沒有人告訴我們怎么來用代碼實現一個數據庫，因為科學家們認為實現它并不重要，那是工程師要考慮的事情，Too Simple，科學家只負責搞出理論，反正我們也不是科學家，那么我們就來做做工程師吧。

既然是工程師，首先想到的就是如何來實現一個數據庫了，一個標準的數據庫大概主要會包含以下幾個大的模塊。

底層的存儲層，這個是必不可少的，他是整個數據庫的核心數據結構，也就是數據是如何保存的，一般提供最簡單的原子增刪改查。

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

在引擎層之上還有個SQL的解析層，主要用來對SQL語句進行解析，分析，優化了，然后把SQL語句轉化成引擎層的接口，進行具體的數據操作。

最上面就是對外的UI了，也就是用戶交互層了，一般我們熟悉的就是網絡交互了。

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

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

而上面說的每一個功能，都能多帶帶的寫一篇長文，所以說要實現一個數據庫其實是很麻煩的，因為為了做到可靠，必然會有很多冗余的數據或者冗余的操作來保證可靠，但作為一個成熟的產品，還需要考慮到產品的性能，所以，如何既可靠又性能優良，就變成了一個衡量數據庫好壞的標準，當然，在這兩點上，目前沒人能干過oracle了。

數據庫如此之復雜，我們如何對他進行瘦身 ，來實現一個最小的數據庫系統呢？我們可以從另外一個角度想想，就是我們拿數據庫是干什么的？那就是存儲和查詢數據，如果這么來想的話，就能簡單不少。

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

所以，一個最最基本的數據庫至少應該包含數據層，查詢層（引擎層）和UI（用戶接口）層三層，那么我們就用幾個簡單的文件來實現這三層，完成一個最小的數據庫吧。

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

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

這么下來，每行記錄就是一個定長的，而一個數據庫的表就是一個二進制文件了，但僅僅是這樣還是不夠的，因為這樣結構，無論什么查詢都需要掃描全表，依次進行判斷，而我們在建表的時候都會建立索引，為了建立索引，我們還得實現一個B+樹來存儲索引，而B+樹基本上是所有數據庫的索引保存的數據結構，這里我們也有實現，如果對B+樹感興趣，可以看我之前的一篇文章，那篇有詳細的B+樹的實現方式，文章后有那篇文章的鏈接。

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

當然，數據層實現完了以后，還需要對上提供幾個簡單的接口，比如

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

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

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

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

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

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

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

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

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

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

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

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

十天沒有更新了，主要是代碼沒時間寫，所以沒有測試結果可看，本來準備等代碼都寫完了再來更新文章，但最近實在是太忙了，沒時間寫代碼，那先放出文章，等代碼補充完整了再說說測試效果吧。

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

B+樹文章

如果你覺得不錯，歡迎轉發給更多人看到，也歡迎關注我的公眾號，主要聊聊搜索，推薦，廣告技術，還有瞎扯。。文章會在這里首先發出來：）掃描或者搜索微信號XJJ267或者搜索西加加語言就行