我在Github上發(fā)現(xiàn)了一個好東西!
好久不見，軒轅終于更新了。
作為一個天天都在CRUD的程序員，你有沒有想過，數(shù)據(jù)庫是如何工作的？
我猜，你曾經無數(shù)次的翻開講數(shù)據(jù)庫的書籍和文章，但總是看著看著就被勸退，太多的專業(yè)術語把人頭都搞大了。
等等，看這畫風，今天是要賣課的節(jié)奏啊！
NO！絕不賣課，請放心閱讀。
一直以來，我都很想深入學習一下數(shù)據(jù)庫。我這個人學東西，如果只知其然而不知其所以然是非常難受的，啥都想去了解下背后的原理，學編程語言是這樣，學操作系統(tǒng)也是這樣。數(shù)據(jù)庫這個東西天天都在用，所以學習一下背后的原理也是非常實用和有必要的。
但無論是哪本書、哪個視頻教程，一打開就被無數(shù)的專業(yè)術語淹沒，太多概念淹沒了數(shù)據(jù)庫最本質最核心的東西。
所以今天，讓我們從一個最最最簡單的模型開始，揭開數(shù)據(jù)庫神秘的一角。
對我們使用者而言，數(shù)據(jù)庫就像是一個黑盒子，你可以往它里面寫入數(shù)據(jù)，也可以從它里面讀出數(shù)據(jù)。
讓我們暫時拋卻SQL、網(wǎng)絡連接、數(shù)據(jù)庫等等概念，就來看這個最基本的需求：如果我們來實現(xiàn)一個可以對外提供讀寫數(shù)據(jù)的黑盒子，該怎么做？
假設我們的黑盒子很簡單，里面只有一張表：
user_info
，用來存儲用戶信息。
表里面也很簡單，只有三個字段，分別記錄用戶的ID、姓名和手機號。
user_id(uint32)
name(char[8])
phone(char[20])
我們可以用一個簡單的結構體（或者一個class）來表示一條數(shù)據(jù)：
struct?DataRecord{
??uint32?user_id;
??char?name[8];
??char?phone[20];
};
user_id是一個uint32類型，占4個字節(jié)，name占8個字節(jié)，phone占20個字節(jié)，加起來一條數(shù)據(jù)總共占32個字節(jié)。
我們選擇用一個文件來存儲這些數(shù)據(jù)，存儲非常簡單，只需要一條一條的碼在一起就行了，就像這樣：
數(shù)據(jù)存儲方式有了，接下來就是如何來讀寫了，我們來提供兩個函數(shù)，分別來插入（insert）和查詢（select）數(shù)據(jù)：
//?偽代碼
void?insert(Table*?table,?DataRecord?record)?{
??fp?=?open(table->file_name);
??fseek(fp,?FILE_END);
??write(fp,?sizeof(DataRecord));
??close(fp);
}
插入很簡單，直接打開表對應的數(shù)據(jù)文件，然后把文件指針移動到文件尾部，接著追加數(shù)據(jù)，最后關閉文件，大功告成。這和把大象關進冰箱的步驟是一樣一樣的。
接下來是查詢，我們提供一個可以通過id來查詢用戶的函數(shù)：
//?偽代碼
DataRecord?select(uint32?user_id)?{
??DataRecord?result;
??fp?=?open(table->file_name);
??
??while?(1)?{
????if?(feof(fp))?
??????break;
??????
????DataRecord?record;
????read(fp,?&record,?sizeof(DataRecord));
????if?(record.user_id?==?user_id)?{
??????result?=?record;
??????break;
????}
??}
??
??close(fp);
??
??return?result;
}
查詢也很簡單，我們打開文件，一條一條讀取數(shù)據(jù)，然后比較用戶id和給定的參數(shù)是否相同，直到找到符合條件的數(shù)據(jù)返回。
好了，以上，我們就實現(xiàn)了一個最最最基礎的黑盒子：它里面有一張表，然后可以往里面寫數(shù)據(jù)，從里面查數(shù)據(jù)。
現(xiàn)在來思考一下：
如果我們寫了很多數(shù)據(jù)進去，比如幾十萬條，我們要查一個指定id的數(shù)據(jù)，要按照這樣一條條比對，那不得等到猴年馬月去了？
為什么要一條條比對呢？是因為我們的數(shù)據(jù)全都是一條一條碼在一起的，完全沒有順序，所以要查詢，只能這樣一條條檢查——全表掃描。
如果我們的數(shù)據(jù)是有順序的呢？
假如我們插入數(shù)據(jù)的時候，是按照id從小到大排列著，這樣我們就能用二分法快速找到指定id的數(shù)據(jù)了。
看上面這張圖，假設我們要查找id為9的數(shù)據(jù)，我們可以讀取第一條數(shù)據(jù)的id是1，就知道id為9的數(shù)據(jù)肯定在它后面。然后再讀取最后一條數(shù)據(jù)id是12，就知道id為9的數(shù)據(jù)肯定在它前面，然后選擇中間的數(shù)據(jù)讀取，如此二分查找，很快就能鎖定目標，不用每條數(shù)據(jù)都讀取了。
因為每條數(shù)據(jù)都是32個字節(jié)，所以可以非常方便定位任意一條數(shù)據(jù)的位置：第n條數(shù)據(jù)的位置在32*(n-1)偏移處。
通過改變數(shù)據(jù)的存儲組織形式，我們可以把數(shù)據(jù)查找的時間復雜度從O(N)下降到O(LogN)。
但如此一來，查找是變快了，但插入就麻煩了。以前的時候，我們直接把數(shù)據(jù)塞到文件最后就拍拍屁股走人了。但現(xiàn)在不行了，我們得把數(shù)據(jù)按照順序，插入到合適的位置。
最麻煩的是，我們的數(shù)據(jù)是一條一條挨個碼在一起的，如果中間某個位置要插入數(shù)據(jù)，就得把那個位置及其以后的數(shù)據(jù)通通往后移動，這就涉及到大量的數(shù)據(jù)復制移動，開銷非常大。
要是每來一條insert操作就數(shù)據(jù)大量遷徙，那不得累得半死？
（其實不止插入，刪除數(shù)據(jù)delete也同樣如此麻煩）
就沒有一種辦法，可以同時插入快，查詢也快嗎？
仔細思考一下，前面我們把數(shù)據(jù)按順序一條一條碼在一起，查起來為什么快？
是因為做了排序以后，數(shù)據(jù)的存儲位置有一條隱含的信息 ：如果id比我們要找的小，那我們要找的肯定在它后面；反之，如果id比我們要找的大，那我們要找的肯定在它前面。
之所以有這個規(guī)律，是因為我們按id的大小進行了排序存儲。
那如果現(xiàn)在回到最開始的那種方式，不排序了，還是一條一條順序來寫入，就沒有這個信息了。
但如果，我們在每條數(shù)據(jù)記錄中增加一些額外的信息，用來指示id比它小的在哪里，id比它大的又在哪里，是不是就能順著這些額外的信息“順藤摸瓜”找到你要找的數(shù)據(jù)呢？
或許，聰明的你已經看出來了，這是按照“二叉樹”的形式在記錄數(shù)據(jù)位置信息。
但實際上，二叉樹也才兩個分叉，如果數(shù)據(jù)量很大的話，這棵樹就會很高很瘦。
而每一次走入一個分支，就對應著一次文件I/O，所以在實際使用中，不會使用二叉樹，而是使用開了非常多個叉的樹——B樹或者B+樹。
如果用B樹或者B+樹來將文件中的數(shù)據(jù) 在邏輯上 組織起來，要查找數(shù)據(jù)就會快得多。
用id來查找數(shù)據(jù)問題解決了，但如果要用name來查找又該怎么辦呢？
想一想，如果另外有一個文件，記錄了每個name和這個name對應的數(shù)據(jù)記錄在文件中的偏移位置，就像這樣：
| user_id | 數(shù)據(jù)位置(偏移) |
|---|---|
| xuanyuan | 0 |
| shuaidi | 31 |
| april | 63 |
| dibingfa | 95 |
有了這個東西，是不是就簡單很多了？只需要在這里搜一遍，拿到數(shù)據(jù)的位置，然后打開文件，定位到對應的偏移，一下就讀出來了。
我們可以另外準備一個文件，同樣使用B樹或者B+樹的形式來組織上面表格中的對應關系。
聰明的你可能已經看出來了，這玩意兒其實就是索引。當然實際中的數(shù)據(jù)庫系統(tǒng)的索引實現(xiàn)或多或少有一些差別，但道理是通用的。
是不是已經開始有些迷糊了？
沒關系，這里軒轅推薦一個Github的開源項目，手把手教大家寫一個最簡單的數(shù)據(jù)庫出來。
https://cstack.github.io/db_tutorial/
整個項目總共分13個課時，從最簡單的內存數(shù)據(jù)庫、到寫磁盤持久化，從順序寫文件然后到B樹和B+樹的引入，完成一個完整的增刪改查的數(shù)據(jù)庫服務。
內容我看了，質量相當不錯，Github收獲了7.5K Star了，要說還是老外搞的開源項目給力啊。
我看很多朋友簡歷上的項目經歷，要么是XXX管理系統(tǒng)，要么是一個Web服務器，這些都太爛大街了，你要是寫上一個手寫一個數(shù)據(jù)庫系統(tǒng)，那絕對能讓面試官眼前一亮。
數(shù)據(jù)庫這塊，用文字來描寫感覺還是太過生澀了，軒轅打算后面用動畫的形式做成視頻放在B站，想看的同學點個贊吧，贊的越多，出的越快哦！
往期推薦