SQL数据库揭秘

英文原文

SQLite

本文里，我们将会通过SQLite的一个早期版本来讨论一下数据库实现的一些架构细节

简介

    数据库是软件系统里很重要的一个组成部分，它主要用来高效地存储和读取数据。本文里，我们将会通过SQLite的一个早期版本来讨论一下数据库实现的一些架构细节。

    SQLite是一个小型数据库软件，但是它被广泛地用在成千上万的软件系统和硬件设备里。它是在2000年8月份被D.Richard Hipp发明的。SQLite是一个高性能的，轻量级的关系型数据库系统。如果你想在代码层面学习数据库的内部实现的话，SQLite是众多开源数据库里最好的选择，它的文档很多，而且代码的可读性非常高。但是，如果去阅读最新版本的SQLite的代码的话，就显得比较困难了，因为它包含了很多新的特性。另外，为了便于理解数据库的实现原理，你需要熟悉数据结构，了解计算原理以及操作系统原理。

    在这里，我们会使用SQLite 2.5.0版本。你可以在GitHub上找到SQLite的一个简单实现。另外，这个代码仓库里有SQLite 2.5.0版本的代码，可以拿来参考。

为什么需要数据库？

    使用纯文件的方式来存储和读取数据是效率比较低的。数据库会通过合适的方式来组织数据，这样的话，数据的读取和写入都会比较快。数据可以是结构化的，半结构化的或者完全非结构化的。根据存储的数据类型，数据结构可以分为以下几类：

1. 关系型数据库：常用的数据库，基于表结构的。数据表之间可以有关联关系。这种数据库可以用SQL语言来操作数据。
2. 键-值数据库：通过键-值对来存储数据。数据可以通过指定的键来读取。内存数据库大多都是这种类型的数据库。
3. 对象数据库。数据结构更像一个对象而不是一个表。
4. 图数据库：图数据库存储的是节点和边，常用于数据挖掘和社交媒体应用。

SQLite 数据库架构

    SQLite数据库架构可以分为两个部分，分别叫做内核（core）和后台（backend）。内核部分包含接口，分词器，解析器，代码生成器和虚拟机，它负责生成数据库事务的执行指令。后台包含B-tree，页（Pager）以及用来读取文件的操作系统接口。分词器，解析器和代码生成器合起来成为编译器，它负责生成在虚拟机上执行的指令。

从哪里开始？

    了解一个数据库的架构，你需要有以下预备知识：

1. 熟悉数据结构和算法。特别是B-tree，链表，哈希表等数据结构。
2. 对计算机系统结构（computer architecture）有一定的了解。例如文件是如何从磁盘里进行读写的，分页系统以及缓存是如何工作的。
3. 一些计算原理的知识，例如有限自动机以及正则表达式。

SQLite 架构

image

虚拟文件系统VFS（Virtual File System)

    在Unix和Windows两种系统中，文件访问的方式是不同的。对此，VFS提供了与操作系统无关的通用API。这套API里包含了文件的打开，读取，写入和关闭这些功能。以下是VFS里里用来读取和写入文件的API。

    Create a connection to file to read write 
    zFilename : file name 
    id : file pointer 
    pReadonly : read or write 
    */
    int sqliteOsOpenReadWrite(const char *zFilename, OsFile *id,int *pReadonly);

    Acqure the lock to read file. This function should be 
    called before caling to any file read function. 
    Return 0 if success
    id : file pointer 
    */
    int sqliteOsReadLock(OsFile *id);

    Get the write lock to write into a file. This function should called before
    doing any write operation into the file system.
    Return 0 if success
    id : file pointer
    */
    int sqliteOsWriteLock(OsFile *id);

    Move to the given number of offest to read or write into the file
    */
    int sqliteOsSeek(OsFile *id, int offset);

`/* 
Read amt bytes from the file with offset pointed by sqliteOsSeek
*/
int sqliteOsRead(OsFile *id, void *pBuf, int amt);`

`/* 
Write amt bytes from the pBuf into the file
*/
int sqliteOsWrite(OsFile *id, const void *pBuf, int amt);`

    首先，你可以通过sqliteOpenReadWrite函数来打开一个文件。它会返回一个文件指针，你可以用这个指针来进行文件的读写操作。接下来，如果要进行读写的话，就需要先获取相应的锁。对于只读操作，只获取读锁。对于事务而言，无论是读写，都需要获取写锁。

    读写文件的寻址操作可以通过给sqliteOsSeek函数传入指定的位移来完成。文件位移是一个整数，它表示要读写的位置距离文件起始处的字节数。

页（Pager）

    页是数据库在文件系统里的数据存储的最小单元。它是数据库从磁盘读取数据的最小单位，当数据库需要加装数据的时候，它会一次性读取整个页的数据。如果被加载的页被访问比较频繁的话，它就会被保存在数据库引擎的缓存里。页都会被编号，起始号是1。第一页被称为根页，而且一个页的大小是固定的。

    Open pager with the given file name
    */
    int sqlitepager_open(Pager **ppPager,const char *zFilename,int nPage,int nEx);

    Get page specified by the page number
    */
    int sqlitepager_get(Pager *pPager, Pgno pgno, void **ppPage);

    Start to write data into a page specified in pData
    */
    int sqlitepager_write(void *pData);

    Commit page changes into the file
    */
    int sqlitepager_commit(Pager*);

    Close the connection to the file
    */
    int sqlitepager_close(Pager *pPager);

Btree

    Btree是一个用来存储数据的树状数据结构。最简单的Btree是二叉树（Binary tree）。数据库使用Btree来保存索引，用以提高其性能。Btree的每个节点都会保存一列用来进行索引的值。而且你可以为数据表的每一列都创建一个Btree索引。每个Btree都包含一个根节点，它是搜索的起始点。

“游标（Cursor）”是用来标识Btree里的一条记录的一个特殊指针。游标通过页码（page id）和位置（offset）来索引一个数据记录。SQLite通过master_table这个表来存储数据表元数据，并且master_table的数据是存放在数据库的第一个数据页里。

    Open file connection to a page file name specified by zFileName with 
    nCache size cache
    */
    int sqliteBtreeOpen(const char *zFilename, int mode, int nCache, Btree **ppBtree)

    Start transaction. This function should called before any btree modification 
    operations
    */
    int sqliteBtreeBeginTrans(Btree *pBt)

    Insert key pKey with nKey byte and value pData with nData byte put 
    into the Btree
    */
    int sqliteBtreeInsert(BtCursor *pCur, const void *pKey, int nKey, 
      const void *pData, int nData)

    Write data into the file
    */
    int sqliteBtreeCommit(Btree *pBt)

    Move cursor to the matching pKey with nKey bytes
    */
    int sqliteBtreeMoveto(BtCursor *pCur, const void *pKey, int nKey, int *pRes)

VDBE（虚拟数据库系统，Virtual Database Engine）

    虚拟数据库系统（VDBE）是一个可以运行代码生成器生成的指令的虚拟机。包括insert，delete，update，select在内的SQL指令都会被转换成一系列指令，然后这些指令都会在虚拟机上运行。每个指令包含三个输入参数，分别是p1，p2和p3。你可以把它们看着是函数的输入参数类似。

    以下是我为下面这个select语句构造的执行指令栈。PC是程序计数器的指令id。SQLite中比较有趣的一点是，你可以通过在SQL语句前面加上explain命令来获取该SQL对应虚拟数据库系统（VDBE）的指令。

explain select * from foo;

PC	OPCode	P1	P2	P3	备注
1	ColumnCount	1	0		设置列数为1
2	ColumnName	0	0	value	设置列名为“value”
3	Open	0	3	foo	打开游标（cursor），并且指向第3页，该页是foo表的根页
4	VerifyCookies	46	0		确认表结构没有变动
5	Rewind	0	11		重置游标到第一个数据项
6	Column	0	0		从Btree里读取数据，并存放在栈里
7	Column	0	0
8	Ne	1	10		取出栈顶的两个元素进行对比。如果相等，就跳到P2的指令；否则的话，继续执行下一条指令。
9	Callback	1	0		从栈顶取出P1个值并且转换成一个数组，这就是SQL表达式的执行结果。
10	Next	0	5		将游标移动到下一条记录上，如果存在数据的话，就跳到P2所对应的指令继续执行；否则，就继续执行下一条。
11	Close	0	0		关闭游标

编译器

    分词器，解析器以及代码生成器组合起来就是编译器，它可以生成在虚拟数据库引擎（VDBE）上执行的指令。分词器通过扫描SQL语句来生成一系列的标识符（Token）。然后，再校验语法并生成语法树（parse tree）。最后，代码生成器将语法树转换成一段SQLite指令的小程序。

结论

    SQLite是一个简单，轻量级，高性能的关系型数据库，它被广泛用于软件系统设计。早期版本的SQLite的实现架构简单，并且代码可读性非常高。页提供了一种将文件读取封装成对固定大小数据块进行操作的抽象层。Btree提供了在内存里高效存储和访问数据的途径。最后，当SQL被加载到SQLite数据库的时候，会被转换成SQLite机器码并在虚拟数据库系统（VDBE）上执行。最终结果会通过API返回给用户。