让我们写一个简单的数据库

使用c语言从0开始实现一个类似sqlite的数据库

overview


我作为一个web开发人员,工作中每天都使用关系型数据库,但是,数据库对我来说就像一个黑盒子。有一些关于数据库的问题想问:

  • 存储进来的数据是什么格式的(内存中和硬盘上)
  • 什么时候把内存中的数据转移到硬盘上
  • 为什么一张表只能有一个主键
  • 回滚事务是如何实现的
  • 索引是什么样的
  • 全表扫描是怎么做的什么时候需要
  • 预处理语句是以什么格式存入的

或者说,一个数据库是如何工作的?

为了搞清楚这些,我要从0开始写一个数据库。 我准备以sqlite为原型,因为它是一个小型数据库,功能要比MySQL和PostgreSQL少,以便于我更好的理解。整个数据库是存在一个文件里的!

Sqlite

有很多关于sqlite内部实现的文章在他们的网站上,加上我有这篇文章的副本 SQLite Database System: Design and Implementation

sqlite architecture (https://www.sqlite.org/zipvfs/doc/trunk/www/howitworks.wiki)


为了获取或修改数据,一个请求,会依次经过上面的组件。 前端组件由以下组成:

  • 分词器(tokenizer)
  • 解析器 (parser)
  • 生成器 (code generator)

A tokenizer breaks a stream of text into tokens, usually by looking for whitespace (tabs, spaces, new lines).

A lexer is basically a tokenizer, but it usually attaches extra context to the tokens – this token is a number, that token is a string literal, this other token is an equality operator.

A parser takes the stream of tokens from the lexer and turns it into an abstract syntax tree representing the (usually) program represented by the original text.

Last I checked, the best book on the subject was “Compilers: Principles, Techniques, and Tools” usually just known as “The Dragon Book”.

https://stackoverflow.com/questions/380455/looking-for-a-clear-definition-of-what-a-tokenizer-parser-and-lexers-are

输入前端组件的是SQL请求。输出的是sqlite虚拟机机器码(简单说就是可以被数据库执行的编译程序)。

后端组件由以下组成:

  • 虚拟机(virtual machine)
  • B-树(B-tree)
  • 硬盘页管理器(pager)
  • 系统接口(os interface)

B树

虚拟机通过前端组件生成的字节码作为命令。这些命令可以操作存储在B-树中的索引或者表。虚拟机简单来说就像是字节命令的大的switch语句。

每个B-树由多个节点组成。每个节点是一个硬盘页的数据长度。B-树可以从硬盘获取一个页或者将一个页存储到硬盘,通过发布命令到硬盘页管理器。

硬盘页管理器接收到命令后,读或写一页数据。它的职责是读或者写合适的量到数据文件。它同时管理着在内存中的最近访问的页,以及这些页什么时候应该写回到硬盘中。

系统接口层在不同的系统中是不一样的。在这个教程中,将支持多系统。

千里之行始于足下,接下来让我们看一些更直观的东西:交互式解释器(repl).

做一个简单的交互式解释器

当你在命令行中打开sqlite的时候,sqlite就开始执行读取-执行-打印循环:

~ 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
~

为了实现它,我们的主函数需要有一个打印提示的无限循环,从输入获取一行命令,然后执行它: