SQLite数据库文件格式全面分析

SQLiteSQLiteSQLiteSQLite数据库文件格式全面分析 0000 前言 性急的兄弟可以跳过前言直接看第 1 章，特别性急的兄弟可以跳过前面各章，直接看鸣谢。 SQLite 数据库包括多方面的知识，比如 VDBE 什么的。据说那些东西会经常变。确实，我 用的是 3.6.18 版，我看跟其它文档中描述的 3.3.6 的 VDBE 已经很不一样了。所以决定先写 文件格式，只要是 3.?.?的版本，文件格式应该不会有太大变化吧。 网上介绍 SQLite 文件格式的文章并不少，但一般都是针对小文件：一个表，几条，两 个页。本文准备一直分析到比较大的文件，至少 B-tree 和 B+tree 中得有内结点(就是说不能 只有一个既是根又是叶的结点，就是说表中得多点记录，得建索引)，还要争取对 SQLite 的 各类页都做出分析。 在分析的过程中，争取把 SQLite 数据库关于文件格式的基本规定也都介绍一下。这样，本 文既是一个综合性的技术文档，又带有实例说明，兄弟们参考时岂不是就很方便了吗？ 既然是技术文档，要想读懂总得先掌握点 SQLite 数据库的基本知识吧。所以，先介绍参考 文献。 0.10.10.10.1 参考文献参考文献参考文献参考文献 1-The Definitive Guide to SQLite . Michael Owens：比较经典的 SQLite 著作。我边看边翻译了 其中的部分内容，但翻得不好，大家还是看原文吧。 2-SQLite 源代码：有关 SQLite 的最原始说明都在源代码中了。先浏览一下代码还是很有收 获的，特别是几个主要的.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.20.20.20.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 数据库需要使用附加的格式，如指针图页 （本文第 6 章有介绍），本文重点讨论非 auto_vacuum 数据库。 (3) 数据库映像、数据库文件和日志文件： “数据库映像”是 SQLite 数据库的磁盘映像。SQLite 数据库存储在单一的“数据库文件” 中。一般情况下，数据库映像和数据库文件是一致的，可以理解为数据库映像就是数据库文 件的内容，但有例外。如果事务对数据库进行了修改，这些修改会暂存在“日志文件”中， 此时可以认为数据库映像分布在数据库文件和日志文件两个文件中。日志文件有自己的格 式，本文第 7 章专门介绍。 (4) SQLite 的当前版本： 我开始写这篇东西时，SQLite 的当前版本为 3.6.18。现在已经变成 3.6.20 了，文件格式没变。 1111 小文件的分析 1.11.11.11.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.21.21.21.2 SQLiteSQLiteSQLiteSQLite文件格式文件格式文件格式文件格式 SQLite 有 3 类数据库。除内存数据库外，SQLite 把每个数据库(main 或 temp)都存储到一个 单独的文件中。 SQLite 数据库文件由固定大小的“页(page)”组成。页的大小可以在 512~32768 之间(包含 这两个值，必须是 2 的指数)，默认大小为 1024 个字节(1KB)。页大小可以在数据库刚刚创 建时设置，一旦创建了数据库对象之后，这个值就不能再改变了。 数据库中所有的页从 1 开始顺序编号。在具体的实现中，页号用 4 字节来表示，并限制最大 页号不得超过 2^31(参 pager.c)。文件的第 1 个页被称为 page 1，第 2 个页被称为 page 2，依 此类推。编号为 0 的页表示“无此页”。 注：关于一个数据库文件中可以有多少个页，SQLite 是这样实现的：为了限制数据库文件 的大小（不要太大），SQLite 在程序中对文件页数进行了限制，文件页数的最大值默认为 1073741823，在 sqliteLimit.h 中定义，可以在运行时改变。 页的类型可以是：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 头字符串，如果不改源程序，此字符串永远是"SQLite format 3"。 16 2 页大小(以字节为单位)。 18 1 文件格式版本(写)。对于 SQLite 的当前版本，此值为 1。如果该值大于 1， 表示文件为只读。SQLite 将来版本对此域的规定可能改变。 19 1 文件格式版本(读)。对于 SQLite 的当前版本，此值为 1。如果该值大于 1， SQLite 认为文件格式错，拒绝打开此文件。SQLite 将来版本对此域的规 定可能改变。 20 1 每页尾部保留空间的大小。(留作它用，默认为 0。) 21 1 Btree 内部页中一个单元最多能够使用的空间。 255 意味着 100%，默认值为 0x40，即 64(25%)，这保证了一个结点(页) 至少有 4 个单元。 22 1 Btree 内部页中一个单元使用空间的最小值。默认值为 0x20，即32(12.5%)。 23 1 Btree 叶子页中一个单元使用空间的最小值。默认值为 0x20，即32(12.5%)。 注：SQLite 的当前版本规定 21~23 的 3 个字节值只能是 0X402020。原来 这 3 个字节值是可变的，从 3.6.0 版开始被固定下来了。 24 4 文件修改计数，通常被事务使用，由事务增加其值。SQLite 用此域的值 验证内存缓冲区中数据的有效性。 28 4 未使用。 32 4 空闲页链表首指针。参“空闲页”一节。 36 4 文件内空闲页的数量。 40 60 15 个 4 字节的元数据变量。 从偏移 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.31.31.31.3 BtreeBtreeBtreeBtree页格式介绍页格式介绍页格式介绍页格式介绍 1.3.11.3.11.3.11.3.1 BtreeBtreeBtreeBtree 页的分区 页的类型有 Btree 页、空闲页和溢出页，本文前 3 章介绍的都是 Btree 页，其他类型的页在 第 4、5 章介绍。 每个 Btree 页由四个部分构成： 1．页头 2．单元指针数组 3．未分配空间 4．单元内容区 首先介绍“单元”的概念：Btree 页内部以单元(cell)为单位来组织数据，一个单元包含一个(或 部分，当使用溢出页时)payload(也称为 Btree 记录)。由于各类数据大小各不相同，每个单元 的大小也就是可变的，所以 Btree 页内部的空间需要进行动态分配(程序内部动态分配，不是 动态申请空间)，单元是 Btree 页内部进行空间分配和回收的基本单位。 页内所有单元的内容集中在页的底部，称为“单元内容区”，由下向上增长。由于单元的大 小可变，因此需要对每个单元在页内的起始位置(称为单元指针)进行记录。单元指针保存在 单元指针数组中，位于页头之后。单元指针数组包含 0 个或多个指针，由上向下增长。 单元指针数组和单元内容区相向增长，中间部分为未分配空间。系统尽量保证未分配空间位 于最后的指针之后，这样，就很容易增加新的单元，而不需要整理碎片。 单元不需要是相邻和有序的，但单元指针是相邻和有序的。每个指针占 2 个字节，表示该单 元在单元内容区中距页开始处的偏移。页中单元的数量保存在页头中。 1.3.21.3.21.3.21.3.2 页头格式 页头包含用来管理页的信息，它通常位于页的开始处。对于数据库文件的 page 1，页头始于 第 100 个字节处，因为前 100 个字节是文件头(file header)。 页头的格式如下： 偏移量 大小 说明 0 1 页类型标志。1: intkey, 2: zerodata, 4: leafdata, 8: leaf。 1 2 第 1 个自由块的偏移量。 3 2 本页的单元数。 5 2 单元内容区的起始地址。 7 1 碎片的字节数。 8 4 最右儿子的页号(the Ptr(n) value)。仅内部页有此域。 下面对页头各域分别进行介绍。 页类型标志： 如果 leaf 位被设置，则该页是一个叶子页，没有儿子； 如果 zerodata 位被设置，则该页只有关键字，而没有数据； 如果 intkey 位被设置，则关键字是整型； 如果 leafdata 位设置，则 tree 只存储数据在叶子页。 注： 以上内容见于大多数 SQLite 介绍性文档，btreeInt.h 中也这么说。但通过分析程序代码，并 从参考文献 6 中得到确认，结论如下： 上述描述与实际实现是矛盾的。可以这样理解：就不用管各标志位的含义了，如果是 B+tree 的叶子页，该字节值为 0X0D，如果是 B+tree 的内部页，该字节值为 0X05，如果是 B-tree 的叶子页，该字节值为 0X0A，如果是 B-tree 的内部页，该字节值为 0X02。由此可见：intkey 标志倒是可以作为判断 B+tree 树和 B-tree 的标志（置 1 为 B+tree 树），程序中实际也是这样 应用的。 第 1 个自由块的偏移量： 由于随机地插入和删除单元，将会导致一个页上单元和空闲区域互相交错。单元内容区域中 没有使用的空间收集起来形成一个空闲块链表，这些空闲块按照它们地址的升序排列。页头 偏移为 1 的 2 个字节指向空闲块链表的头。每个空闲块至少 4 个字节，因为一个空闲块的开 始 4 个字节存储控制信息：前 2 个字节指向下一个空闲块(0 意味着没有下一个空闲块了)， 后 2 个字节为该空闲块的大小。 碎片的字节数： 由于空闲块大小至少为 4 个字节，所以单元内容区中的 3 个字节或更小的自由空间(称为碎 片，fragment)不能存在于空闲块列表中。所有碎片的总的字节数将记录在页头偏移为 7 的位 置(碎片最多为 255 个字节，在它达到最大值之前，页会被整理)。 单元内容区的起始地址： 单元内容区的起始地址记录在页头偏移为 5 的地方。这个值为单元内容区域和未使用区域的 分界线。 最右儿子的页号： 如果本 Btree 页是叶子页，则无此域，页头长为 8 个字节。如果本 Btree 页为内部页，则有 此域，页头长为 12 个字节。页头偏移为 8 的 4 个字节包含指向最右儿子的指针，该指针的 含义将在第 2 章介绍。 有关 Btree 页格式的其它规定，将在下一节中用到时再介绍。 1.41.41.41.4 PagePagePagePage 1111格式分析格式分析格式分析格式分析 Btree 的基本原理这里就不详细介绍了。Btree 有多种实现方法，各类《数据结构》教材中的 介绍也各不相同，但原理大同小异，随便找一本参考一下吧。最简单的 Btree 只有一个结点， 既是根页，也是叶子页。 当前 foods_test.db(大小为 2K)只有两个页，都是 Btree 页。每个页都是一个 Btree(B+tree，因 为存储的是表数据)，都是上述的单结点 Btree。其中 page 1 为系统表 sqlite_master 的根页， 下面我们对该页进行详细分析。 1.4.11.4.11.4.11.4.1 页头分析 该页的页头从 0X64=100 处开始(前面 100 个字节是文件头)，8 个字节(因为是叶子页)。如下 图中深蓝色部分所示： 说明： 0X0D：说明该页为 B+tree 的叶子结点。 0X0000：第 1 个自由块的偏移量。值为 0，说明当前自由块链表为空。 0X0001：本页的单元数。当前 sqlite_master 表中只有一条记录，所以本页当前只有 1 个单元。 0X0399：单元内容区的起始地址。 0X00：碎片的字节数。当前值为 0。 1.4.21.4.21.4.21.4.2 单元指针数组 单元指针数组在页头之后，当前只有一个指针，为 0X0399。 1.4.31.4.31.4.31.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.41.4.41.4.41.4.4 关于 sqlite_mastersqlite_mastersqlite_mastersqlite_master 表 sqlite_master 是一个系统表，保存了数据库的 schema 信息。在逻辑上 sqlite_master 包含 5 个 字段，如下表所示： 编号 字段 说明 1 type 值为"table"、 "index"、 "trigger"或"view"之一。 2 name 对象名称，值为字符串。 3 tbl_name 如果是表或视图对象，此字段值与字段 2 相同。如果是索引或触发 器对象，此字段值为与其相关的表名。 4 rootpage 对触发器或视图对象，此字段值为 0。对表或索引对象，此字段值 为其根页的编号。 5 SQL 字符串，创建此对象时所使用的 SQL 语句。 1.4.51.4.51.4.51.4.5 B+treeB+treeB+treeB+tree 叶子页的单元格式 单元是变长的字节串。一个单元包含一个(或部分，当使用溢出页时)payload。B+tree 叶子页 单元的结构如下： 大小 说明 var(1–9) Payload 大小，以字节为单位。 var(1–9) 数据库记录的 Rowid 值。 * Payload 内容，存储数据库中某个表一条记录的数据。 4 溢出页链表中第 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 NULL 0 N in 1..4 有符号整数 N 5 有符号整数 6 6 有符号整数 8 7 IEEE 符点数 8 8-11 未使用 N/A N>12 的偶数 BLOB (N-12)/2 N>13 的奇数 TEXT (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.51.51.51.5 PagePagePagePage 2222格式分析格式分析格式分析格式分析 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.11.5.11.5.11.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); 2222 “大”文件的分析 前面分析的数据库文件只有 2 个页，每个页自成一个 Btree，每个 Btree 只有一个结点，既 是根页，也是叶子页。所以，至此，我们还没见过 Btree 的内部页呢。 2.12.12.12.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.22.22.22.2 BBBB++++treetreetreetree内部页格式介绍内部页格式介绍内部页格式介绍内部页格式介绍 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.32.32.32.3 BBBB++++treetreetreetree内部页格式分析内部页格式分析内部页格式分析内部页格式分析 现在对 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 的逻辑结构图如下所示： Page 3，Key<=0X2C Page 4，Key<=0X56 Page 5，Key>0X56 Ptr(0) Key(0) Ptr(1) Key(1) Ptr(2) 3 0X2C 4 0X56 5 2.42.42.42.4 叶子页格式分析叶子页格式分析叶子页格式分析叶子页格式分析 其实在上一章中分析 page 1 和 page 2 时，这两个页都是叶子页。这里再次对叶子页的格式 进行分析，主要是为了验证前一节对内部页的