1 体系结构

接口
大部分sqlite的接口在main.c,legacy.c，vdbeapi.c源文件中实现，但是有些常规性的分散在其他的文件中，因为它们可以在文件作用域内访问一些数据结构。比如，sqlite3_get_table() 在table.c中实现，sqlite3_mprintf() 在printf.c中实现，sqlite3_complete()在tokenizer.c中实现，tcl接口在tclsqlite.c中实现，更多关于sqlite的c接口可以访问
为了避免与其他的软件产生命名冲突，所有的对外符号都以sqlite3作为前缀。（也就是说，这些符号构成了sqlite的api）

分词器
当一个包含sql语句的字符串执行的时候，接口把字符串传递给分词器。分词器的工作就是把原始的字符串分割成标记，然后一个一个的传给语法分析器。这个分词器在tokenizer.c中用c实现。
注意在这个设计里面，分词器调用语法分析器。那些熟悉YACC或者BISON的朋友们习惯用另一种方式设计-----用语法分析器调用分词器。sqlite的作者分别用这两种方法实现过，最后发现第一种方法工作效率比较高。YACC有很多局限性。

语法分析器
语法分析器是一个根据环境给符号赋予意义的模块。这个分析器用了lemo的LALR(1)分析器生成。lemon跟YACC/BISON差不多，但是它用了一种很少产生错误的输入句法（Syntax），而且lemon可以产生一个可重入(reentrant)和线程安全(thread-safe)的分析器。lemon可以定义无端点的破坏（non-terminal destructor）的概念，所以当出现错误句法时不会出现内存泄露。
由于lemon是一个一般不会经常使用的程序，lemon完整的源文件(就一个c文件)在sqlite发布版本的tool文件夹下。关于lemon的文档在doc文件夹下。

代码生成器
在分析器把符号翻译(assemble)成完整的sql语句的后，它会调用代码生成器产生sql语句需要执行的虚拟机代码。代码生成器包含很多文件，attach.c,auth.c,build.c,delete.c,expr.c,insert.c,pragma.c,select.c,trigger.c update.c,vacuum.c和where.c。这些文件是大部分古怪魔法(serIoUs magic)发生的地方。expr.c处理表达式的代码生成，where.c 处理select，update，delete语句中where子句的代码生成，attach.c,delete.c insert.c select.c trigger.c update.c 和 vacuum.c 处理跟它们名字有关语句的代码生成(当有必要时，这些文件调用expr.c和where.c中常用的函数)。其余的sql 语句在build.c中生成。auth.c文件实现sqlite3_set_authorizer()接口.

虚拟机
由代码生成器生成的代码被虚拟机执行。更多的关于虚拟的的信息可以访问————。摘要而言，虚拟机实现了一个专门处理数据库文件的抽象的计算引擎(abstract computing engine)。这个虚拟机包含了一个作为中间存储器的栈，每条指令包含一个操作码和多达3个的操作数。
这个虚拟机完全在vdbe.c中实现，它有自己的头文件vdbe.h，里面定义了虚拟机和其他的模块的接口。vdbeInt.h里面定义了虚拟机里面私有的数据结构，vdbeaux.c里面包含了虚拟机常用的工具，也包含了其余为构造虚拟机程序的库的接口模块。vdbeapi.c 包含了虚拟机对外的接口比如sqlite3_bind_... 的函数族。数据类型(individual values)(strings,integer,floating point numbers,和BLOBs)存储在一个内部的叫做“mem”对象当中，在vdbemen.c中。
sqlite用回调c语言函数（c-language routines）的方法实现sql 函数。甚至内建的sql函数都是用这种方式实现的。很多内建的sql函数（比如coalesce(),count(),substr()，还有很多），在func.c中实现，数据和时间的转换函数在date.c中实现。

B-Tree
sqlite数据库在硬盘上用B-tree实现，具体代码在btree.c中。在数据库中的每个表和索引都使用单独的b-tree。所有的b-tree存储在用一个文件中。文件格式的细节在btree.c开头的一大段注释中记录。
b-tree的接口在btree.h头文件中记录。

页缓存
B-tree模块需要以一个固定大小的块从硬盘读取数据。默认的块大小是1024个字节，可以在512和65536个字节间变化。页缓存的任务是读，写，缓存块。页缓存提供回滚，原子委托抽象（atomic commit abstraction），处理数据文件的锁。b-tree需要从页缓存请求特殊的页，当修改页，委托，回滚时通知页缓存，页缓存处理所以的细节以确定快速，安全，高效的处理请求。
实现页缓存的代码在pager.c中，页缓存子系统的接口在pager.h头文件中定义。

操作系统接口
为了在POSIX和win32操作系统之间移植，sqlite用了一个抽象的层作为与操作系统间的接口。实现OS抽象层的接口在os.h中定义，每一种支持的系统有它们自己的实现方式，os_unix.c为unix，os_win.c为windows，当然也有自己相应的头文件os_unix.h和os_win.h，等等。
工具
内存配置和字符串比较的功能在util.c中，语法分析器用到的符号表用hash 表实现，具体代码在hash.c中。utf.c包含了Unicode转换子程序。sqlite有它自己printf()实现(增加了很多功能)，在printf.c中。也有自己的随机数生成的实现，在random.c中。

sqlite采用了层次化，模块化的设计，而这些使得它的可扩展性和可移植性非常强。而且sqlite的架构与通用DBMS的结构差别不是很大，所以它对于理解通用DBMS具有重要意义。好了，下面我们开始讨论sqlite剩余的两部分：Back-end(后端)和compiler(编译器)。

2、B-tree和Pager
B-Tree使得VDBE可以在O(logN)下查询，插入和删除数据，以及O(1)下双向遍历结果集。B-Tree不会直接读写磁盘，它仅仅维护着页面(pages)之间的关系。当B-TREE需要页面或者修改页面时，它就会调用Pager。当修改页面时，pager保证原始页面首先写入日志文件，当它完成写操作时，pager根据事务状态决定如何做。B-tree不直接读写文件，而是通过page cache这个缓冲模块读写文件对于性能是有重要意义的（注：这和操作系统读写文件类似，在Linux中,操作系统的上层模块并不直接调用设备驱动读写设备，而是通过一个高速缓冲模块调用设备驱动读写文件,并将结果存到高速缓冲区）。

2.1、数据库文件格式（Database File Format）
数据库中所有的页面都按从1开始顺序标记。一个数据库由许多B-tree构成——每一个表和索引都有一个B-tree（注：索引采用B-tree，而表采用B+tree，这主要是表和索引的需求不同以及B-tree和B+tree的结构不同决定的：B+tree的所有叶子节点包含了全部关键字信息，而且可以有两种顺序查找——具体参见《数据结构》，严蔚敏。而B-tree更适合用来作索引）。所有表和索引的根页面都存储在sqlite_master表中。
数据库中第一个页面（page 1）有点特殊，page 1的前100个字节包含一个描述数据库文件的特殊的文件头。它包括库的版本，模式的版本，页面大小，编码等所有创建数据库时设置的参数。这个特殊的文件头的内容在btree.c中定义，page 1也是sqlite_master表的根页面。

2.1、页面重用及回收(Page Reuse and Vacuum )
sqlite利用一个空闲列表(free list)进行页面回收。当一个页面的所有记录都被删除时，就被插入到该列表。当运行VACUUM命令时，会清除free list，所以数据库会缩小，本质上它是在新的文件重新建立数据库，而所有使用的页在都被拷贝过去，而free list却不会，结果就是一个新的，变小的数据库。当数据库的autovacuum开启时，sqlite不会使用free list，而且在每一次commit时自动压缩数据库。

2.2、B-Tree记录
B-tree中页面由B-tree记录组成，也叫做payloads。每一个B-tree记录，或者payload有两个域：关键字域(key field)和数据域(data field)。Key field就是ROWID的值，或者数据库中表的关键字的值。从B-tree的角度，data field可以是任何无结构的数据。数据库的记录就保存在这些data fields中。B-tree的任务就是排序和遍历，它最需要就是关键字。Payloads的大小是不定的，这与内部的关键字和数据域有关，当一个payload太大不能存在一个页面内进便保存到多个页面。

B+Tree按关键字排序，所有的关键字必须唯一。表采用B+tree，内部页面不包含数据，如下：

B+tree中根页面(root page)和内部页面(internal pages)都是用来导航的，这些页面的数据域都是指向下级页面的指针，仅仅包含关键字。所有的数据库记录都存储在叶子页面(leaf pages)内。在叶节点一级，记录和页面都是按照关键字的顺序的，所以B-tree可以水平方向遍历，时间复杂度为O(1)。

2.3、记录和域（Records and Fields）
位于叶节点页面的数据域的记录由VDBE管理，数据库记录以二进制的形式存储，但有一定的数据格式。记录格式包括一个逻辑头（logical header）和一个数据区(data segment)，header segment包括header的大小和一个数据类型数组，数据类型用来在data segment的数据的类型，如下：

2.4、层次数据组织(Hierarchical Data Organization)

从上往下，数据越来越无序，从下向上，数据越来越结构化.

2.5、B-Tree API
B-Tree模块有它自己的API，它可以独立于C API使用。另一个特点就是它支持事务。由pager处理的事务，锁和日志都是为B-tree服务的。根据功能可以分为以下几类：
2.5.1、访问和事务函数
sqlite3BtreeOpen: Opens a new database file. Returns a B-tree object.
sqlite3BtreeClose: Closes a database.
sqlite3BtreeBeginTrans: Starts a new transaction.
sqlite3BtreeCommit: Commits the current transaction.
sqlite3BtreeRollback: Rolls back the current transaction.
sqlite3BtreeBeginStmt: Starts a statement transaction.
sqlite3BtreeCommitStmt: Commits a statement transaction.
sqlite3BtreeRollbackStmt: Rolls back a statement transaction.

2.5.2、表函数
sqlite3BtreeCreateTable: Creates a new,empty B-tree in a database file.
sqlite3BtreeDropTable: Destroys a B-tree in a database file.
sqlite3BtreeClearTable: Removes all data from a B-tree,but keeps the B-tree intact.
2.5.3、游标函数(Cursor Functions)
sqlite3BtreeCursor: Creates a new cursor pointing to a particular B-tree.
sqlite3BtreeCloseCursor: Closes the B-tree cursor.
sqlite3BtreeFirst: Moves the cursor to the first element in a B-tree.
sqlite3BtreeLast: Moves the cursor to the last element in a B-tree.
sqlite3BtreeNext: Moves the cursor to the next element after the one it is currently
pointing to.
sqlite3BtreePrevIoUs: Moves the cursor to the prevIoUs element before the one it is
currently pointing to.

sqlite3BtreeMoveto: Moves the cursor to an element that matches the key value passed in as a parameter.

2.5.4、记录函数(Record Functions)
sqlite3BtreeDelete: Deletes the record that the cursor is pointing to.
sqlite3BtreeInsert: Inserts a new element in the appropriate place of the B-tree.
sqlite3BtreeKeySize: Returns the number of bytes in the key of the record that the
cursor is pointing to.
sqlite3BtreeKey: Returns the key of the record the cursor is currently pointing to.
sqlite3BtreeDataSize: Returns the number of bytes in the data record that the cursor is
currently pointing to.
sqlite3BtreeData: Returns the data in the record the cursor is currently pointing to.

2.5.5、配置函数(Configuration Functions)
sqlite3BtreeSetCacheSize: Controls the page cache size as well as the synchronous
writes (as defined in the synchronous pragma).
sqlite3BtreeSetSafetyLevel: Changes the way data is synced to disk in order to increase
or decrease how well the database resists damage due to OS crashes and power failures.
Level 1 is the same as asynchronous (no syncs() occur and there is a high probability of
damage). This is the equivalent to pragma synchronous=OFF. Level 2 is the default. There
is a very low but non-zero probability of damage. This is the equivalent to pragma
synchronous=NORMAL. Level 3 reduces the probability of damage to near zero but with a
write performance reduction. This is the equivalent to pragma synchronous=FULL.
sqlite3BtreeSetPageSize: Sets the database page size.
sqlite3BtreeGetPageSize: Returns the database page size.
sqlite3BtreeSetAutoVacuum: Sets the autovacuum property of the database.
sqlite3BtreeGetAutoVacuum: Returns whether the database uses autovacuum.
sqlite3BtreeSetBusyHandler: Sets the busy handler
2.6、实例分析
最后以sqlite3_open的具体实现结束本节的讨论(参见Version 3.6.10的源码)：

由上图可以知道，sqlite的所有IO操作，最终都转化为操作系统的系统调用(一名话：DBMS建立在痛苦的OS之上)。同时也可以看到sqlite的实现非常的层次化，模块化，使得sqlite更易扩展，可移植性非常强。

3、编译器（Compiler）
3.1、分词器(Tokenizer)
接口把要执行的sql语句传递给Tokenizer,Tokenizer按照sql的词法定义把它切分一个一个的词，并传递给分析器(Parser)进行语法分析。分词器是手工写的，主要在Tokenizer.c中实现。
3.2、分析器(Parser)
sqlite的语法分析器是用Lemon——一个开源的LALR(1)语法分析器的生成器，生成的文件为parser.c。
一个简单的语法树：
SELECT rowid,name,season FROM episodes WHERE rowid=1 LIMIT 1


3.3、代码生成器（Code Generator）
代码生成器是sqlite中取庞大，最复杂的部分。它与Parser关系紧密，根据语法分析树生成VDBE程序执行sql语句的功能。由诸多文件构成：select.c,update.c,trigger.c,where.c等文件。这些文件生成相应的VDBE程序指令，比如SELECT语句就由select.c生成。下面是一个读操作中打开表的代码的生成实现：
/* Generate code that will open a table for reading.
*/
void sqlite3OpenTableForReading(
Vdbe *v,/* Generate code into this VDBE */
int iCur,/* The cursor number of the table */
Table *pTab /* The table to be opened */
){
sqlite3VdbeAddOp(v,OP_Integer,pTab->iDb,0);
sqlite3VdbeAddOp(v,OP_OpenRead,iCur,pTab->tnum);
VdbeComment((v,"# %s",pTab->zName));
sqlite3VdbeAddOp(v,OP_SetNumColumns,pTab->nCol);
}
sqlite3vdbeAddOp函数有三个参数：（1）VDBE实例（它将添加指令），（2）操作码（一条指令），（3）两个操作数。

3.4、查询优化
代码生成器不仅负责生成代码，也负责进行查询优化。主要的实现位于where.c中，生成的WHERE语句块通常被其它模块共享，比如select.c，update.c以及delete.c。这些模块调用sqlite3WhereBegin()开始WHERE语句块的指令生成，然后加入它们自己的VDBE代码返回，最后调用sqlite3WhereEnd()结束指令生成，如下：