作为一个web从业者，我们每天都和关系型数据库打交道，但是对我们来说只是黑箱，因此我们就很想知道数据库是怎么样工作的？于是乎我就想弄明白数据库到底是怎么运作的，它的基本原理是什么？因此我决定从以下几个问题入手来弄明白数据库系统
- 数据库中的数据在内存或者磁盘中以什么格式保存？
- 什么时候数据从内存移动到磁盘中？(持久化)
- 为什么数据库的每个表有且只有一个主键？
- 数据库中事务的回滚是怎样工作的？
- 数据库中索引是怎样格式化的？
- 什么时候以及如何去扫描全表？
- 已准备好的语句以什么格式保存的？
换句话说，一个数据库是怎样工作的？ 需要指出的是，我在这里从头写了一个简单的mini数据库，模仿的是sqlite,因为它的设计相对于MySQL或者PostgreSQL来说更小，设计更加简单移动，容易理解明白，更加能上手模仿明白！我也能更好的理解数据库工作的原理。整个数据库我存放在单个文件中。
在它们的网站中有许多关于sqlite的实际实现的文章。 SQLite数据库系统: 设计与实现.
一个查询通过一系列组件能够检索或者修改数据。前端有以下部分组成
- 标记器(tokenizer)
- 解析器(parser)
- 代码生成器(code generator)
从前端输入一个sql查询，输出sqlite虚拟机字节码(本质上是一个可以对数据库进行操作的编译程序)。换句话说我们有一个控制台作为输入输出用，当一个sql查询在控制台被输入，然后控制台显示slqite虚拟机的字节码。 后端的组成如下
- 虚拟机(virtual machine)
- B-tree(b树)
- 页(pager)
- 操作系统接口(os interface)
虚拟机以前端生成的字节码为指令，接着它(字节码指令)能操作一个或者数据库表或者索引，这些数据库表或者索引存放在b-tree的数据结构中。VM本质上讲就是字节码指令类型的一个大的switch语句。
每个b-tree由多个节点组成。每个节点的长度为一页。B-tree能够检索一页从磁盘或者把他通过发送一个命令给pager存回到磁盘中去。
pager可以接受一些命令来读写pages的数据。它负责以适当的偏移量来读取/写入数据库文件。它也可以将最近访问的page缓存在内存中，并且能决定在什么时候这些在缓存中的page被写回到磁盘中。
在 os interface层面取决与在那个操作系统上编译sqlite，这本次课程中呢将不支持多个平台。
千里之行始于足下 ，所以让我们从更直接的开始：REPL
制作一个简单的REPL
sqlite从read-execute-print循环开始当你输入某些命令的时候
~ 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
~
为了做到上面的内容，我们的函数需要一个无限循环来打印标识符，获取一行数据，然后处理这行命令:
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);
}
}
}
我们需要将把InputBuffer 定义为一个小包装器，他包含了我们需要的状态，以便于与getline()交互（关于getline会在后续详细讲解）。
typedef struct {
char* buffer;
size_t buffer_length;
size_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;
}
接下来，我们需要定义一个print_prompt()函数，来打印标识符，并且在读取每一行之前都需要调用它
void print_prompt() { printf("db > "); }
读取输入的每一行数据，使用getline()函数
size_t getline(char **lineptr, size_t *n, FILE *stream);
lineptr:指向变量的指针，该变量用于指向包含读取行的缓冲区.如果设置为'NULL'则由getline()来分配，因此即使命令失败，该用户也会释放它。 n:用来保存分配buffer大小的变量的指针。 stream:读取输入流，我们会以标准输出。 return value:读取字节的大小，它可能小于buffer的大小。 我们将告诉getline()把读取一行的数据存放到input_buffer->buffer中，并且分配的buffer大小存到input_buffer->buffer_lenth。我们把返回值存到input_buffer->input_length中。 buffer开始是null,因此getline()分配足够的内存来保存输入并且使buffer指向输入。
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;
}
现在我们定义了一个适合的函数，来释放分配给InputBuffer *的内存和buffer中元素各自的结构。(在read_input()函数中getline()函数分配内存给input_buffer->buffer).
void close_input_buffer(InputBuffer* input_buffer){
free(input_buffer->buffer);
free(input_buffer);
}
最终我们将解析和执行命令.目前我们只有一个.exit命令能解析执行，该命令用来终止程序的。否则我们会打印一个错误信息并继续进行循环。
if (strcmp(input_buffer->buffer, ".exit") == 0) {
close_input_buffer(input_buffer);
exit(EXIT_SUCCESS);
} else {
printf("Unrecognized command '%s'.\n", input_buffer->buffer);
}
哇塞我们终于可以检验我们的成果了！！运行程序，我们首先输入.tables命令，会打印出Unrecognized command .tables(未能识别.tables命令)然后输入.exit。
~ ./db
db > .tables
Unrecognized command '.tables'.
db > .exit
~
好了，我们已经成功的完成了一个REPL，在下一个章节，我们开始开发我们的命令语言。同时，下面是我们本章节的代码:
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct {
char* buffer;
size_t buffer_length;
size_t input_length;
} InputBuffer;
InputBuffer* new_input_buffer() {
InputBuffer* input_buffer = malloc(sizeof(InputBuffer));
input_buffer->buffer = NULL;
input_buffer->buffer_length = 0;
input_buffer->input_length = 0;
return input_buffer;
}
void print_prompt() { printf("db > "); }
void read_input(InputBuffer* input_buffer) {
size_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;
}
void close_input_buffer(InputBuffer* input_buffer) {
free(input_buffer->buffer);
free(input_buffer);
}
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);
}
}
}
想要了解更多的后续文章，请关注我哦，微信公众号很简书昵称同名
