如何教你从0到1实现一个简单的数据库系统(一)
作为一个web从业者,我们每天都和关系型数据库打交道,但是对我们来说只是黑箱,因此我们就很想知道数据库是怎么样工作的?于是乎我就想弄明白数据库到底是怎么运作的,它的基本原理是什么?因此我决定从以下几个问题入手来弄明白数据库系统数据库中的数据在内存或者磁盘中以什么格式保存?什么时候数据从内存移动到磁盘中?(持久化)为什么数据库的每个表有且只有一个主键?数据库中事务的回滚是怎样工作的?数据库中索引是怎
作为一个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);
}
}
}
更多推荐
所有评论(0)