作为一个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);
    }
  }
}