作為一個(gè)天天都在CRUD的程序員，你有沒(méi)有想過(guò)，數(shù)據(jù)庫(kù)是如何工作的？
我猜，你曾經(jīng)無(wú)數(shù)次的翻開(kāi)講數(shù)據(jù)庫(kù)的書籍和文章，但總是看著看著就被勸退，太多的專業(yè)術(shù)語(yǔ)把人頭都搞大了。
等等，看這畫風(fēng)，今天是要賣課的節(jié)奏??！
NO！絕不賣課，請(qǐng)放心閱讀。
一直以來(lái)，我都很想深入學(xué)習(xí)一下數(shù)據(jù)庫(kù)。我這個(gè)人學(xué)東西，如果只知其然而不知其所以然是非常難受的，啥都想去了解下背后的原理，學(xué)編程語(yǔ)言是這樣，學(xué)操作系統(tǒng)也是這樣。數(shù)據(jù)庫(kù)這個(gè)東西天天都在用，所以學(xué)習(xí)一下背后的原理也是非常實(shí)用和有必要的。
但無(wú)論是哪本書、哪個(gè)視頻教程，一打開(kāi)就被無(wú)數(shù)的專業(yè)術(shù)語(yǔ)淹沒(méi)，太多概念淹沒(méi)了數(shù)據(jù)庫(kù)最本質(zhì)最核心的東西。
所以今天，讓我們從一個(gè)最最最簡(jiǎn)單的模型開(kāi)始，揭開(kāi)數(shù)據(jù)庫(kù)神秘的一角。
對(duì)我們使用者而言，數(shù)據(jù)庫(kù)就像是一個(gè)黑盒子，你可以往它里面寫入數(shù)據(jù)，也可以從它里面讀出數(shù)據(jù)。
讓我們暫時(shí)拋卻SQL、網(wǎng)絡(luò)連接、數(shù)據(jù)庫(kù)等等概念，就來(lái)看這個(gè)最基本的需求：如果我們來(lái)實(shí)現(xiàn)一個(gè)可以對(duì)外提供讀寫數(shù)據(jù)的黑盒子，該怎么做？
假設(shè)我們的黑盒子很簡(jiǎn)單，里面只有一張表：user_info，用來(lái)存儲(chǔ)用戶信息。
表里面也很簡(jiǎn)單，只有三個(gè)字段，分別記錄用戶的ID、姓名和手機(jī)號(hào)。
user_id(uint32)
name(char[8])
phone(char[20])
我們可以用一個(gè)簡(jiǎn)單的結(jié)構(gòu)體（或者一個(gè)class）來(lái)表示一條數(shù)據(jù)：
struct DataRecord{
uint32 user_id;
char name[8];
char phone[20];
};
user_id是一個(gè)uint32類型，占4個(gè)字節(jié)，name占8個(gè)字節(jié)，phone占20個(gè)字節(jié)，加起來(lái)一條數(shù)據(jù)總共占32個(gè)字節(jié)。
我們選擇用一個(gè)文件來(lái)存儲(chǔ)這些數(shù)據(jù)，存儲(chǔ)非常簡(jiǎn)單，只需要一條一條的碼在一起就行了，就像這樣：
數(shù)據(jù)存儲(chǔ)方式有了，接下來(lái)就是如何來(lái)讀寫了，我們來(lái)提供兩個(gè)函數(shù)，分別來(lái)插入（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);
}
插入很簡(jiǎn)單，直接打開(kāi)表對(duì)應(yīng)的數(shù)據(jù)文件，然后把文件指針移動(dòng)到文件尾部，接著追加數(shù)據(jù)，最后關(guān)閉文件，大功告成。這和把大象關(guān)進(jìn)冰箱的步驟是一樣一樣的。
接下來(lái)是查詢，我們提供一個(gè)可以通過(guò)id來(lái)查詢用戶的函數(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;
}
查詢也很簡(jiǎn)單，我們打開(kāi)文件，一條一條讀取數(shù)據(jù)，然后比較用戶id和給定的參數(shù)是否相同，直到找到符合條件的數(shù)據(jù)返回。
好了，以上，我們就實(shí)現(xiàn)了一個(gè)最最最基礎(chǔ)的黑盒子：它里面有一張表，然后可以往里面寫數(shù)據(jù)，從里面查數(shù)據(jù)。
現(xiàn)在來(lái)思考一下：
如果我們寫了很多數(shù)據(jù)進(jìn)去，比如幾十萬(wàn)條，我們要查一個(gè)指定id的數(shù)據(jù)，要按照這樣一條條比對(duì)，那不得等到猴年馬月去了？
為什么要一條條比對(duì)呢？是因?yàn)槲覀兊臄?shù)據(jù)全都是一條一條碼在一起的，完全沒(méi)有順序，所以要查詢，只能這樣一條條檢查——全表掃描。
如果我們的數(shù)據(jù)是有順序的呢？
假如我們插入數(shù)據(jù)的時(shí)候，是按照id從小到大排列著，這樣我們就能用二分法快速找到指定id的數(shù)據(jù)了。
看上面這張圖，假設(shè)我們要查找id為9的數(shù)據(jù)，我們可以讀取第一條數(shù)據(jù)的id是1，就知道id為9的數(shù)據(jù)肯定在它后面。然后再讀取最后一條數(shù)據(jù)id是12，就知道id為9的數(shù)據(jù)肯定在它前面，然后選擇中間的數(shù)據(jù)讀取，如此二分查找，很快就能鎖定目標(biāo)，不用每條數(shù)據(jù)都讀取了。
因?yàn)槊織l數(shù)據(jù)都是32個(gè)字節(jié)，所以可以非常方便定位任意一條數(shù)據(jù)的位置：第n條數(shù)據(jù)的位置在32*(n-1)偏移處。
通過(guò)改變數(shù)據(jù)的存儲(chǔ)組織形式，我們可以把數(shù)據(jù)查找的時(shí)間復(fù)雜度從O(N)下降到O(LogN)。
但如此一來(lái)，查找是變快了，但插入就麻煩了。以前的時(shí)候，我們直接把數(shù)據(jù)塞到文件最后就拍拍屁股走人了。但現(xiàn)在不行了，我們得把數(shù)據(jù)按照順序，插入到合適的位置。
最麻煩的是，我們的數(shù)據(jù)是一條一條挨個(gè)碼在一起的，如果中間某個(gè)位置要插入數(shù)據(jù)，就得把那個(gè)位置及其以后的數(shù)據(jù)通通往后移動(dòng)，這就涉及到大量的數(shù)據(jù)復(fù)制移動(dòng)，開(kāi)銷非常大。
要是每來(lái)一條insert操作就數(shù)據(jù)大量遷徙，那不得累得半死？
（其實(shí)不止插入，刪除數(shù)據(jù)delete也同樣如此麻煩）
就沒(méi)有一種辦法，可以同時(shí)插入快，查詢也快嗎？
仔細(xì)思考一下，前面我們把數(shù)據(jù)按順序一條一條碼在一起，查起來(lái)為什么快？
是因?yàn)樽隽伺判蛞院?，?shù)據(jù)的存儲(chǔ)位置有一條隱含的信息：如果id比我們要找的小，那我們要找的肯定在它后面；反之，如果id比我們要找的大，那我們要找的肯定在它前面。
之所以有這個(gè)規(guī)律，是因?yàn)槲覀儼磇d的大小進(jìn)行了排序存儲(chǔ)。
那如果現(xiàn)在回到最開(kāi)始的那種方式，不排序了，還是一條一條順序來(lái)寫入，就沒(méi)有這個(gè)信息了。
但如果，我們?cè)诿織l數(shù)據(jù)記錄中增加一些額外的信息，用來(lái)指示id比它小的在哪里，id比它大的又在哪里，是不是就能順著這些額外的信息“順藤摸瓜”找到你要找的數(shù)據(jù)呢？
或許，聰明的你已經(jīng)看出來(lái)了，這是按照“二叉樹”的形式在記錄數(shù)據(jù)位置信息。
但實(shí)際上，二叉樹也才兩個(gè)分叉，如果數(shù)據(jù)量很大的話，這棵樹就會(huì)很高很瘦。
而每一次走入一個(gè)分支，就對(duì)應(yīng)著一次文件I/O，所以在實(shí)際使用中，不會(huì)使用二叉樹，而是使用開(kāi)了非常多個(gè)叉的樹——B樹或者B+樹。
如果用B樹或者B+樹來(lái)將文件中的數(shù)據(jù)在邏輯上組織起來(lái)，要查找數(shù)據(jù)就會(huì)快得多。
用id來(lái)查找數(shù)據(jù)問(wèn)題解決了，但如果要用name來(lái)查找又該怎么辦呢？
想一想，如果另外有一個(gè)文件，記錄了每個(gè)name和這個(gè)name對(duì)應(yīng)的數(shù)據(jù)記錄在文件中的偏移位置，就像這樣：
user_id數(shù)據(jù)位置(偏移)xuanyuan0shuaidi31april63dibingfa95
有了這個(gè)東西，是不是就簡(jiǎn)單很多了？只需要在這里搜一遍，拿到數(shù)據(jù)的位置，然后打開(kāi)文件，定位到對(duì)應(yīng)的偏移，一下就讀出來(lái)了。
我們可以另外準(zhǔn)備一個(gè)文件，同樣使用B樹或者B+樹的形式來(lái)組織上面表格中的對(duì)應(yīng)關(guān)系。
聰明的你可能已經(jīng)看出來(lái)了，這玩意兒其實(shí)就是索引。當(dāng)然實(shí)際中的數(shù)據(jù)庫(kù)系統(tǒng)的索引實(shí)現(xiàn)或多或少有一些差別，但道理是通用的。
原文鏈接：
https://mp.weixin.qq.com/s/wUwJ4sPapE74AbOE2j5hMw
