1、sqlite介绍

　　自几十年前出现的商业应用程序以来，数据库就成为软件应用程序的主要组成部分。正与数据库 管理 系统非常关键一样，它们也变得非常庞大，并占用了相当多的系统资源，增加了管理的复杂性。随着软件应用程序逐渐模块模块化，一种新型数据库会比大型复杂的传统数据库管理系统更适应。嵌入式数据库直接在应用程序进程中运行，提供了零配置（zero-configuration）运行模式，并且资源占用非常少。

　　sqlite是一个开源的嵌入式关系 数据库 ，它在2000年由D. Richard Hipp发布，它的减少应用程序管理数据的开销，sqlite可移植性好，很容易使用，很小，高效而且可靠。

　　sqlite嵌入到使用它的应用程序中，它们共用相同的进程 空间 ，而不是单独的一个进程。从外部看，它并不像一个RDBMS，但在进程内部，它却是完整的，自包含的数据库引擎。

　　嵌入式数据库的一大好处就是在你的程序内部不需要网络配置，也不需要管理。因为客户端和服务器在同一进程空间运行。sqlite 的数据库权限只依赖于文件系统，没有用户帐户的概念。sqlite 有数据库级锁定，没有网络服务器。它需要的内存，其它开销很小，适合用于嵌入式设备。你需要做的仅仅是把它正确的编译到你的程序。

　　2、架构(architecture)

　　sqlite采用了模块的设计，它由三个子系统，包括8个独立的模块构成。

　　2.1、接口(Interface)

　　接口由sqlite C API组成，也就是说不管是程序、脚本语言还是库文件，最终都是通过它与sqlite交互的(我们通常用得较多的ODBC/JDBC最后也会转化为相应C API的调用)。

　　2.2、编译器(Compiler)

　　在编译器中，分词器（Tokenizer）和分析器(Parser)对sql进行 语法 检查，然后把它转化为底层能更方便处理的分层的数据结构---语法树，然后把语法树传给代码生成器(code generator)进行处理。而代码生成器根据它生成一种针对sqlite的汇编代码，最后由 虚拟 机(Virtual Machine)执行。

　　2.3、虚拟机(Virtual Machine)

　　架构中最核心的部分是虚拟机，或者叫做虚拟数据库引擎(Virtual Database Engine,VDBE)。它和Java虚拟机相似，解释执行字节代码。VDBE的字节代码由128个操作码(opcodes)构成，它们主要集中在数据库操作。它的每一条指令都用来完成特定的数据库操作(比如打开一个表的游标)或者为这些操作栈空间的准备(比如压入参数)。总之，所有的这些指令都是为了满足sql命令的要求(关于VM，后面会做详细介绍)。

　　2.4、后端(Back-End)

　　后端由B-树(B-tree)，页缓存(page cache，pager)和操作系统接口(即系统调用)构成。B-tree和page cache共同对数据进行管理。B-tree的主要功能就是索引，它维护着各个页面之间的复杂的关系，便于快速找到所需数据。而pager的主要作用就是通过OS接口在B-tree和Disk之间传递页面。

　　3、sqlite的特点(sqlite’s Features and Philosophy)

　　3.1、零配置(Zero Configuration)

　　3.2、可移植(Portability)：

　　它是运行在Windows,Linux,BSD,Mac OS X和一些商用Unix系统，比如Sun的Solaris,IBM的AIX，同样，它也可以工作在许多嵌入式操作系统下，比如QNX,VxWorks,Palm OS,Symbin和Windows CE。

　　3.3、压缩（Compactness）：

　　sqlite是被设计成轻量级，自包含的。one header file,one library,and you’re relational,no external database server required

　　3.4、简单(Simplicity)

　　3.5、灵活(Flexibility)

　　3.6、可靠(Reliability)：

　　sqlite的核心大约有3万行标准C代码，这些代码都是模块化的，很容易阅读。

　　主要参考:The Definitive Guide to sqlite

　我原打算直接从VDBE入手的，因为它起着承上启下的作用，是整个sqlite的核心，并分析源码，但考虑到这是一个系列的文章，我希望能把问题说全，所以还是从基本概念入手，对于初学者，如果没有这些概念，是很继续下去的。好了，下面开始第二章，由于这一章内容很多，我将分两部分讨论，下面开始第一部分。

　　1、API

　　由两部分组成: 核心API(core API) 和扩展API（extension API）

　　核心API的函数实现基本的数据库操作：连接数据库，处理sql，遍历结果集。它也包括一些实用函数，比如字符串转换，操作控制，调试和错误处理。

　　扩展API通过创建你自定义的sql函数去扩展sqlite。

　　1.1、sqlite Version 3的一些新特点：

　　(1)sqlite的API全部重新设计，由第二版的15个函数增加到88个函数。这些函数包括支持UTF-8和UTF-16编码的功能函数。

　　(2)改进并发性能。加锁子系统引进一种锁升级模型(lock escalation model)，解决了第二版的写进程饿死的问题(该问题是任何一个DBMS必须面对的问题)。这种模型保证写进程按照先来先服务的算法得到排斥锁(Exclusive Lock)。甚至，写进程通过把结果写入临时缓冲区(Temporary Buffer)，可以在得到排斥锁之前就能开始工作。这对于写要求较高的应用，性能可提高400%（引自参考文献）。

　　(3)改进的B-树。对于表采用B+树，大大提高查询效率。

(4)sqlite 3最重要的改变是它的存储模型。由第二版只支持文本模型，扩展到支持5种本地数据类型。

　　总之，sqlite Version 3与sqlite Vertion 2有很大的不同，在灵活性，特点和性能方面有很大的改进。

　　1.2、主要的 数据结构 (The Principal Data Structures)

　　sqlite由很多部分组成－parser,tokenize,virtual machine等等。但是从程序员的角度，最需要知道的是:connection,statements,B-tree和pager。它们之间的关系如下：

　　上图告诉我们在编程需要知道的三个主要方面：API,事务(Transaction)和锁(Locks)。从技术上来说，B-tree和pager不是API的一部分。但是它们却在事务和锁上起着关键 作用 （稍后将讨论）。

　　1.3、Connections和Statements

　　Connection和statement是执行sql命令涉及的两个主要数据结构，几乎所有通过API 进行 的操作都要用到它们。一个连接(Connection)代表在一个独立的事务环境下的一个连接A (connection represents a single connection to a database as well as a single transaction context)。每一个statement都和一个connection关联，它通常 表示 一个编译过的sql语句，在内部，它以VDBE字节码表示。Statement包括执行一个命令所需要一切，包括保存VDBE程序执行状态所需的 资源 ，指向硬盘记录的B-树游标，以及参数等等。

　　1.4、B-tree和pager

　　一个connection可以有多个database对象---一个主要的数据库以及附加的数据库，每一个数据库对象有一个B-tree对象，一个B-tree有一个pager对象(这里的对象不是面向对象的“对象”，只是为了说清楚问题)。

　　Statement最终都是通过connection的B-tree和pager从数据库读或者写数据，通过B-tree的游标(cursor)遍历存储在页面(page)中的 记录 。游标在访问页面之前要把数所从disk加载到内存，而这就是pager的任务。任何时候，如果B-tree需要页面，它都会请求pager从disk读取数据，然后把页面(page)加载到页面缓冲区(page cache)，之后，B-tree和与之关联的游标就可以访问位于page中的记录了。

　　如果cursor改变了page，为了防止事务回滚，pager必须采取特殊的方式保存原来的page。总的来说，pager负责读写 数据库 ，管理内存缓存和页面（page），以及管理事务，锁和崩溃恢复(这些在事务一节会详细介绍)。

　　总之，关于connection和transaction，你必须知道两件事：

　　(1)对数据库的任何操作，一个连接存在于一个事务下。

　　(2)一个连接决不会同时存在多个事务下。

　　whenever a connection does anything with a database,it always operates under exactly one

　　transaction,no more,no less.

　　1.5、核心API

　　核心API 主要与执行sql命令有关，本质上有两种方法执行sql语句：prepared query 和wrapped query。Prepared query由三个阶段构成：preparation，execution和finalization。其实wrapped query只是对prepared query的三个过程包装而已，最终也会转化为prepared query的执行。

　　1.5.1、连接的生命周期(The Connection Lifecycle)

　　和大多数据库连接相同，由三个过程构成：

　　（1）连接数据库(Connect to the database)：

　　每一个sqlite数据库都存储在单独的操作系统文件中，连接，打开数据库的C API为：sqlite3_open()，它的实现位于main.c文件中，如下：

int sqlite3_open(const char *zFilename,sqlite3 **ppDb)
{
　return openDatabase(zFilename,ppDb,sqlITE_OPEN_READWRITE | sqlITE_OPEN_CREATE,0);
}

　　当连接一个在磁盘上的 数据库 ，如果数据库文件存在，sqlite打开一个文件；如果不存在，sqlite会假定你想创建一个新的数据库。在这种情况下，sqlite不会立即在磁盘上创建一个文件，只有当你向数据库写入数据时才会创建文件，比如：创建表、视图或者其它数据库对象。如果你打开一个数据，不做任何事，然后关闭它，sqlite会创建一个文件，只是一个空文件而已。

　　另外一个不立即创建一个新文件的原因是，一些数据库的参数，比如：编码，页面大小等，只在在数据库创建前设置。默认情况下，页面大小为1024字节，但是你可以选择512-32768字节之间为 2幂数的数字。有些时候，较大的页面能更有效的处理大量的数据。

　　（2）执行事务(Perform transactions)：

　　all commands are executed within transactions。默认情况下，事务自动提交，也就是每一个sql语句都在一个独立的事务下运行。当然也可以通过使用BEGIN..COMMIT手动提交事务。

　　（3）断开连接(Disconnect from the database)：

　　主要是关闭数据库的文件。

　　1.5.2、执行Prepared Query

　　前面提到，预处理查询(Prepared Query)是sqlite执行所有sql命令的方式，包括以下三个过程：

　　(1)Prepared Query：

　　分析器（parser），分词器(tokenizer)和代码生成器(code generator)把sql Statement编译成VDBE字节码，编译器会创建一个statement句柄(sqlite3_stmt)，它包括字节码以及其它执行命令和遍历结果集的所有资源。

　　相应的C API为sqlite3_prepare()，位于prepare.c文件中，如下：

int sqlite3_prepare(
　sqlite3 *db,　　　　　　　
　const char *zsql,　　　　
　int nBytes,　　　　　　　
　sqlite3_stmt **ppStmt,　　
　const char **pzTail　　　
){
　int rc;
　rc = sqlite3LockAndPrepare(db,zsql,nBytes,ppStmt,pzTail);
　assert( rc==sqlITE_OK || ppStmt==0 || *ppStmt==0 );　
　return rc;
}

(2)Execution：

　　虚拟机执行字节码，执行过程是一个步进(stepwise)的过程，每一步(step)由sqlite3_step()启动，并由VDBE执行一段字节码。由sqlite3_prepare编译字节代码，并由sqlite3_step()启动虚拟机执行。在遍历结果集的过程中，它返回sqlITE_ROW，当到达结果末尾时，返回sqlITE_DONE。

　　(3)Finalization：

　　VDBE关闭statement，释放 资源 。相应的C API为sqlite3_finalize()。

　　通过下图可以更容易理解该过程：

　　最后以一个具体的例子结束本节，下节讨论事务。

#include
#include
#include"sqlite3.h"
#include
intmain(intargc,char**argv)
{
　　int rc,i,ncols;
　　sqlite3 *db;
　　sqlite3_stmt *stmt;
　　char *sql;
　　const char*tail;
　　//打开数据
　　rc=sqlite3_open("foods.db",&db);
　　if(rc){
　　　　fprintf(stderr,"Can'topendatabase:%sn",sqlite3_errmsg(db));
　　　　sqlite3_close(db);
　　　　exit(1);
　　}
　　
　　sql="select * from episodes";
　　//预处理
　　rc=sqlite3_prepare(db,sql,(int)strlen(sql),&stmt,&tail);
　　if(rc!=sqlITE_OK){
　　　　fprintf(stderr,"sqlerror:%sn",sqlite3_errmsg(db));
　　}
　　
　　rc=sqlite3_step(stmt);
　　ncols=sqlite3_column_count(stmt);
　　while(rc==sqlITE_ROW){
　　　　
　　　　for(i=0;i
　　　　　　fprintf(stderr,"'%s'",sqlite3_column_text(stmt,i));
　　　　}
　　　　fprintf(stderr,"n");
　　　　rc=sqlite3_step(stmt);
　　}
　　//释放statement
　　sqlite3_finalize(stmt);
　　//关闭数据库
　　sqlite3_close(db);
　　return0;　　
}

写在前面:本节讨论事务,事务是DBMS最核心的技术之一.在计算机科学史上,有三位科学家因在数据库领域的成就而获ACM图灵奖,而其中之一 Jim Gray(曾任职微软)就是因为在事务处理方面的成就而获得这一殊荣,正是因为他,才使得OLTP系统在随后直到今天大行其道.关于事务处理技术,涉及到很多,随便就能写一本书.在这里我只讨论sqlite事务实现的一些原理,sqlite的事务实现与大型通用的DBMS相比,其实现比较简单.这些内容可能比较偏于理论,但却不难,也是理解其它内容的基础.好了,下面开始第二节---事务.

2、 事务(Transaction)

2.1、事务的周期(Transaction Lifecycles)
程序与事务之间有两件事值得注意：
（1） 哪些对象在事务下运行——这直接与API有关。
（2） 事务的生命周期，即什么时候开始，什么时候结束以及它在什么时候开始影响别的连接（这点对于并发性很重要）——这涉及到sqlite的具体实现。
一个连接（connection）可以包含多个(statement)，而且每个连接有一个与数据库关联的B-tree和一个pager。Pager在连接中起着很重要的作用，因为它管理事务、锁、内存缓存以及负责崩溃恢复(crash recovery)。当你进行数据库写操作时，记住最重要的一件事：在任何时候，只在一个事务下执行一个连接。这些回答了第一个问题。
一般来说，一个事务的生命和statement差不多，你也可以手动结束它。默认情况下，事务自动提交，当然你也可以通过BEGIN..COMMIT手动提交。接下来就是锁的问题。

2.2、锁的状态(Lock States)
锁对于实现并发访问很重要，而对于大型通用的DBMS，锁的实现也十分复杂，而sqlite相对较简单。通常情况下，它的持续时间和事务一致。一个事务开始，它会先加锁，事务结束，释放锁。但是系统在事务没有结束的情况下崩溃，那么下一个访问数据库的连接会处理这种情况。
在sqlite中有5种不同状态的锁，连接（connection）任何时候都处于其中的一个状态。下图显示了相应的状态以及锁的生命周期。

关于这个图有以下几点值得注意：
（1） 一个事务可以在UNLOCKED，RESERVED或EXCLUSIVE三种状态下开始。默认情况下在UNLOCKED时开始。
（2） 白色框中的UNLOCKED,PENDING,SHARED和 RESERVED可以在一个数据库的同一时存在。
（3） 从灰色的PENDING开始，事情就变得严格起来，意味着事务想得到排斥锁(EXCLUSIVE)（注意与白色框中的区别）。
虽然锁有这么多状态，但是从体质上来说，只有两种情况：读事务和写事务。

2.3、读事务(Read Transactions)
我们先来看看SELECT语句执行时锁的状态变化过程，非常简单：一个连接执行select语句，触发一个事务，从UNLOCKED到SHARED，当事务COMMIT时，又回到UNLOCKED，就这么简单。
考虑下面的例子(为了简单，这里用了伪码)：
db = open('foods.db')
db.exec('BEGIN')
db.exec('SELECT * FROM episodes')
db.exec('SELECT * FROM episodes')
db.exec('COMMIT')
db.close()

由于显式的使用了BEGIN和COMMIT，两个SELECT命令在一个事务下执行。第一个exec()执行时，connection处于SHARED，然后第二个exec()执行，当事务提交时，connection又从SHARED回到UNLOCKED状态，如下：
UNLOCKED→PENDING→SHARED→UNLOCKED
如果没有BEGIN和COMMIT两行时如下：
UNLOCKED→PENDING→SHARED→UNLOCKED→PENDING→ SHARED→UNLOCKED

2.4、写事务（Write Transactions）
下面我们来考虑写数据库，比如UPDATE。和读事务一样，它也会经历UNLOCKED→PENDING→SHARED，但接下来却是灰色的PENDING，

2.4.1、The Reserved States
当一个连接（connection）向数据库写数据时，从SHARED状态变为RESERVED状态，如果它得到RESERVED锁，也就意味着它已经准备好进行写操作了。即使它没有把修改写入数据库，也可以把修改保存到位于pager中缓存中（page cache）。
当一个连接进入RESERVED状态，pager就开始初始化恢复日志（rollback journal）。在RESERVED状态下，pager管理着三种页面：
(1) Modified pages：包含被B-树修改的记录，位于page cache中。
(2) Unmodified pages：包含没有被B-tree修改的记录。
(3) Journal pages：这是修改页面以前的版本，这些并不存储在page cache中，而是在B-tree修改页面之前写入日志。
Page cache非常重要，正是因为它的存在，一个处于RESERVED状态的连接可以真正的开始工作，而不会干扰其它的（读）连接。所以，sqlite可以高效的处理在同一时刻的多个读连接和一个写连接。

2.4.2 、The Pending States
当一个连接完成修改，就真正开始提交事务，执行该过程的pager进入EXCLUSIVE状态。从RESERVED状态，pager试着获取 PENDING锁，一旦得到，就独占它，不允许任何其它连接获得PENDING锁（PENDING is a gateway lock）。既然写操作持有PENDING锁，其它任何连接都不能从UNLOCKED状态进入SHARED状态，即没有任何连接可以进入数据（no new readers,no new writers）。只有那些已经处于SHARED状态的连接可以继续工作。而处于PENDING状态的Writer会一直等到所有这些连接释放它们的锁，然后对数据库加EXCUSIVE锁，进入EXCLUSIVE状态，独占数据库(讨论到这里，对sqlite的加锁机制应该比较清晰了)。


2.4.3、The Exclusive State
在EXCLUSIVE状态下，主要的工作是把修改的页面从page cache写入数据库文件，这是真正进行写操作的地方。
在pager写入modified pages之前，它还得先做一件事：写日志。它检查是否所有的日志都写入了磁盘，而这些通常位于操作的缓冲区中，所以pager得告诉OS把所有的文件写入磁盘，这是由程序synchronous(通过调用OS的相应的API实现)完成的。
日志是数据库进行恢复的惟一方法，所以日志对于DBMS非常重要。如果日志页面没有完全写入磁盘而发生崩溃，数据库就不能恢复到它原来的状态，此时数据库就处于不一致状态。日志写入完成后，pager就把所有的modified pages写入数据库文件。接下来就取决于事务提交的模式，如果是自动提交，那么pager清理日志，page cache，然后由EXCLUSIVE进入UNLOCKED。如果是手动提交，那么pager继续持有EXCLUSIVE锁和保存日志，直到COMMIT 或者ROLLBACK。

总之，从性能方面来说，进程占有排斥锁的时间应该尽可能的短，所以DBMS通常都是在真正写文件时才会占有排斥锁，这样能大大提高并发性能。

写在前面:从本章开始,我们开始进入sqlite的内核。为了能更好的理解sqlite，我先从总的结构上讨论一下内核，从全局把握sqlite很重要。sqlite的内核实现不是很难，但是也不是很简单。总的来说分为三个部分，本章主要讨论虚拟机(Virtual Machine)，但是这里只是从原理上概述，不会太多的涉及实际代码。但是概述完内核之后会仔细讨论源代码的。好了，下面我们来讨论虚拟机(VM)。

1、虚拟机（Virtual Machine）
VDBE是sqlite的核心，它的上层模块和下层模块都是本质上都是为它服务的。它的实现位于vbde.c,vdbe.h,vdbeapi.c,vdbeInt.h,和vdbemem.c几个文件中。它通过底层的基础设施B+Tree执行由编译器（Compiler）生成的字节代码，这种字节代码程序语言 (bytecode programming lauguage)是为了进行查询，读取和修改数据库而专门设计的。
字节代码在内存中被封装成sqlite3_stmt对象(内部叫做Vdbe，见vdbeInt.h)，Vdbe（或者说statement）包含执行程序所需要的一切：
a) a bytecode program
b) names and data types for all result columns
c) values bound to input parameters
d) a program counter
e) an execution stack of operands
f) an arbitrary amount of "numbered" memory cells
g) other run-time state information (such as open BTree objects,sorters,lists,sets)

字节代码和汇编程序十分类似，每一条指令由操作码和三个操作数构成：<opcode,P1,P2,P3>。Opcode为一定功能的操作码，为了理解，可以看成一个函数。P1是32位的有符号整数，p2是31位的无符号整数，它通常是导致跳转 (jump)的指令的目标地址（destination），当然这了有其它用途；p3为一个以null结尾的字符串或者其它结构体的指针。和C API不同的是，VDBE操作码经常变化，所以不应该用字节码写程序。
下面的几个C API直接和VDBE交互：
• sqlite3_bind_xxx() functions
• sqlite3_step()
• sqlite3_reset()
• sqlite3_column_xxx() functions
• sqlite3_finalize()

为了有个感性，下面看一个具体的字节码程序：
sqlite> .m col
sqlite> .h on
sqlite> .w 4 15 3 3 15
sqlite> explain select * from episodes;
addr opcode p1 p2 p3
---- --------------- --- --- ---------------
0 Goto 0 12
1 Integer 0 0
2 OpenRead 0 2 # episodes
3 SetNumColumns 0 3
4 Rewind 0 10
5 Recno 0 0
6 Column 0 1
7 Column 0 2
8 Callback 3 0
9 Next 0 5
10 Close 0 0
11 Halt 0 0
12 Transaction 0 0
13 VerifyCookie 0 10
14 Goto 0 1
15 Noop 0 0

1.1、 栈(Stack)
一个VDBE程序通常由不同完成特定任务的段（section）构成，每一个段中，都有一些操作栈的指令。这是由于不同的指令有不同个数的参数，一些指令只有一个参数；一些指令没有参数；一些指令有好几个参数，这种情况下，三个操作数就不能满足。
考虑到这些情况，指令采用栈来传递参数。(注：从汇编的角度来看，传递参数的方式有好几种，比如：寄存器，全局变量，而堆栈是现代语言常用的方式，它具有很大的灵活性)。而这些指令不会自己做这些事情，所以在它们之前，需要其它一些指令的帮助。VDBE把计算的中间结果保存到内存单元(memory cells)中，其实，堆栈和内存单元都是基于Mem（见vdbeInt.h）数据结构(注：这里的栈，内存单元都是虚拟的，记得一位计算机科学家说过：计算机科学中90%以上的科学都是虚拟化问题。一点不假，OS本质上也是虚拟机，而在这里sqlite，我们也处处可见虚拟化的身影，到后面的OS Interface模块中再仔细讨论这个问题)。

1.2、程序体(Program Body)
这是一个打开episodes表的过程。
第一条指令：Integer是为第二条指令作准备的，也就是把第二条指令执行需要的参数压入堆栈，OpenRead从堆栈中取出参数值然后执行。 sqlite可以通过ATTACH命令在一个连接中打开多个数据库文件，每当sqlite打开一个数据，它就为之赋一个索引号(index)，main database的索引为0，第一个数据库为1，依次如此。Integer指令数据库索引的值压入栈，而OpenRead从中取出值，并决定打开哪个数据，来看看sqlite文档中的解释：
Open a read-only cursor for the database table whose root page is P2 in a database file.
The database file is determined by an integer from the top of the stack. 0 means the main database and 1 means the database used for temporary tables.Give the new cursor an identifier of P1. The P1 values need not be contiguous but all P1 values should be small integers. It is an error for P1 to be negative.
If P2==0 then take the root page number from off of the stack.
There will be a read lock on the database whenever there is an open cursor. If the data-
base was unlocked prior to this instruction then a read lock is acquired as part of this instruction. A read lock allows other processes to read the database but prohibits any other process from modifying the database. The read lock is released when all cursors are closed. If this instruction attempts to get a read lock but fails,the script terminates with an sqlITE_BUSY error code.
The P3 value is a pointer to a KeyInfo structure that defines the content and collating

sequence of indices. P3 is NULL for cursors that are not pointing to indices.

再来看看SetNumColumns指令设置游标将指向的列。P1为游标的索引（这里为0，刚刚打开），P2为列的数目，episodes表有三列。
继续Rewind指令，它将游标重新设置到表的开始，它会检查表是否为空（即没有记录），如果没有记录，它会导致指令指针跳到P2指定的指令处。在这里，P2为10，即Close指令。一旦Rewind设置游标，接下就执行5-9这几条指令，它们的主要功能是遍历结果集，Recno把由游标P1指定的记录的关键字压入堆栈。Column指令从由P1指定的游标，P2指定的列取值。5,6,7三条指令分别把id(primary key),season和name字段的值压入栈。接下来，Callback指令从栈中取出三个值（P1），然后形成一个记录数组，存储在内存单元中 (memory cell)。Callback会停止VDBE的操作，把控制权交给sqlite3_stemp()，该函数返回sqlITE_ROW。

一旦VDBE创建了记录结构，我们就可以通过sqlite3_column_xxx() functions从记录结构的域内取出值。当下次调用sqlite3_step()时，指令指针会指向Next指令，而Next指令会把游标向移向下一行，如果有其它的记录，它会跳到由P2指定的指令，在这里为指令5，创建一个新的记录结构，一直循环，直到结果集的最后。Close指令会关闭游标，然后执行Halt指令，结束VDBE程序。

1.3、程序开始与停止
现在来看看其余的指令，Goto指令是一条跳转指令，跳到P2处，即第12条指令。指令12是Transaction，它开始一个新的事务；然后执行 VerifyCookie，它的主要功能VDBE程序编译后，数据库模式是否改变（即是否进行过更新操作）。这在sqlite中是一个很重要的概念，在 sql被sqlite3_prepare()编译成VDBE代码至程序调用sqlite3_step()执行字节码的这段时间，另一个sql命令可能会改变数据库模式（such as ALTER TABLE,DROP TABLE,or CREATE TABLE）。一旦发生这种情况，之前编译的statement就会变得无效，数据库模式信息记录在数据库文件的根页面中。类似，每一个 statement都有一份用来比较的在编译时刻该模式的备份，VerifyCookie的功能就是检查它们是否匹配，如果不匹配，将采取相关操作。

如果两者匹配，会执行下一条指令Goto；它会跳到程序的主要部分，即第一条指令，打开表读取记录。这里有两点值得注意：
(1)Transaction指令自己不会获取锁（ The Transaction instruction doesn’t acquire any locks in itself）。它的功能相当于BEGIN，而实际是由OpenRead指令获取share lock的。当事务关闭时释放锁，这取决于Halt指令，它会进行扫尾工作。
(2)statement对象（VDBE程序）所需的存储空间在程序执行前就已经确定。这有原于两个重要事实：首先，栈的深度不会比指令的数目还多（通常少得多）。其次，在执行VDBE程序之前，sqlite可以计算出为分配资源所需要的内存。

1.4指令的类型(Instruction Types)
每条指令都完成特定的任务，而且通常和别的指令有关。大体上来说，指令可分为三类：
（1)Value manipulation：这些指令通常完成算术运算，比如：add,subtract,divide；逻辑运算，比如：AND和OR；还有字符串操作。
（2)Data management：这些指令操作在内存和磁盘上的数据。内存指令进行栈操作或者在内存单元之间传递数据。磁盘操作指令控制B-tree和pager打开或操作游标，开始或结束事务，等等。

（3)Control flow：控制指令主要是移动指令指针。

1.5、程序的执行(Program execution)
最后我们来看VM解释器是如何实现以及字节代码大致是如何执行的。在vdbe.c文件中有一个很关键的函数：
//执行VDBE程序
int sqlite3VdbeExec(
Vdbe *p
)
该函数是执行VDBE程序的入口。来看看它的内部实现：


for(pc=p->pc; rc==sqlITE_OK; pc++){
//取得操作码
pOp = &p->aOp[pc];
switch( pOp->opcode ){
case OP_Goto: {
CHECK_FOR_INTERRUPT;
pc = pOp->p2 - 1;
break;
}
… …
}
}
从这段代码，我们大致可以推出VM执行的原理：VM解释器实际上是一个包含大量switch语句的for循环，每一个switch语句实现一个特定的操作指令。

写在前面:本节是前一节内容的后续部分，这两节都是从全局的角度sqlite内核各个模块的设计和功能。只有从全局上把握sqlite，才会更容易的理解sqlite的实现。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,insert.c,delete.c,trigger.c,where.c等文件。这些文件生成相应的VDBE 程序指令，比如SELECT语句就由select.c生成。下面是一个读操作中打开表的代码的生成实现：

void sqlite3OpenTableForReading(
Vdbe *v,
int iCur,
Table *pTab
){
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()结束指令生成，如下：

写在前面：从本章开始，将对sqlite的每个模块进行讨论。讨论的顺序按照我阅读sqlite的顺序来进行，由于项目的需要，以及时间关系，不能给出一个完整的计划，但是我会先讨论我认为比较重要的内容。本节讨论sqlite的事务处理技术，事务处理是DBMS中最关键的技术，对sqlite也一样，它涉及到并发控制，以及故障恢复，由于内容较多，分为两节。好了，下面进入正题。

本节通过一个具体的例子来分析sqlite原子提交的实现（基于Version 3.3.6的代码）。
CREATE TABLE episodes( id integer primary key,name text,cid int) ；
插入一条记录：insert into episodes(name,cid) values("cat",1) ;
它经过编译器处理后生成的虚拟机代码如下：
sqlite> explain insert into episodes(name,1);
0|Trace|0|0|0|explain insert into episodes(name,1);|00|
1|Goto|0|12|0||00|
2|SetNumColumns|0|3|0||00|
3|OpenWrite|0|2|0||00|
4|NewRowid|0|2|0||00|
5|Null|0|3|0||00|
6|String8|0|4|0|cat|00|
7|Integer|1|5|0||00|
8|MakeRecord|3|3|6|dad|00|
9|Insert|0|6|2|episodes|0b|
10|Close|0|0|0||00|
11|Halt|0|0|0||00|
12|Transaction|0|1|0||00|
13|VerifyCookie|0|1|0||00|
14|Transaction|1|1|0||00|
15|VerifyCookie|1|0|0||00|

16|TableLock|0|2|1|episodes|00|

17|Goto|0|2|0||00|

1、初始状态（Initial State）
当一个数据库连接第一次打开时，状态如图所示。图中最右边（“Disk”标注）表示保存在存储设备中的内容。每个方框代表一个扇区。蓝色的块表示这个扇区保存了原始数据。图中中间区域是操作系统的磁盘缓冲区。开始的时候，这些缓存是还没有被使用，因此这些方框是空白的。图中左边区域显示sqlite用户进程的内存。因为这个数据库连接刚刚打开，所以还没有任何数据记录被读入，所以这些内存也是空的。

2、获取读锁(Acquiring A Read Lock)
在sqlite写数据库之前，它必须先从数据库中读取相关信息。比如，在插入新的数据时，sqlite会先从sqlite_master表中读取数据库模式(相当于数据字典)，以便编译器对INSERT语句进行分析，确定数据插入的位置。
在进行读操作之前，必须先获取数据库的共享锁(shared lock)，共享锁允许两个或更多的连接在同一时刻读取数据库。但是共享锁不允许其它连接对数据库进行写操作。
shared lock存在于操作系统磁盘缓存，而不是磁盘本身。文件锁的本质只是操作系统的内核数据结构，当操作系统崩溃或掉电时，这些内核数据也会随之消失。

3、读取数据
一旦得到shared lock，就可以进行读操作。如图所示，数据先由OS从磁盘读取到OS缓存，然后再由OS移到用户进程空间。一般来说，数据库文件分为很多页，而一次读操作只读取一小部分页面。如图，从8个页面读取3个页面。

4、获取Reserved Lock
在对数据进行修改操作之前，先要获取数据库文件的Reserved Lock，Reserved Lock和shared lock的相似之处在于，它们都允许其它进程对数据库文件进行读操作。Reserved Lock和Shared Lock可以共存，但是只能是一个Reserved Lock和多个Shared Lock——多个Reserved Lock不能共存。所以，在同一时刻，只能进行一个写操作。
Reserved Lock意味着当前进程(连接)想修改数据库文件，但是还没开始修改操作，所以其它的进程可以读数据库，但不能写数据库。

5、创建恢复日志(Creating A Rollback Journal File)
在对数据库进行写操作之前，sqlite先要创建一个单独的日志文件，然后把要修改的页面的原始数据写入日志。回滚日志包含一个日志头(图中的绿色)——记录数据库文件的原始大小。所以即使数据库文件大小改变了，我们仍知道数据库的原始大小。
从OS的角度来看，当一个文件创建时，大多数OS(Windows,Mac OS X)不会向磁盘写入数据，新创建的文件此时位于磁盘缓存中，之后才会真正写入磁盘。如图，日志文件位于OS磁盘缓存中，而不是位于磁盘。

上面 5步的代码的实现：

其实现过程如下图所示：

主要参考：http://www.sqlite.org/atomiccommit.html

http://

blog.sina.com.cn/s/blog_506a53070100mj62.html

原文链接：https://www.f2er.com/sqlite/200513.html