SQLite 数据库文件分析

来源：筏尚旅游网

SQLite数据库文件分析

前言

性急的兄弟可以跳过前言直接看第1章，特别性急的兄弟可以跳过前面各章，直接看鸣谢。最近对SQLite数据库很感兴趣，认真地学了有半个多月了，越学越觉着好玩。好玩归好玩，只是目前没什么实际用途，那就写点儿东西吧，否则半个月不是白学了嘛！

SQLite数据库包括多方面的知识，比如VDBE什么的。据说那些东西会经常变。确实，我用的是3.6.18版，我看跟其它文档中描述的3.3.6的VDBE已经很不一样了。所以决定先写文件格式，只要是3.?.?的版本，文件格式应该不会有太大变化吧。

网上介绍SQLite文件格式的文章并不少，但一般都是针对小文件：一个表，几条记录，两个页。本文准备一直分析到比较大的文件，至少B-tree和B+tree中得有内结点(就是说不能只有一个既是根又是叶的结点，就是说表中得多点记录，得建索引)，还要争取对SQLite的各类页都做出分析。

在分析的过程中，争取把SQLite数据库关于文件格式的基本规定也都介绍一下。这样，本文既是一个综合性的技术文档，又带有实例说明，兄弟们参考时岂不是就很方便了吗？既然是技术文档，要想读懂总得先掌握点SQLite数据库的基本知识吧。所以，先介绍参考文献。

0.1 参考文献

1-The Definitive Guide to SQLite . Michael Owens：据说是比较经典的SQLite著作，我看写得是挺好的。边看边翻译了其中的主要部分，但不敢拿出来，大家还是看原文吧。

2-SQLite源代码：其实有关SQLite的最原始说明可能都在源代码中了。把此项列在第2，只是因为我是先看的书再看的代码，估计大家也会是这个顺序吧。先浏览一下代码还是很有收获的，特别是几个主要的.h文件，对本文的写作很有帮助。有关文件格式的说明主要在btreeInt.h中。

3-SQLite入门与分析：网上Arrowcat的系列文章。Arrowcat应该是一个很博学的人，看他的文章收获很大，在此也算是鸣谢吧。

4-SQLite . Chris Newman：我没看，因为也是网上能够下载到的重要资源，所以也在此列出。看目录内容应该比参考文献1简单一些，但出版日期也更早了一些。 5-NULL：在网上搜了半天，国内为什么就没有关于SQLite的好书呢？

6- http://www.sqlite.org/fileformat.html：如果这篇文章看懂了，其实我这篇东西根本就不用再看了。这是介绍SQLite文件格式的权威文档，列在最后，是因为我也是写完这篇东西后才看到的。该文档由SQLite官方网站提供，当初没看，一是因为上网少，还没仔细浏览人家的网站就开始干了(太激动)，其实归根结蒂还是因为英语不好。看到此文档这后还敢把我的东西发出来，有两个原因：一、为其他英语比我强不了多少的兄弟提供一点方便，二、我这里有例子，看起来更形象一些吧。

0.2 术语

这里不集中讨论大量术语了，那样显得太正式，还真成“文章”了。绝大多数术语都是在出现时再进行简单解释，但还是有个别概念需要先说明清楚，比如： (1) Btree、B-tree和B+tree：

Btree是为磁盘存储而优化了的一种树结构，其一般性说明可参考各类《数据结构》教材。根据实现方法的不同，Btree又分为很多类型。在SQLite中，存储表数据用的是B+tree，存储表索引用的是B-tree。由于历史原因，SQLite在3.0版以前只使用B-tree，从3.0版开始，才对表数据使用了B+tree。因此，在SQLite的官方文档中，有时B-tree表示存储表索引的B-tree，有时又是两种Btree的统称。本文中将两种Btree的概念加以了区分，而将Btree作为两种树的统称，这是与SQLite官方文档及当前大多数SQLite介绍性文档相区别的地方。 (2) auto-vacuum数据库：

一般情况下，当一个事务从数据库中删除了数据并提交后，数据库文件的大小保持不变。即使整页的数据都被删除，该页也会变成“空闲页”等待再次被使用，而不会实际地被从数据库文件中删除。执行vacuum操作，可以通过重建数据库文件来清除数据库内所有的未用空间，使数据库文件变小。但是，如果一个数据库在创建时被指定为auto_vacuum数据库，当删除事务提交时，数据库文件会自动缩小。使用auto_vacuum数据库可以节省空间，但却会增加数据库操作的时间，有利有弊。Auto_vacuum数据库需要使用附加的格式，如指针位图页，本文只讨论非auto_vacuum数据库。 (3) 数据库映像、数据库文件和日志文件：

“数据库映像”是SQLite数据库的磁盘映像。SQLite数据库存储在单一的“数据库文件”中。一般情况下，数据库映像和数据库文件是一致的，可以理解为数据库映像就是数据库文件的内容，但有例外。如果事务对数据库进行了修改，这些修改会暂存在“日志文件”中，此时可以认为数据库映像分布在数据库文件和日志文件两个文件中。日志文件有自己的格式，本文不涉及。

(4) SQLite的当前版本：

我写这篇东西时，SQLite的当前版本为3.6.18。等我写完时，已经变成3.6.19了，文件格式没变。

1 小文件的分析

1.1 准备数据库

执行SQLite的命令行工具，创建一个新的数据库food_test.db。 D:\\SQLite\\CLP>sqlite3 foods_test.db 创建一个新表。

CREATE TABLE foods( id integer primary key, type_id integer, name text ); 插入2条记录。

INSERT INTO \"foods\" VALUES(1, 1, 'Bagels');

INSERT INTO \"foods\" VALUES(2, 1, 'Bagels, raisin'); 退出命令行工具。

当前目录下多了一个文件foods_test.db，大小为2K。

现在，就可以用UltraEdit或WinHex之类的软件对其进行分析了。

1.2 SQLite文件格式

SQLite有3类数据库。除内存数据库外，SQLite把每个数据库(main或temp)都存储到一个单独的文件中。

SQLite数据库文件由固定大小的“页(page)”组成。页的大小可以在512~32768之间(包含这两个值，必须是2的指数)，默认大小为1024个字节(1KB)。页大小可以在数据库刚刚创建时设置，一旦创建了数据库对象之后，这个值就不能再改变了。

数据库中所有的页从1开始顺序编号。在具体的实现中，页号用4字节来表示(但我没搞清是否有符号位)。文件的第1个页被称为page 1，第2个页被称为page 2，依此类推。编号为0的页表示“无此页”。页的类型可以是：Btree页、空闲(free)页或溢出(overflow)页。Btree又可以是B-tree或B+tree，每一种树的结点又区分为内部页和叶子页。一个数据库文件中可能没有空闲页或溢出页，但必然有Btree页。关于Btree页的格式规定是SQLite数据库的核心内容，本文的前半部分都是在介绍Btree页。

注：其实SQLite还有两种页。一种称为“锁页(locking page)”。只有1页，位于数据库文件偏移为1G开始的地方，如果文件不足1G，就没有此页。该页是用于文件加锁的区域，不能存储数据(参源代码io.h)。好在，如果只是读数据，即使文件大于1G，也不会有指针指向此页，因此下面我们就不再提它了。另一种称为 “指针位图页(pointer-map page)”，这类页用于在auto-vacuum的数据库中存储元数据。本文不涉及auto-vacuum数据库，也就不讨论这种页了。

从逻辑上来说，一个SQLite数据库文件由多个多重Btree构成。每个Btree存储一个表的数据或一个表的索引，索引采用B-tree，而表数据采用B+tree，每个Btree占用至少一个完整的页，每个页是Btree的一个结点。每个表或索引的第1个页称为根页，所有表或索引的根页编号都存储在系统表sqlite_master中，表sqlite_master的根页为page 1。

注：sqlite_master是一个系统表，保存了数据库的schema信息，详参“关于sqlite_master表”一节。

数据库中第一个页(page 1)永远是Btree页。Page 1的前100个字节是一个对数据库文件进行描述的“文件头”。它包括数据库的版本、格式的版本、页大小、编码等所有创建数据库时设置的永久性参数。关于这个特殊文件头的文档在btreeInt.h中，具体格式如下：偏移量 0 16 18 大小 16 2 1 页大小(以字节为单位)。文件格式版本(写)。对于SQLite的当前版本，此值为1。如果该值大于1，表示文件为只读。SQLite将来版本对此域的规定可能改变。说明头字符串，如果不改源程序，此字符串永远是\"SQLite format 3\"。 19 1 文件格式版本(读)。对于SQLite的当前版本，此值为1。如果该值大于1，SQLite认为文件格式错，拒绝打开此文件。SQLite将来版本对此域的规定可能改变。每页尾部保留空间的大小。(留作它用，默认为0。) Btree内部页中一个单元最多能够使用的空间。 255意味着100%，默认值为0x40，即64(25%)，这保证了一个结点(页)至少有4个单元。 Btree内部页中一个单元使用空间的最小值。默认值为0x20，即32(12.5%)。 Btree叶子页中一个单元使用空间的最小值。默认值为0x20，即32(12.5%)。注：SQLite的当前版本规定21~23的3个字节值只能是0X402020。原来这3个字节值是可变的，从3.6.0版开始被固定下来了。文件修改计数，通常被事务使用，由事务增加其值。SQLite用此域的值验证内存缓冲区中数据的有效性。未使用。空闲页链表首指针。参“空闲页”一节。文件内空闲页的数量。 15个4字节的元数据变量。 20 21 1 1 22 23 1 1 24 28 32 36 40 4 4 4 4 60 从偏移40开始的15个4字节元数据变量在btreeInt.h中的定义如下：

40 4 Schema版本：每次schema改变(创建或删除表、索引、视图或触发器等对象，造成sqlite_master表被修改)时，此值+1。

44 4 File format of schema layer：当前允许值为1~4，超过此范围，将被认为是文件格式错。

48 4 Size of page cache。

52 4 Largest root-page (auto/incr_vacuum)：对于auto-vacuum数据库，此域为数据库中根页编号的最大值，非0。对于非auto-vacuum数据库，此域值为0。 56 4 1=UTF-8、2=UTF16le、3=UTF16be。

60 4 User version。此域值供用户应用程序自由存取，其含义也由用户定义。 64 4 Incremental vacuum mode：对于auto-vacuum数据库，如果是Incremental vacuum模式，此域值为1。否则，此域值为0。 68 4 未使用。 72 4 未使用。

用UltraEdit打开文件foods_test.db，page 1在0X0000~0X03FF。其中文件头内容如下(深蓝色部分)：

前16个字节为头字符串，程序中固定设为\"SQLite format 3\"。 0X0400：页大小，0X0400=1024字节。 0X01：文件格式版本(写)，值为1。 0X01：文件格式版本(读)，值为1。

0X40：Btree内部页中一个单元最多能够使用的空间。0X40=64，即25%。

0X20：Btree内部页中一个单元使用空间的最小值。0X20=32，即12.5%。 0X20：Btree叶子页中一个单元使用空间的最小值。0X20=32，即12.5%。

0X00000003：文件修改计数，现在已经修改了3次，分别是1次创建和两次插入。从0X20开始的4个字节：空闲页链表首指针。当前值为0，表示该链表为空。从0X24开始的4个字节：文件内空闲页的数量。当前值为0。

从0X28开始的4个字节：Schema version。当前值为0X00000001。以后，每次sqlite_master表被修改时，此值+1。

从0X38开始的4个字节：采用的字符编码。此处为0X00000001，表示采用的是UTF-8编码。

注意：在SQLite文件中，所有的整数都采用大端格式，即高位字节在前。

1.3 Btree页格式介绍 1.3.1 Btree页的分区

页的类型有Btree页、空闲页和溢出页，本文前3章介绍的都是Btree页，其他类型的页在第4、5章介绍。

每个Btree页由四个部分构成：

1．页头 2．单元指针数组 3．未分配空间 4．单元内容区首先介绍“单元”的概念：Btree页内部以单元(cell)为单位来组织数据，一个单元包含一个(或部分，当使用溢出页时)payload(也称为Btree记录)。由于各类数据大小各不相同，每个单元的大小也就是可变的，所以Btree页内部的空间需要进行动态分配(程序内部动态分配，不是动态申请空间)，单元是Btree页内部进行空间分配和回收的基本单位。页内所有单元的内容集中在页的底部，称为“单元内容区”，由下向上增长。由于单元的大小可变，因此需要对每个单元在页内的起始位置(称为单元指针)进行记录。单元指针保存在单元指针数组中，位于页头之后。单元指针数组包含0个或多个指针，由上向下增长。单元指针数组和单元内容区相向增长，中间部分为未分配空间。系统尽量保证未分配空间位于最后的指针之后，这样，就很容易增加新的单元，而不需要整理碎片。

单元不需要是相邻和有序的，但单元指针是相邻和有序的。每个指针占2个字节，表示该单元在单元内容区中距页开始处的偏移。页中单元的数量保存在页头中。

1.3.2 页头格式

页头包含用来管理页的信息，它通常位于页的开始处。对于数据库文件的page 1，页头始于

第100个字节处，因为前100个字节是文件头(file header)。页头的格式如下：偏移量 0 1 3 5 7 8 大小 1 2 2 2 1 4 第1个自由块的偏移量。本页的单元数。单元内容区的起始地址。碎片的字节数。最右儿子的页号(the Ptr(n) value)。仅内部页有此域。说明页类型标志。1: intkey, 2: zerodata, 4: leafdata, 8: leaf。下面对页头各域分别进行介绍。页类型标志：

如果leaf位被设置，则该页是一个叶子页，没有儿子；如果zerodata位被设置，则该页只有关键字，而没有数据；如果intkey位被设置，则关键字是整型；

如果leafdata位设置，则tree只存储数据在叶子页。注：

以上内容见于大多数SQLite介绍性文档，btreeInt.h中也这么说。但通过分析程序代码，并从参考文献6中得到确认，结论如下：

上述描述与实际实现是矛盾的。可以这样理解：就不用管各标志位的含义了，如果是B+tree的叶子页，该字节值为0X0D，如果是B+tree的内部页，该字节值为0X05，如果是B-tree的叶子页，该字节值为0X0A，如果是B-tree的内部页，该字节值为0X02。第1个自由块的偏移量：由于随机地插入和删除单元，将会导致一个页上单元和空闲区域互相交错。单元内容区域中没有使用的空间收集起来形成一个空闲块链表，这些空闲块按照它们地址的升序排列。页头偏移为1的2个字节指向空闲块链表的头。每个空闲块至少4个字节，因为一个空闲块的开始4个字节存储控制信息：前2个字节指向下一个空闲块(0意味着没有下一个空闲块了)，后2个字节为该空闲块的大小。碎片的字节数：

由于空闲块大小至少为4个字节，所以单元内容区中的3个字节或更小的自由空间(称为碎片，fragment)不能存在于空闲块列表中。所有碎片的总的字节数将记录在页头偏移为7的位置(碎片最多为255个字节，在它达到最大值之前，页会被整理)。单元内容区的起始地址：

单元内容区的起始地址记录在页头偏移为5的地方。这个值为单元内容区域和未使用区域的分界线。

最右儿子的页号：

如果本Btree页是叶子页，则无此域，页头长为8个字节。如果本Btree页为内部页，则有此域，页头长为12个字节。页头偏移为8的4个字节包含指向最右儿子的指针，该指针的含义将在第2章介绍。

有关Btree页格式的其它规定，将在下一节中用到时再介绍。

1.4 Page 1格式分析

Btree的基本原理这里就不详细介绍了。Btree有多种实现方法，各类《数据结构》教材中的

介绍也各不相同，但原理大同小异，随便找一本参考一下吧。最简单的Btree只有一个结点，既是根页，也是叶子页。

当前foods_test.db(大小为2K)只有两个页，都是Btree页。每个页都是一个Btree(B+tree，因为存储的是表数据)，都是上述的单结点Btree。其中page 1为系统表sqlite_master的根页，下面我们对该页进行详细分析。

1.4.1 页头分析

该页的页头从0X64=100处开始(前面100个字节是文件头)，8个字节(因为是叶子页)。如下图中深蓝色部分所示：

说明：

0X0D：说明该页为B+tree的叶子结点。

0X0000：第1个自由块的偏移量。值为0，说明当前自由块链表为空。

0X0001：本页的单元数。当前sqlite_master表中只有一条记录，所以本页当前只有1个单元。

0X0399：单元内容区的起始地址。 0X00：碎片的字节数。当前值为0。

1.4.2 单元指针数组

单元指针数组在页头之后，当前只有一个指针，为0X0399。

1.4.3 关于可变长整数

可变长整数是SQLite的特色之一，使用它既可以处理大整数，又可以节省存储空间。由于单元中大量使用可变长整数，故在此先加以介绍。

可变长整数由1~9个字节组成，每个字节的低7位有效，第8位是标志位。在组成可变长整数的各字节中，前面字节(整数的高位字节)的第8位置1，只有最低一个字节的第8位置0，表示整数结束。

可变长整数可以不到9个字节，即使使用了全部9个字节，也可以将它转换为一个64-bit整数。

下面是一些可变长整数的例子：

0x00 转换为 0x00000000 0x7f 转换为 0x0000007f 0x81 0x00 转换为 0x00000080 0x82 0x00 转换为 0x00000100 0x80 0x7f 转换为 0x0000007f 0x8a 0x91 0xd1 0xac 0x78 转换为 0x12345678 0x81 0x81 0x81 0x81 0x01 转换为 0x10204081

可变长整数可用于存储rowid、字段的字节数或Btree单元中的数据。

1.4.4 关于sqlite_master表

sqlite_master是一个系统表，保存了数据库的schema信息。在逻辑上sqlite_master包含5个字段，如下表所示：编号 1 2 3 4 5 字段 Schema item type Schema item name Associated table name The \"root page\" number The SQL statement 说明值为\"table\"、 \"index\"、 \"trigger\"或\"view\"之一。对象名称，值为字符串。如果是表或视图对象，此字段值与字段2相同。如果是索引或触发器对象，此字段值为与其相关的表名。对触发器或视图对象，此字段值为0。对表或索引对象，此字段值为其根页的编号。字符串，创建此对象时所使用的SQL语句。 1.4.5 B+tree叶子页的单元格式

单元是变长的字节串。一个单元包含一个(或部分，当使用溢出页时)payload。B+tree叶子页单元的结构如下：大小 var(1–9) var(1–9) * 4 Payload大小，以字节为单位。数据库记录的Rowid值。 Payload内容，存储数据库中某个表一条记录的数据。溢出页链表中第1个溢出页的页号。如果没有溢出页，无此域。说明结合实例来说明吧。

当前的单元内容区中只有一个单元，从0X0399开始，内容如下图所示：

0X65：Payload数据的字节数。可以看出Payload数据是从07 17 ~20 29。 0X01：foods(table对象)在sqlite_master表中对应记录的rowid，值为0X01。 Payload的格式如下图所示：

每个payload由两部分组成。第1部分是记录头，由N+1个可变长整数组成，N为记录中的字段数。第1个可变长整数(header-size)的值为记录头的字节数。跟着的N个可变长整数与记录的各字段一一对应，表示各字段的数据类型和宽度。用可变长整数表示各字段类型和宽度的规定如下表所示：类型值 0 N in 1..4 5 NULL 有符号整数有符号整数含义 0 N 6 数据宽度(字节数) 6 7 8-11 N>12的偶数 N>13的奇数有符号整数 IEEE符点数未使用 BLOB TEXT 8 8 N/A (N-12)/2 (N-13)/2 header-size的值包括header-size本身的字节和Type1~TypeN的字节。

Data1~DataN为各字段数据，与Type1~TypeN一一对应，类型和宽度由Type1~TypeN指定。本例的payload数据为：

0X07：记录头包括7个字节。

0X17：字段1。TEXT，长度为：(23-13)/2=5。值为：table。 0X17：字段2。TEXT，长度为：(23-13)/2=5。值为：foods。 0X17：字段3。TEXT，长度为：(23-13)/2=5。值为：foods。

0X01：字段4。整数，长度为1。值为：0X02。表示本表B+tree的根页编号为2。

0X8129：字段5。TEXT。0X8129为可变长整数，转换为定长为0XA9=169。可知字段长度为：(169-13)/2=78=0X4E。对应数据为下图中蓝色部分。

1.5 Page 2格式分析

Page 2为表foods的根页。foods的Btree只有一个结点，既是根页，也是叶子页。有了page 1的分析经验，page 2就好分析了。作为对上一节内容的巩固，再简单分析一下吧。用UltraEdit打开文件foods_test.db，page 2在0X0400~0X07FF。本页不再是文件首页(没有文件头)，所以页头起始于本页的开始处，其内容如下(深蓝色部分)：

因为是Btree的叶子页，所以页头只有8个字节。说明： 0X0D：说明该页为B+tree的叶子结点。

0X0000：第1个自由块的偏移量。0，说明当前自由块链表为空。 0X0002：本页的单元数。当前foods表中只有2条记录。 0X03DE：单元内容区的起始地址。 0X00：碎片的字节数。当前为0。

两个单元的指针分别为0X03F3和0X03DE。由于单元指针按次序排列，所以指针0X03F3指向本表的第1条记录，我们选择它进行分析。 0X03F3指向的单元内容如下图所示(深蓝色部分)：

说明：

0X0B：Payload数据的字节数。可以看出Payload数据是从04 00 ~6C 73，共11个字节。

0X01：本记录rowid的值为1。 Payload数据：

0X04：记录头包括4个字节。

0X00：字段1。类型为NULL(详细说明参“关于自增长的主键字段”一小节)。 0X01：字段2。1字节整数。值为01，表示本记录type_id字段的值为01。 0X19：字段3。TEXT，长度为：(25-13)/2=6。值为：Bagels。按此方法，第2条记录所对应的单元应该很容易分析了吧。

1.5.1 关于自增长的主键字段

SQLite规定：SQLite会对所有整型主键字段应用自动增长属性。个人分析，还没找到权威说明：如果一个表具有整型主键字段，如表foods具有主键字段id，则该表的id字段值即为其rowid值。对上述字段1的进一步说明是：

由于rowid值已经在单元头部保存了，所以将字段1的类型设为NULL，这样既节省空间，又容易保持数据一致性。

以上内容可以用以下语句创建一个新的数据库来验证。但请等看完下一章后再来验证这些内容吧，因为现在有关索引的内容还没介绍呢。 CREATE TABLE foods( id integer primary key, type_id integer, name text );

CREATE INDEX foods_name_idx on foods (name COLLATE NOCASE); INSERT INTO \"foods\" VALUES(1, 1, 'Bagels');

INSERT INTO \"foods\" VALUES(2, 1, 'Bagels, raisin');

INSERT INTO \"foods\" VALUES(40, 1, 'Bavarian Cream Pie'); INSERT INTO \"foods\" VALUES(30, 1, 'Bear Claws');

INSERT INTO \"foods\" (type_id,name) VALUES(1, 'Black and White cookies');

当然，如果主键字段为非整数，则rowid与主键字段值分别存储，则不存在上述问题，可用以下语句创建一个新的数据库来验证。 CREATE TABLE test( id text primary key, name text );

INSERT INTO test VALUES('aaa', 'Bagels');

INSERT INTO test VALUES('bbb', 'Bagels, raisin');

CREATE INDEX test_name_idx on test (name COLLATE NOCASE);

2 “大”文件的分析

前面分析的数据库文件只有2个页，每个页自成一个Btree，每个Btree只有一个结点，既是根页，也是叶子页。所以，至此，我们还没见过Btree的内部页呢。

2.1 准备数据库

向表foods继续插入记录。

INSERT INTO \"foods\" VALUES(3, 1, 'Bavarian Cream Pie'); INSERT INTO \"foods\" VALUES(4, 1, 'Bear Claws');

INSERT INTO \"foods\" VALUES(5, 1, 'Black and White cookies'); INSERT INTO \"foods\" VALUES(6, 1, 'Bread (with nuts)'); INSERT INTO \"foods\" VALUES(7, 1, 'Butterfingers'); INSERT INTO \"foods\" VALUES(8, 1, 'Carrot Cake');

INSERT INTO \"foods\" VALUES(9, 1, 'Chips Ahoy Cookies'); INSERT INTO \"foods\" VALUES(10, 1, 'Chocolate Bobka'); INSERT INTO \"foods\" VALUES(11, 1, 'Chocolate Eclairs'); INSERT INTO \"foods\" VALUES(12, 1, 'Chocolate Cream Pie'); INSERT INTO \"foods\" VALUES(13, 1, 'Cinnamon Bobka'); INSERT INTO \"foods\" VALUES(14, 1, 'Cinnamon Swirls'); INSERT INTO \"foods\" VALUES(15, 1, 'Cookie'); INSERT INTO \"foods\" VALUES(16, 1, 'Crackers'); INSERT INTO \"foods\" VALUES(17, 1, 'Cupcake'); INSERT INTO \"foods\" VALUES(18, 1, 'Cupcakes');

INSERT INTO \"foods\" VALUES(19, 1, 'Devils Food Cake'); INSERT INTO \"foods\" VALUES(20, 1, 'Dinky Donuts'); INSERT INTO \"foods\" VALUES(21, 1, 'Dog biscuits'); INSERT INTO \"foods\" VALUES(22, 1, 'Donuts');

INSERT INTO \"foods\" VALUES(23, 1, 'Drakes Coffee Cakes'); INSERT INTO \"foods\" VALUES(24, 1, 'Entenmann''s Cake'); INSERT INTO \"foods\" VALUES(25, 1, 'Kaiser Rolls'); INSERT INTO \"foods\" VALUES(26, 1, 'Marble Ryes'); INSERT INTO \"foods\" VALUES(27, 1, 'Mini Ritz'); INSERT INTO \"foods\" VALUES(28, 1, 'Muffin');

INSERT INTO \"foods\" VALUES(29, 1, 'Muffin Tops'); INSERT INTO \"foods\" VALUES(30, 1, 'Muffin Stumps'); INSERT INTO \"foods\" VALUES(31, 1, 'Nut Bread');

INSERT INTO \"foods\" VALUES(32, 1, 'Pastries (of the Gods)'); INSERT INTO \"foods\" VALUES(33, 1, 'Peach Muffin');

INSERT INTO \"foods\" VALUES(34, 1, 'Peppridge Farms Cookies (Milanos)'); INSERT INTO \"foods\" VALUES(35, 1, 'Pizza Bagels'); INSERT INTO \"foods\" VALUES(36, 1, 'Pie');

INSERT INTO \"foods\" VALUES(37, 1, 'Pie (blueberry)');

INSERT INTO \"foods\" VALUES(38, 1, 'Pie (Blackberry) Pie'); INSERT INTO \"foods\" VALUES(39, 1, 'Pie (Boysenberry)'); INSERT INTO \"foods\" VALUES(40, 1, 'Pie (Huckleberry)'); INSERT INTO \"foods\" VALUES(41, 1, 'Pie (Raspberry)'); INSERT INTO \"foods\" VALUES(42, 1, 'Pie (Strawberry)'); INSERT INTO \"foods\" VALUES(43, 1, 'Pie (Cranberry)');

INSERT INTO \"foods\" VALUES(44, 1, 'Pie (Peach)');

INSERT INTO \"foods\" VALUES(45, 1, 'Poppy Seed Muffins'); INSERT INTO \"foods\" VALUES(46, 1, 'Triscuits');

INSERT INTO \"foods\" VALUES(47, 1, 'Wedding Cake (Royal)'); INSERT INTO \"foods\" VALUES(48, 2, 'Bran'); INSERT INTO \"foods\" VALUES(49, 2, 'Cheerios'); INSERT INTO \"foods\" VALUES(50, 2, 'Corn Flakes'); INSERT INTO \"foods\" VALUES(51, 2, 'Double Crunch'); INSERT INTO \"foods\" VALUES(52, 2, 'Fruit Loops'); INSERT INTO \"foods\" VALUES(53, 2, 'Grape Nuts'); INSERT INTO \"foods\" VALUES(54, 2, 'Honey Combs'); INSERT INTO \"foods\" VALUES(55, 2, 'Kasha'); INSERT INTO \"foods\" VALUES(56, 2, 'Kix'); INSERT INTO \"foods\" VALUES(57, 2, 'Life');

INSERT INTO \"foods\" VALUES(58, 2, 'Pancakes');

INSERT INTO \"foods\" VALUES(59, 2, 'Reese''s Peanut-Butter Puffs'); INSERT INTO \"foods\" VALUES(60, 2, 'Rice Krispies'); INSERT INTO \"foods\" VALUES(61, 2, 'Special K');

INSERT INTO \"foods\" VALUES(62, 2, 'Tightly Wrapped Magic Pan Crepes'); INSERT INTO \"foods\" VALUES(63, 3, 'Broiled Chicken'); INSERT INTO \"foods\" VALUES(64, 3, 'Casserole'); INSERT INTO \"foods\" VALUES(65, 3, 'Chicken');

INSERT INTO \"foods\" VALUES(66, 3, 'Chicken (for wedding)');

INSERT INTO \"foods\" VALUES(67, 3, 'Chicken Cashew (not ordered)'); INSERT INTO \"foods\" VALUES(68, 3, 'Chicken Kiev');

INSERT INTO \"foods\" VALUES(69, 3, 'Kung-Pao Chicken'); INSERT INTO \"foods\" VALUES(70, 3, 'Chicken Marsala'); INSERT INTO \"foods\" VALUES(71, 3, 'Chicken Piccata');

INSERT INTO \"foods\" VALUES(72, 3, 'Chicken with Poppy Seeds');

INSERT INTO \"foods\" VALUES(73, 3, 'Chicken, whole stuffed w/Gorganzolla and Ham'); INSERT INTO \"foods\" VALUES(74, 3, 'Chicken Skins');

INSERT INTO \"foods\" VALUES(75, 3, 'Chicken Wing (Shoulder Blades)'); INSERT INTO \"foods\" VALUES(76, 3, 'Chicken (Kenny Rogers) '); INSERT INTO \"foods\" VALUES(77, 3, 'Chicken (Tyler) ');

INSERT INTO \"foods\" VALUES(78, 3, 'Colonel Chang Chicken'); INSERT INTO \"foods\" VALUES(79, 3, 'Cornish Game Hen'); INSERT INTO \"foods\" VALUES(80, 3, 'Duck');

INSERT INTO \"foods\" VALUES(81, 3, 'Duck, juicy breasts of'); INSERT INTO \"foods\" VALUES(82, 3, 'Turkey');

INSERT INTO \"foods\" VALUES(83, 3, 'Turkey, Kramer'); INSERT INTO \"foods\" VALUES(84, 3, 'Turkey Jerky'); INSERT INTO \"foods\" VALUES(85, 3, 'Turkey Chili'); INSERT INTO \"foods\" VALUES(86, 4, 'A1 Sauce');

INSERT INTO \"foods\" VALUES(87, 4, 'Barbeque Sauce');

INSERT INTO \"foods\" VALUES(88, 4, 'Dijon Mustard'); INSERT INTO \"foods\" VALUES(89, 4, 'Dill'); INSERT INTO \"foods\" VALUES(90, 4, 'Ginger'); INSERT INTO \"foods\" VALUES(91, 4, 'Gravy');

INSERT INTO \"foods\" VALUES(92, 4, 'Honey Mustard');

INSERT INTO \"foods\" VALUES(93, 4, 'Ketchup and Mustard together'); INSERT INTO \"foods\" VALUES(94, 4, 'Ketchup');

INSERT INTO \"foods\" VALUES(95, 4, 'Ketchup (secret)'); INSERT INTO \"foods\" VALUES(96, 4, 'Maple Syrup'); INSERT INTO \"foods\" VALUES(97, 4, 'Mustard (fancy)'); INSERT INTO \"foods\" VALUES(98, 4, 'Parsley'); INSERT INTO \"foods\" VALUES(99, 4, 'Pepper'); INSERT INTO \"foods\" VALUES(100, 4, 'Pesto');

列出上述命令，是为了兄弟们自行验证时方便。现在表内有100条记录，文件大小为5K，说明foods表在文件中占4个页，其B+tree的逻辑结构如下图所示： Page 2，内部页。 Page 3，叶子页。 Page 4，叶子页。 Page 5，叶子页。用UltraEdit打开文件foods_test.db，观察文件头，其内容如下(深蓝色部分)：

与前文比较，文件头内容基本无变化，只有偏移为24处的文件修改计数变成了0X00000065，表示现在文件已经修改了101次，包括1次创建和100次插入。 Page 1其他部分无变化。

2.2 B+tree内部页格式介绍

Page 2仍然是表foods的根页，但已经变成了内部页，格式有较大的变化。

对于数据库表，从SQLite3开始采用了B+tree，在此，先对B+tree的结构做一个简单介绍。B+tree与B-tree的主要区别在于，B-tree的所有页上都包含数据，而B+tree的数据只存在于叶子页上，内部页只存储导航信息。B+tree所有的叶子页都在同一层上，并按关键字排序，所有的关键字必须唯一，其逻辑结构举例如下图所示：

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

我们将根页和内部页统称为内部页，它们的结构是相同的，其逻辑结构如下： ---------------------------------------------------------------- | Ptr(0) | Key(0) | Ptr(1) | Key(1) | ... | Key(N-1) | Ptr(N) | ---------------------------------------------------------------- 内部页包含N个关键值(Key(0)~ Key(N-1))和N+1个子页指针(Ptr(0)~ Ptr(N))，其值为子页的页号。其中，Ptr(N)存储在页头中偏移为8的地方(4字节整数，只有内部页的页头有此域，参“Btree页格式介绍”一节)。其他的每对子页指针和关键值(Ptr(i) 和Key(i))组成1个单元，共N个单元。Ptr(i) 所指向子树中关键字的最大值<=Key(i)，Ptr(N) 所指向子树中关键字的值都>Key(N-1)。

2.3 B+tree内部页格式分析

现在对foods B+tree仅有的内部页进行分析。文件第2页页头的内容如下：(图中深蓝色部分)

前文对页头格式已经有比较详细的介绍，这里不再赘述。直接对内容进行说明： 0X05：说明该页为B+tree的内部页。

0X0000：第1个自由块的偏移量。此处为0，表示本页没自由块。 0X0002：本页有2个单元。

0X03F6：单元内容区的起始位置。 0X00：碎片的字节数，此处为0。

0X00000005：最右儿子的页号，即Ptr(N)。由于本页有2个单元，所以此处即Ptr(2)。其值为0X05，即Ptr(2)指向第5页。第5页是表数据的最后一页，也是当前文件的最后一页。

单元指针数组在页头之后，有2个指针，分别为0X03FB和0X03F6。

注意：这两个指针后面还有一些乱七八糟内容，我也曾为此迷惑过。这些不是指针，而是属于“未分配空间”的一部分。因为此页在还没有成为内部页(还是叶子页)时，曾经插入过不少记录，有过不少指针。现在成为内部页了，只使用两个指针，但以前使用过的空间也没必要清零，再次使用时自然会覆盖。提示：此页尾部的内容区也存在这个情况，不再单独解释。

下面来看单元内容区的数据，内容如下：(图中深蓝色部分)

由于单元内容区中各单元是反向增长的，所以两个单元的数据分别为： 0X00000003，0X2C 0X00000004，0X56

每个单元包括两部分内容：

一个4字节的页号，指向相应的儿子，即Ptr(i)。此处分别指向第3页和第4页。

一个可变长整数，即Key(i)。0X2C表示最左儿子(文件第3页)中关键字值都<=0X2C。0X56表示第2个儿子(文件第4页)中关键字都>0X2C，都<=0X56。注意：关键字值使用可变长整数，我们插入的记录少，在此都只有1个字节，所以看不出来。

前文刚介绍过，最右儿子的页号存储在页头中，值为0X00000005，说明第5页中关键字值都>0X56。

重画前文B+tree的逻辑结构图如下所示： Ptr(0) 3 Key(0) 0X2C Ptr(1) 4 Key(1) 0X56 Ptr(2) 5 Page 3，Key<=0X2C Page 4，Key<=0X56 Page 5，Key>0X56 2.4 叶子页格式分析

其实在上一章中分析page 1和page 2时，这两个页都是叶子页。这里再次对叶子页的格式进行分析，主要是为了验证前一节对内部页的分析结果，所以，咱就别嫌麻烦了。文件第4页页头的内容如下：(图中深蓝色部分)

之所以选择第4页，是因为该页为中间叶子，其记录的关键值应该在Key(0)和Key(1)之间。从上图可以看出，本页有0X2A=42个单元。第1个单元的入口地址为0X03E7，最后一个单元的入口地址为0X006F。 0X03E7单元的内容为：

这是本页关键值最小的记录，可以看出其rowid值为0X2D，恰大于0X2C。 0X006F单元的内容为：

这是本页关键值最大的记录，可以看出其rowid值为0X56=0X56。

3 索引格式分析

前面分析的都是表数据页的格式。表数据用B+tree来存储，而索引用B-tree来存储。两者的区别主要是：B-tree中只存储关键字段的值和对应记录的rowid值；B-tree树中的内部页也可以存储数据。

3.1 准备数据库

为表创建一个索引。

CREATE INDEX foods_name_idx on foods (name COLLATE NOCASE);

创建索引后文件大小为9K，说明索引有4个页，其B-tree的逻辑结构如下图所示： Page 6，内部页。 Page 7，叶子页。 Page 8，叶子页。 Page 9，叶子页。此处4个页是连续的，如果在创建表时同时创建索引，然后再插入记录，则用于存储数据的页和用于存储索引的页应该是交叉的。

此时观察page 1的内容，单元指针数组中多了一个单元指针，sqlite_master表中多了索引对象记录，从其数据可以看出其根页为第6页。另外，Schema版本的值变成了2。

3.2 索引页的内部页

现在我们对索引B-tree唯一内部页(也就是根页，文件第6页)的格式进行分析。文件第6页页头的内容如下：(图中深蓝色部分)

说明：

0X02：说明该页为B-tree的内部页。

0X0000：第1个自由块的偏移量。0，说明当前自由块链表为空。 0X0002：本页有2个单元。

0X03DC：单元内容区的起始位置为0X03DC。 0X00：碎片的字节数，当前为0。

0X00000009：最右儿子的页号，即Ptr(N)。由于本页有2个单元，所以此处即Ptr(2)。其值为0X09，即Ptr(2)指向第9页。第9页是索引数据的最后一页，也是当前文件的最后一页。

单元指针数组在页头之后，有2个指针，分别为0X03F1和0X03DC。

下面来看单元内容区的数据。

0X03F1单元的内容如下：(图中深蓝色部分)

0X00000007：为Ptr(0)，指向第7页。

0X0A：Payload数据的字节数。数据从03~0F。 0X03：记录头包括3个字节。

0X19：字段1。TEXT，长度为：(25-13)/2=6。字段值为：cookie。

0X01：字段2。整数，长度为1。字段值为：0X0F，表示索引值cookie所对应记录的关键值(即记录的rowid值)为15。

注：如果是通过索引字段查找“cookie”，现在就可以按其rowid值=15到数据B+tree树中去检索记录的全部数据了。

0X03DC单元的内容如下：(图中深蓝色部分)

0X00000008：为Ptr(1)，指向第8页。

0X10：Payload数据的字节数。数据从03~21。 0X03：记录头包括3个字节。

0X25：字段1。TEXT，长度为：(37-13)/2=12。字段值为：Peach Muffin。

0X01：字段2。整数，长度为1。字段值为：0X21，表示索引值Peach Muffin所对应记录的关键值为33。

3.3 索引页的叶子页格式

对于B-tree来说，内部页与叶子页的格式差别其实不大。简单分析一下，为了验证上一节的结果。

文件第8页前半部分的内容如下：

页头的第1个字节值为0X0A，说明该页为B-tree的叶子页。其它不再详述。

单元内容区的开始部分内容如下：

单元内容区的开始和结束部分内容如下：

不再详细分析了，粗看可以看出：

此页记录的索引值确实都在cookie和Peach Muffin之间，不包括这两个值(这两个值已经在根页中了)。单元数据都按索引值大小排序。

4 碎片、自由块和空闲页

到目前为止，我们只对数据库表进行了插入操作，因此，文件格式还是很“整齐”的。如果对数据库进行删除和修改操作，就会产生碎片、自由块和空闲页。本文1.2节和1.3节对相应的概念有较详细介绍，本章就算是对前述内容的例证吧。

4.1 碎片

执行下面的update语句，每执行一句都将原记录的name字段长度减少2字节(可与前文的insert语句对照)。

update foods set name='Bavarian Cream P' where id=3;

执行完上面语句后，文件第3页的页头内容如下图所示：

可以看到，偏移为7的字节值变成了2，说明当前页中有2字节的碎片。再执行下面语句： update foods set name='Bear Cla' where id=4;

可以看到当前页中的碎片字节数已经变成了4，如下图所示：

至于碎片字节数到多大才会整理，这得分析源程序了。

4.2 自由块

执行下面删除语句：

delete from foods where id=5; 文件第3页的页头内容如下：

可以看到，第1个自由块的偏移量为0X0396。观察0X0396处的单元，数据如下图所示：

单元的前2个字节指向下一个空闲块，此处值为0，表示没有下一个空闲块了。 0X001E表示该空闲块的大小，从数值上来分析，应该是包含了这两个字节本身。如果再删除1条记录，就可以看到自由块是如何串接的，我们就不做了。

4.3 空闲页

执行下面删除语句：

delete from foods where id>10; 文件大小仍为9K，但此时文件中应该有了6个空闲页(索引和数据都只需要一个页就能放下了)，分别是页3、4、5、7、8和页9。观察此时的文件头，内容为：

注意其中深蓝色部分，可以看到，偏移为32的4个字节中值为0X00000005，表示空闲页链表首指针指向第5个页。对了，就应该是第5个页先空闲出来。

偏移为36的4个字节中值为0X00000006，表示文件中空闲页的数量为6。

现在得介绍一下空闲页链表的格式了。空闲页有两种类型：trunk page(主干页)和leaf page(叶子页)。文件头偏移为32处的指针指向空闲链表的第一个trunk page，每个trunk page指向多个叶子页。偏移36处的4个字节为空闲页的总数量，包括所有的trunk page和leaf page。空闲页链表的结构如下图所示：

文件头空闲页链表首指针 trunk page 下一个trunk page leaf page数量 … trunk page 下一个trunk page leaf page数量 … … trunk page 下一个trunk page leaf page数量 … leaf page leaf page … leaf page 其中，trunk page的格式(从页的起始处开始)如下：

(1)4个字节，指向下一个trunk page的页号，0表示链表结束； (2)4个字节，该页leaf page的数量；

(3)0个或多个指向leaf page的页号，每项4个字节。

文件第6页前部的内容如下：

说明：

下一个trunk page的页号为0X00000000，表示链表中只有此一个trunk page，没有后继结点了。

该页leaf page的数量为0X00000005，表示本页带有5个leaf page，依次为0X00000009，0X00000008，0X00000007、0X00000004和0X00000003。

SQLite对leaf page的格式没有规定。

5 溢出页的格式

5.1 溢出页格式说明

如前所述，单元(cell)具有可变的大小，而页的大小是固定的，这就有可能一个单元比一个完整的页还大，这样的单元就会溢出到由溢出页组成的链表上，如下图所示：

Btree页单元头 Payload 单元头 Payload(第1部分) 溢出页号溢出页号溢出页 Payload(第2部分) … 0 溢出页 Payload(最后部分) 在上图中，Btree页的最后一个单元超大，需要使用溢出页。此时，单元的最后4个字节为溢出页链表中第1个溢出页的页号。对于每个溢出页，其头4个字节为下一溢出页的页号，该值为0时表示此页为溢出页链表的表尾页。

除最后一个溢出页外，每个溢出页全部填充数据(除了最开始的4个字节)。最后一个溢出页可能数据很少，甚至只有一个字节的数据，但一个溢出页不会存储来自两个单元的数据。

5.2 准备数据库

得换一个数据库了。我们用下面的方法来分析溢出页的格式，并对上节内容进行验证。执行SQLite的命令行工具，创建一个新的数据库food_text.db。 D:\\SQLite\\CLP>sqlite3 foods_text.db 创建一个新表。

CREATE TABLE foods( id integer primary key, type_id integer, name text );

插入1条记录，该记录包含一段较长的文本。 INSERT INTO \"foods\" VALUES(1, 1,

'0000000001000000000200000000030000000004000000009 0000000001000000000200000000030000000004000000009

0000000001000000000200000000030000000004000000009 0000000001000000000200000000030000000004000000009 0000000001000000000200000000030000000004000000009 0000000001000000000200000000030000000004000000009 0000000001000000000200000000030000000004000000009 0000000001000000000200000000030000000004000000009 0000000001000000000200000000030000000004000000009 0000000001000000000200000000030000000004000000009 0000000001000000000200000000030000000004000000009 0000000001000000000200000000030000000004000000009 0000000001000000000200000000030000000004000000009 0000000001000000000200000000030000000004000000009 0000000001000000000200000000030000000004000000009 0000000001000000000200000000030000000004000000009 0000000001000000000200000000030000000004000000009 0000000001000000000200000000030000000004000000009 0000000001000000000200000000030000000004000000009 0000000001000000000200000000030000000004000000009 0000000001000000000200000000030000000004000000009 ');

该记录的文本字段包括21行，每行50字节(49字符+1换行)，共1050个字节。

退出命令行工具。当前目录下多了一个文件foods_text.db，大小为3K，其中第3页应该为溢出页。

5.3 溢出页格式分析

用UltraEdit打开foods_text.db文件，对其进行分析。文件第2页前部内容如下图所示：

可以看出，该表唯一的记录单元始于0X0392。0X0392单元的内容如下图所示：

0X8820是可变长整数，其值：

0X8820=0B1000,1000,0010,0000转换为整数=0B100,0010,0000=4*256+2*16=1056。说明数据区(从0X0500开始)长度为1056，显然需要使用溢出页。 0X01：当前记录的rowid，值为0X01。 0X05：记录头包括5个字节。

0X00：字段1。类型为NULL(详细说明参“关于自增长的主键字段”一小节)。

0X01：字段2。1字节整数。对应的数据值为01，表示本记录type_id字段的值为01。

0X9041(可变长整数)：字段3。TEXT，长度为：(2113-13)/2=1050，与插入文本值的长度相符。

本单元最后4个字节为0X00000003，表示第1个溢出页的页号为3。文件第3页前部内容如图所示：

头4个字节值为0，表示此页后面再无溢出页。