建站
咨詢
售后
建站咨詢
新聞中心
“What I cannot create, I do not understand.” – Richard Feynman
創(chuàng)新互聯(lián)建站主要從事網(wǎng)站建設(shè)、網(wǎng)站設(shè)計(jì)、網(wǎng)頁(yè)設(shè)計(jì)、企業(yè)做網(wǎng)站、公司建網(wǎng)站等業(yè)務(wù)。立足成都服務(wù)柞水,10多年網(wǎng)站建設(shè)經(jīng)驗(yàn),價(jià)格優(yōu)惠、服務(wù)專業(yè),歡迎來(lái)電咨詢建站服務(wù):18982081108
I’m building a clone of sqlite from scratch in C in order to understand, and I’m going to document my process as I go.
譯注：cstsck在github維護(hù)了一個(gè)簡(jiǎn)單的、類似SQLite的數(shù)據(jù)庫(kù)實(shí)現(xiàn)，通過(guò)這個(gè)簡(jiǎn)單的項(xiàng)目，可以很好的理解數(shù)據(jù)庫(kù)是如何運(yùn)行的，原文標(biāo)題：Let's Build a Simple Database，本文是第一篇。
Part 1 介紹&設(shè)置REPL
作為一名開(kāi)發(fā)人員，在工作中我每天都使用關(guān)系型數(shù)據(jù)庫(kù)。但是對(duì)我來(lái)說(shuō)，它們是一個(gè)黑盒。我有一些問(wèn)題：
- 數(shù)據(jù)存儲(chǔ)使用什么格式？（在內(nèi)存與磁盤中）
- 數(shù)據(jù)什么時(shí)候從內(nèi)存轉(zhuǎn)移到磁盤？
- 為什么每張表只能有一個(gè)主鍵？
- 事務(wù)回滾是怎么工作的？
- 索引是什么格式的？
- 全表掃描時(shí)什么時(shí)候發(fā)生，如何發(fā)生的？
預(yù)處理語(yǔ)句（prepared statement）是使用什么格式存儲(chǔ)的？
換句話說(shuō)，數(shù)據(jù)庫(kù)是怎么工作的？
為了弄清楚這些，我從頭寫了一個(gè)數(shù)據(jù)庫(kù)。它是模仿SQLite實(shí)現(xiàn)的，因?yàn)镾QLite設(shè)計(jì)小巧，并且相比于MySQL和PostgreSQL，它的功能相對(duì)要少很多，所以我希望能更容易的理解它。在實(shí)現(xiàn)上，整個(gè)數(shù)據(jù)庫(kù)都存儲(chǔ)在一個(gè)數(shù)據(jù)文件中。
SQLite
在SQLite的網(wǎng)站上，有很多SQLite的內(nèi)部文檔（https://www.sqlite.org/arch.html）。另外我還拷貝了文檔（SQLite Database System: Design and Implementation.）的一個(gè)副本（https://play.google.com/store/books/details?id=9Z6IQQnX1JEC）
SQLite architecture
(https://www.sqlite.org/zipvfs/doc/trunk/www/howitworks.wiki)
一個(gè)查詢通過(guò)組件鏈來(lái)獲取數(shù)據(jù)或者修改數(shù)據(jù)。前端如下組件：
- 分詞器(tokenizer)
- 解析器（parser）
- 代碼生成器（code generator）
前端的輸入是SQL語(yǔ)句。輸出則是SQLite的虛擬機(jī)字節(jié)碼（virtual machine bytecode），本質(zhì)上是一個(gè)可以在數(shù)據(jù)庫(kù)運(yùn)行的編譯程序。
譯注：數(shù)據(jù)庫(kù)實(shí)現(xiàn)查詢優(yōu)化模型分為傳統(tǒng)的火山模型（Volcano model）與Code gen模型，本文作者實(shí)現(xiàn)的是code gen模型。
后端包括如下組件：
- 虛擬機(jī)（virtual machine）
- B-tree
- 頁(yè)管理（pager）
- 系統(tǒng)接口（os interface）
virtual machine
虛擬機(jī)將前端生成的字節(jié)碼作為指令。它接下來(lái)可以在一個(gè)或更多的表、索引上執(zhí)行操作，表以及索引都是存儲(chǔ)在叫B-tree的數(shù)據(jù)結(jié)構(gòu)中。VM 本質(zhì)上是字節(jié)碼指令類型的一個(gè)大開(kāi)關(guān)語(yǔ)句（a big switch statement on the type of bytecode instruction）
B-tree
每個(gè)B-tree有許多節(jié)點(diǎn)。每個(gè)節(jié)點(diǎn)是一個(gè)page的長(zhǎng)度。B-tree可以通過(guò)執(zhí)行命令到pager，從磁盤獲取一個(gè)page或者保存回page到磁盤。
pager
pager接收命令來(lái)讀取或者寫入數(shù)據(jù)的pages。它是負(fù)責(zé)來(lái)讀、寫數(shù)據(jù)庫(kù)文件的適當(dāng)偏移位置。也負(fù)責(zé)保持當(dāng)前訪問(wèn)的pages在內(nèi)存中，并且決定何時(shí)這些pages需要寫回磁盤。
os interface
系統(tǒng)接口與SQLite根據(jù)不同操作系統(tǒng)平臺(tái)來(lái)編譯不同，在這個(gè)系列教程中，我不準(zhǔn)備去支持多平臺(tái)適配。
千里之行始于足下，所以我們從一些簡(jiǎn)單的事開(kāi)始：REPL
實(shí)現(xiàn)簡(jiǎn)單的REPL
譯注：REPL，Read - Execute - Print - Loop，即讀取 - 執(zhí)行 - 打印輸出 - 循環(huán)，這個(gè)過(guò)程。有時(shí)候翻譯成交互式解釋器
當(dāng)你執(zhí)行命令行命令時(shí)，SQLite開(kāi)始讀取-執(zhí)行-打印循環(huán)：
sqlite3
SQLite version 3.16.0 2016-11-04 19:09:39
Enter ".help" for usage hints.
Connected to a transient in-memory database.
Use ".open FILENAME" to reopen on a persistent database.
sqlite> create table users (id int, username varchar(255), email varchar(255));
sqlite> .tables
users
sqlite> .exit
為了實(shí)現(xiàn)這樣的效果，我們的主程序需要有一個(gè)無(wú)限循環(huán)來(lái)打印這個(gè)提示，獲取一行輸入，然后處理這行輸入：
int main(int argc, char* argv[]) {
InputBuffer* input_buffer = new_input_buffer();
while (true) {
print_prompt();
read_input(input_buffer);
if (strcmp(input_buffer->buffer, ".exit") == 0) {
close_input_buffer(input_buffer);
exit(EXIT_SUCCESS);
} else {
printf("Unrecognized command '%s'.\n", input_buffer->buffer);
}
}
}我們定義一個(gè)InputBuffer來(lái)作為一個(gè)封裝，封裝圍繞在我們需要存儲(chǔ)的、與getline()函數(shù)交互的狀態(tài)（稍后將對(duì)此進(jìn)行詳細(xì)介紹）
typedef struct {
char* buffer;
size_t buffer_length;
ssize_t input_length;
} InputBuffer;
InputBuffer* new_input_buffer() {
InputBuffer* input_buffer = (InputBuffer*)malloc(sizeof(InputBuffer));
input_buffer->buffer = NULL;
input_buffer->buffer_length = 0;
input_buffer->input_length = 0;
return input_buffer;
}接下來(lái)，print_prompt()函數(shù)為用戶打印出提示。在做這個(gè)之前需要讀取每一行輸入。
void print_prompt() { printf("db > "); }讀取命令行輸入，需要使用getline()函數(shù):
ssize_t getline(char **lineptr, size_t *n, FILE *stream);
（以下為getline的函數(shù)釋義）
lineptr：
一個(gè)指針指向我們?cè)赽uffer中包含的，從命令行讀取的命令的變量。如果設(shè)置為NULL，它由getline()函數(shù)分配內(nèi)存。并且后續(xù)由用戶來(lái)釋放，即使命令行的命令執(zhí)行失敗也能保證會(huì)被釋放已分配的內(nèi)存。
n：
一個(gè)指針變量，指向已經(jīng)分配內(nèi)存的buffer的大小（size）。
stream：
讀取的輸入流，這里是從標(biāo)準(zhǔn)輸入讀取的。
return value（返回值，ssize_t類型）:
讀取的字節(jié)數(shù)量，可能會(huì)比buffer的size小。
我們告訴getline()函數(shù)保存讀取的命令行到input_buffer->buffer，存儲(chǔ)buffer的size到input_buffer->buffer_length，保存返回值到input_buffer->input_length
buffer在初始時(shí)是NULL，所以getline()函數(shù)分配足夠的內(nèi)存來(lái)存輸入的命令行數(shù)據(jù)然后讓buffer來(lái)指向這些數(shù)據(jù)。
void read_input(InputBuffer* input_buffer) {
ssize_t bytes_read =
getline(&(input_buffer->buffer), &(input_buffer->buffer_length), stdin);
if (bytes_read <= 0) {
printf("Error reading input\n");
exit(EXIT_FAILURE);
}
// Ignore trailing newline
input_buffer->input_length = bytes_read - 1;
input_buffer->buffer[bytes_read - 1] = 0;
}現(xiàn)在就可以定義一個(gè)函數(shù)來(lái)釋放已分配給InputBuffer實(shí)例和buffer中元素各自的數(shù)據(jù)結(jié)構(gòu)的內(nèi)存了（在read_input()函數(shù)中，調(diào)用getline()函數(shù)為input_buffer->buffer分配內(nèi)存）。
void close_input_buffer(InputBuffer* input_buffer) {
free(input_buffer->buffer);
free(input_buffer);
}在最后，我們解析并執(zhí)行命令?，F(xiàn)在這只是僅有的一個(gè)認(rèn)可的命令：.exit，一個(gè)終止程序的命令。除此之外的命令，我們打印一個(gè)報(bào)錯(cuò)信息然后繼續(xù)程序的循環(huán)。
if (strcmp(input_buffer->buffer, ".exit") == 0) {
close_input_buffer(input_buffer);
exit(EXIT_SUCCESS);
} else {
printf("Unrecognized command '%s'.\n", input_buffer->buffer);
}讓我們來(lái)試試吧！
~ ./db
db > .tables
Unrecognized command '.tables'.
db > .exit
~
好了，我們得到了一個(gè)可以工作的REPL。在下一部分，我們將開(kāi)始開(kāi)發(fā)我們的命令語(yǔ)言。同時(shí)，下面是是這部分的全部程序代碼：
1 #include
2 #include
3 #include
4 #include
5
6 typedef struct {
7 char* buffer;
8 size_t buffer_length;
9 ssize_t input_length;
10 } InputBuffer;
11
12 InputBuffer* new_input_buffer() {
13 InputBuffer* input_buffer = malloc(sizeof(InputBuffer));
14 input_buffer->buffer = NULL;
15 input_buffer->buffer_length = 0;
16 input_buffer->input_length = 0;
17
18 return input_buffer;
19 }
20
21 void print_prompt() { printf("db > "); }
22
23 void read_input(InputBuffer* input_buffer) {
24 ssize_t bytes_read =
25
26 getline(&(input_buffer->buffer), &(input_buffer->buffer_length), stdi n);
27
28 if (bytes_read <= 0) {
29 printf("Error reading input\n");
30 exit(EXIT_FAILURE);
31 }
32
33 // Ignore trailing newline
34 input_buffer->input_length = bytes_read - 1;
35 input_buffer->buffer[bytes_read - 1] = 0;
36 }
37
38 void close_input_buffer(InputBuffer* input_buffer) {
39 free(input_buffer->buffer);
40 free(input_buffer);
41 }
42
43 int main(int argc, char* argv[]) {
44 InputBuffer* input_buffer = new_input_buffer();
45 while (true) {
46 print_prompt();
47 read_input(input_buffer);
48
49 if (strcmp(input_buffer->buffer, ".exit") == 0) {
50 close_input_buffer(input_buffer);
51 exit(EXIT_SUCCESS);
52 } else {
53 printf("Unrecognized command '%s'.\n", input_buffer->buffer);
54 }
55 }
56 }
網(wǎng)頁(yè)名稱：實(shí)現(xiàn)一個(gè)簡(jiǎn)單的Database1，你會(huì)了嗎？
網(wǎng)站地址：http://www.fisionsoft.com.cn/article/djjgsgs.html
