数据库文件格式

本文档描述并定义了自版本 3.0.0 (2004-06-18) 以来所有版本的 SQLite 使用的磁盘数据库文件格式。

1.数据库文件

SQLite 数据库的完整状态通常包含在磁盘上称为“主数据库文件”的单个文件中。

在事务期间,SQLite 将附加信息存储在称为“回滚日志”的第二个文件中,或者如果 SQLite 处于 WAL 模式,则为预写日志文件。

1.1. 热点期刊

如果应用程序或主机在事务完成之前崩溃,则回滚日志或预写日志包含将主数据库文件恢复到一致状态所需的信息。当回滚日志或预写日志包含恢复数据库状态所需的信息时,它们被称为“热日志”或“热 WAL 文件”。热日志和 WAL 文件只是错误恢复场景中的一个因素,因此并不常见,但它们是 SQLite 数据库状态的一部分,因此不容忽视。本文档定义了回滚日志和预写日志文件的格式,但重点放在主数据库文件上。

1.2. 页数

主数据库文件由一页或多页组成。页的大小是 2 的幂,介于 512 和 65536 之间(含)。同一数据库中的所有页面大小相同。数据库文件的页面大小由位于距数据库文件开头 16 字节偏移处的 2 字节整数确定。

页码从 1 开始。最大页码为 4294967294 (2 32 - 2)。最小大小的 SQLite 数据库是一个 512 字节的页面。最大数据库大小为 2147483646 页,每页 65536 字节或 281,474,976,579,584 字节(约 281 TB)。通常,SQLite 会在达到其自身的内部大小限制之前很久就达到底层文件系统或磁盘硬件的最大文件大小限制。

通常情况下,SQLite 数据库的大小范围从几千字节到几千兆字节不等,尽管已知生产中存在 TB 大小的 SQLite 数据库。

在任何时间点,主数据库中的每个页面都有一次使用,即以下之一:

  • 锁定字节页面
  • 自由列表页面
    • 一个自由列表主干页面
    • 一个自由列表叶页
  • 一个 b 树页面
    • A表b树内页
    • 一张表b-tree叶子页
    • 索引 b-tree 内部页面
    • 索引 b 树叶页
  • 负载溢出页面
  • 指针映射页面

对主数据库文件的所有读取和写入都从页面边界开始,并且所有写入的大小都是整数页。读取通常也是整数页大小,唯一的例外是当数据库第一次打开时,数据库文件(数据库文件头)的前 100 个字节被作为子页大小单元读取。

在数据库的任何信息承载页面被修改之前,该页面的原始未修改内容被写入回滚日志。如果事务中断并需要回滚,则可以使用回滚日志将数据库恢复到其原始状态。Freelist 叶页不包含需要在回滚时恢复的信息,因此它们不会在修改之前写入日志,以减少磁盘 I/O。

1.3. 数据库头

数据库文件的前 100 个字节包含数据库文件头。数据库文件头分为如下表所示的字段。数据库文件头中的所有多字节字段均以最高有效字节在前(big-endian)存储。

数据库头格式
OffsetSizeDescription
016 The header string: "SQLite format 3\000"
162 The database page size in bytes. Must be a power of two between 512 and 32768 inclusive, or the value 1 representing a page size of 65536.
181 File format write version. 1 for legacy; 2 for WAL.
191 File format read version. 1 for legacy; 2 for WAL.
201 Bytes of unused "reserved" space at the end of each page. Usually 0.
211 Maximum embedded payload fraction. Must be 64.
221 Minimum embedded payload fraction. Must be 32.
231 Leaf payload fraction. Must be 32.
244 File change counter.
284 Size of the database file in pages. The "in-header database size".
324 Page number of the first freelist trunk page.
364 Total number of freelist pages.
404 The schema cookie.
444 The schema format number. Supported schema formats are 1, 2, 3, and 4.
484 Default page cache size.
524 The page number of the largest root b-tree page when in auto-vacuum or incremental-vacuum modes, or zero otherwise.
564 The database text encoding. A value of 1 means UTF-8. A value of 2 means UTF-16le. A value of 3 means UTF-16be.
604 The "user version" as read and set by the user_version pragma.
644 True (non-zero) for incremental-vacuum mode. False (zero) otherwise.
684 The "Application ID" set by PRAGMA application_id.
7220 Reserved for expansion. Must be zero.
924 The version-valid-for number.
964 SQLITE_VERSION_NUMBER

1.3.1. 魔术头字符串

每个有效的 SQLite 数据库文件都以以下 16 个字节(十六进制)开头:53 51 4c 69 74 65 20 66 6f 72 6d 61 74 20 33 00。此字节序列对应于 UTF-8 字符串“SQLite format 3”,包括末尾的 nul 终止符。

1.3.2. 页面大小

从偏移量 16 开始的两字节值决定了数据库的页面大小。对于 SQLite 版本 3.7.0.1 (2010-08-04) 及更早版本,此值被解释为大端整数,并且必须是介于 512 和 32768(含)之间的 2 的幂。从 SQLite版本 3.7.1 (2010-08-23) 开始,支持 65536 字节的页面大小。值 65536 不适合两字节整数,因此要指定 65536 字节的页面大小,偏移量 16 处的值为 0x00 0x01。该值可以解释为大端 1,并被视为表示 65536 页大小的幻数。或者可以将双字节字段视为一个小端序号,并说它表示页面大小除以 256。页面大小字段的这两种解释是等价的。

1.3.3. 文件格式版本号

偏移量 18 和 19 处的文件格式写入版本和文件格式读取版本旨在允许在未来版本的 SQLite 中增强文件格式。在当前版本的 SQLite 中,这两个值对于回滚日志模式都是 1,对于WAL 日志模式都是 2。如果编码为当前文件格式规范的 SQLite 版本遇到读取版本为 1 或 2 但写入版本大于 2 的数据库文件,则必须将数据库文件视为只读。如果遇到读取版本大于 2 的数据库文件,则无法读取或写入该数据库。

1.3.4. 每页保留字节数

SQLite 能够在每个页面的末尾留出少量额外字节供扩展使用。例如,SQLite 加密扩展使用这些额外的字节来存储与每个页面关联的随机数和/或加密校验和。偏移量 20 处的 1 字节整数中的“保留空间”大小是每页末尾为扩展保留的空间字节数。该值通常为 0。该值可以是奇数。

数据库页面的“可用大小”是由标头中偏移量 16 处的 2 字节整数指定的页面大小减去标头中偏移量 20 处的 1 字节整数中记录的“保留”空间大小。页面的可用大小可能是奇数。但是,可用大小不能小于480。换句话说,如果页面大小为512,那么预留空间大小不能超过32。

1.3.5. 有效载荷分数

最大和最小嵌入有效载荷分数和叶有效载荷分数必须为 64、32 和 32。这些值最初旨在作为可调参数,可用于修改 b 树算法的存储格式。但是,该功能不受支持,目前没有计划在未来添加支持。因此,这三个字节固定为指定的值。

1.3.6. 文件更改计数器

文件更改计数器是一个位于偏移量 24 处的 4 字节大端整数,只要数据库文件在修改后解锁,它就会递增。当两个或多个进程正在读取同一个数据库文件时,每个进程都可以通过监视更改计数器来检测来自其他进程的数据库更改。当另一个进程修改数据库时,一个进程通常希望刷新其数据库页面缓存,因为缓存已经过时。文件更改计数器有助于实现这一点。

在 WAL 模式下,使用 wal-index 检测数据库的更改,因此不需要更改计数器。因此,在 WAL 模式下,更改计数器可能不会在每个事务上递增。

1.3.7. 标头内数据库大小

头部偏移量 28 处的 4 字节大端整数以页为单位存储数据库文件的大小。如果此标头内数据大小无效(请参阅下一段),则通过查看数据库文件的实际大小来计算数据库大小。旧版本的 SQLite 忽略了头文件中的数据库大小并专门使用实际文件大小。如果可用,则较新版本的 SQLite 使用头内数据库大小,但如果头内数据库大小无效,则回退到实际文件大小。

只有在非零且偏移量 24 处的 4 字节更改计数器与 4 字节版本有效数字完全匹配时,才认为头内数据库大小有效在偏移量 92 处。当仅使用 SQLite 的最新版本 3.7.0 (2010-07-21) 及更高版本修改数据库时,标头内数据库大小始终有效。如果 SQLite 的旧版本写入数据库,它将不知道更新头内数据库大小,因此头内数据库大小可能不正确。但是旧版本的 SQLite 也会保留偏移量 92 处的版本有效编号不变,因此它不会匹配更改计数器。因此,可以通过观察更改计数器何时与版本有效数字不匹配来检测(并忽略)无效的标头内数据库大小。

1.3.8. 免费页面列表

数据库文件中未使用的页面存储在空闲列表中。偏移量 32 处的 4 字节大端整数存储空闲列表第一页的页码,如果空闲列表为空,则为零。偏移量 36 处的 4 字节 big-endian 整数存储了空闲列表上的页面总数。

模式 cookie 是偏移量为 40 的 4 字节大端整数,只要数据库模式发生变化,它就会递增。准备好的语句是针对特定版本的数据库模式编译的。当数据库模式发生变化时,必须重新准备语句。当准备好的语句运行时,它首先检查模式 cookie 以确保该值与语句准备时的值相同,如果模式 cookie 已更改,则该语句要么自动重新准备并重新运行,要么因SQLITE_SCHEMA 错误而中止。

1.3.10。架构格式编号

模式格式号是偏移量 44 处的 4 字节大端整数。模式格式号类似于偏移量 18 和 19 处的文件格式读写版本号,只是模式格式号指的是高级 SQL格式而不是低级 b 树格式。当前定义了四种模式格式编号:

  1. 回到 3.0.0 (2004-06-18) 版的所有 SQLite 版本都可以理解格式 1。
  2. 格式 2 添加了同一表中的行具有不同数量的列的能力,以支持 ALTER TABLE ... ADD COLUMN功能。在 2005 年 2 月 20 日的 SQLite 3.1.3 版中添加了对格式 2 的读写支持
  3. 格式 3 添加了由 ALTER TABLE ... ADD COLUMN添加的额外列的能力,以具有非 NULL 默认值。此功能已添加到 2005 年 3 月 11 日的 SQLite 3.1.4 版 中。
  4. 格式 4 使 SQLite 遵守索引声明中的 DESC 关键字(DESC 关键字在格式 1、2 和 3 的索引中被忽略。)格式 4 还添加了两个新的布尔记录类型值(序列类型 8 和 9)。2006 年 1 月 10 日的 SQLite 3.3.0 中添加了对格式 4 的支持。

SQLite 创建的新数据库文件默认使用格式 4。legacy_file_format pragma可用于使 SQLite 使用格式 1 创建新的数据库文件。通过在编译时 设置SQLITE_DEFAULT_FILE_FORMAT =1,可以使格式版本号默认为 1 而不是 4。

1.3.11。建议缓存大小

偏移量 48 处的 4 字节 big-endian 有符号整数是建议的数据库文件页面缓存大小。该值只是一个建议,SQLite 没有义务遵守它。整数的绝对值用作建议的大小。可以使用default_cache_size pragma设置建议的缓存大小。

1.3.12。增量真空设置

偏移量为 52 和 64 的两个 4 字节大端整数用于管理auto_vacuumincremental_vacuum模式。如果偏移量 52 处的整数为零,则指针映射 (ptrmap) 页将从数据库文件中省略,并且不支持 auto_vacuum 和 incremental_vacuum。如果偏移量 52 处的整数非零,则它是数据库文件中最大根页的页码,数据库文件将包含 ptrmap 页,并且模式必须是 auto_vacuum 或 incremental_vacuum。在后一种情况下,偏移量 64 处的整数对于 incremental_vacuum 为真,对于 auto_vacuum 为假。如果偏移量 52 处的整数为零,则偏移量 64 处的整数也必须为零。

1.3.13。文本编码

偏移量 56 处的 4 字节大端整数确定用于存储在数据库中的所有文本字符串的编码。值 1 表示 UTF-8。值 2 表示 UTF-16le。值 3 表示 UTF-16be。不允许使用其他值。sqlite3.h 头文件将 C 预处理器宏 SQLITE_UTF8 定义为 1,将 SQLITE_UTF16LE 定义为 2,并将 SQLITE_UTF16BE 定义为 3,以代替文本编码的数字代码。

1.3.14。用户版本号

偏移量 60 处的 4 字节大端整数是用户版本,由user_version pragma设置和查询。SQLite 不使用用户版本。

1.3.15。申请编号

偏移量 68 处的 4 字节大端整数是一个“应用程序 ID”,可以通过PRAGMA application_id命令设置,以便将数据库标识为属于特定应用程序或与特定应用程序相关联。应用程序 ID 适用于用作 应用程序文件格式的数据库文件。应用程序 ID 可以被file(1)等实用程序用来确定特定的文件类型,而不仅仅是报告“SQLite3 数据库”。可以通过查阅 SQLite 源存储库中的magic.txt文件来查看分配的应用程序 ID 列表。

1.3.16。写入库版本号和版本有效号

偏移量 96 处的 4 字节大端整数存储 最近修改数据库文件的 SQLite 库的SQLITE_VERSION_NUMBER值。偏移量 92 处的 4 字节大端整数是存储版本号时更改计数器的值。偏移量 92 处的整数表示版本号对哪个事务有效,有时称为“版本有效号”。

1.3.17。预留扩展头空间

数据库文件头的所有其他字节都保留用于将来的扩展,并且必须设置为零。

1.4. 锁定字节页面

锁定字节页面是数据库文件的单个页面,包含偏移量介于 1073741824 和 1073742335(含)之间的字节。大小小于或等于 1073741824 字节的数据库文件不包含锁定字节页。大于 1073741824 的数据库文件恰好包含一个锁定字节页。

锁定字节页面被留出供操作系统特定的 VFS实现在实现数据库文件锁定原语时使用。SQLite 不使用锁定字节页面。SQLite 核心永远不会读取或写入锁定字节页面,尽管操作系统特定的VFS 实现可能会根据底层系统的需要和倾向选择读取或写入锁定字节页面上的字节。SQLite 中内置的 unix 和 win32 VFS实现不会写入锁定字节页面,但其他操作系统的第三方 VFS 实现可能。

锁定字节页面源于支持 Win95 的需要,Win95 是设计此文件格式时的主要操作系统,并且仅支持强制文件锁定。我们所知道的所有现代操作系统都支持建议文件锁定,因此实际上不再需要锁定字节页面,而是为了向后兼容而保留。

1.5. 自由清单

数据库文件可能包含未使用的一页或多页。例如,当信息从数据库中删除时,可能会出现未使用的页面。未使用的页面存储在空闲列表中,并在需要其他页面时重新使用。

自由列表被组织为自由列表主干页面的链接列表,每个主干页面包含零个或多个自由列表叶子页面的页码。

freelist 主干页面由一个 4 字节大端整数数组组成。数组的大小是适合页面可用空间的整数。最小可用空间为 480 字节,因此数组的长度始终至少为 120 个条目。自由列表主干页面上的第一个整数是列表中下一个自由列表主干页面的页码,如果这是最后一个自由列表主干页面,则为零。空闲列表主干页面上的第二个整数是要跟随的叶页面指针的数量。将自由列表主干页面上的第二个整数称为 L。如果 L 大于零,则数组索引介于 2 和 L+1 之间的整数包含自由列表叶子页面的页码。

Freelist 叶页不包含任何信息。SQLite 避免读取或写入空闲列表叶页以减少磁盘 I/O。

3.6.0 (2008-07-16) 之前的 SQLite 版本中的错误导致如果自由列表主干页面数组中的最后 6 个条目中的任何一个包含非零值,则数据库被报告为已损坏。较新版本的 SQLite 没有这个问题。然而,新版本的 SQLite 仍然避免使用空闲列表主干页面数组中的最后六个条目,以便旧版本的 SQLite 可以读取由新版本的 SQLite 创建的数据库文件。

空闲列表页面的数量作为一个 4 字节的 big-endian 整数存储在数据库头中,距文件开头的偏移量为 36。数据库头还将第一个空闲列表主干页面的页码存储为一个 4 字节的大端整数,距文件开头的偏移量为 32。

1.6. B树页面

b-tree 算法在面向页面的存储设备上提供具有唯一且有序密钥的密钥/数据存储。有关 B 树的背景信息,请参阅 Knuth,计算机编程艺术,第 3 卷“排序和搜索”,第 471-479 页。SQLite 使用了两种 b 树变体。“表 b 树”使用 64 位带符号整数键并将所有数据存储在叶子中。“索引 b 树”使用任意键并且根本不存储任何数据。

B 树页面是内部页面或叶页面。叶页包含键,在表 b 树的情况下,每个键都有关联的数据。一个内部页面包含 K 个键和 K+1 个指向子 b-tree 页面的指针。内部 b-tree 页面中的“指针”只是子页面的 32 位无符号整数页码。

内部 B 树页面上的键数 K 几乎总是至少为 2,通常远大于 2。唯一的例外是页面 1 是内部 B 树页面。页 1 的可用存储空间少了 100 个字节,因为该页的开头存在数据库标头,因此有时(很少)如果页 1 是内部 b 树页,它最终可能只保存 aa单键。在所有其他情况下,K 为 2 或更大。K 的上限是页面上可以容纳的键数。索引 B 树上的大键被拆分成溢出页因此没有一个键使用页面上可用存储空间的四分之一以上,因此每个内部页面都能够存储至少 4 个键。表 B 树的整数键永远不会大到需要溢出,所以键溢出只发生在索引 B 树上。

将叶子 b 树的深度定义为 1,并将任何内部 b 树的深度定义为比其任何子树的最大深度大 1。在结构良好的数据库中,内部 B 树的所有子树都具有相同的深度。

在内部 B 树页面中,指针和键在逻辑上与两端的指针交替出现。(前一句要从概念上理解——页面内按键和指针的实际布局更复杂,将在后续描述。)同一页面内的所有按键都是唯一的,逻辑上从左到右按升序排列向右。(同样,这种排序是逻辑的,而不是物理的。页面中键的实际位置是任意的。)对于任何键 X,指向 X 左侧的指针指向所有键都小于或等于的 b 树页面指向X。指向X右侧的指针指的是所有键都大于X的页面。

在内部 b-tree 页面中,每个键和指向其紧邻左侧的指针组合成一个称为“单元格”的结构。最右边的指针是分开保存的。叶子 B 树页没有指针,但它仍然使用单元结构来保存索引 B 树的键或表 B 树的键和内容。数据也包含在单元格中。

每个 b-tree 页面至多有一个父 b-tree 页面。没有父页面的 b 树页面称为根页面。一个根 b-tree 页和它的孩子的闭包一起形成一个完整的 b-tree。有可能(事实上相当普遍)有一个完整的 b 树,它由一个既是叶子又是根的页面组成。因为有从父节点到子节点的指针,所以只要知道根页,就可以定位到完整b树的每一页。因此,b 树由它们的根页码标识。

b-tree 页是表 b-tree 页或索引 b-tree 页。每个完整 B 树中的所有页面都属于同一类型:表或索引。对于数据库模式中的每个 rowid 表,数据库文件中都有一个表 b-trees,包括系统表,如sqlite_schema对于模式中的每个索引,数据库文件中都有一个索引 b 树,包括由唯一性约束创建的隐含索引。没有与 虚拟表关联的 b 树。特定的虚拟表实现可能会使用影子表进行存储,但这些影子表将在数据库模式中具有单独的条目。 没有ROWID表使用索引 b 树而不是表 b 树,因此数据库文件中每个WITHOUT ROWID都有一个索引 b 树。与 sqlite_schema 表对应的 b-tree 始终是表 b-tree,并且根页始终为 1。sqlite_schema 表包含数据库文件中每个其他表和索引的根页码。

表 b 树中的每个条目都包含一个 64 位带符号整数键和最多 2147483647 字节的任意数据。(表 b-tree 的键对应于 b-tree 实现的 SQL 表的rowid。)内部表 b-tree 仅包含键和指向子节点的指针。所有数据都包含在表 b-tree 叶子中。

索引 b 树中的每个条目都包含一个长度不超过 2147483647 字节的任意键,并且没有数据。

将单元格的“有效负载”定义为单元格的任意长度部分。对于索引 b-tree,键的长度总是任意的,因此有效负载就是键。内部表 b-tree 页面的单元格中没有任意长度的元素,因此这些单元格没有有效负载。表 b-tree 叶子页面包含任意长度的内容,因此对于这些页面上的单元格,有效负载就是内容。

当单元的有效负载大小超过某个阈值(稍后定义)时,只有有效负载的前几个字节存储在 b 树页面上,其余部分存储在内容溢出页面的链表中。

B 树页面按以下顺序划分为区域:

  1. 100 字节的数据库文件头(仅在第 1 页上找到)
  2. 8 或 12 字节的 b-tree 页头
  3. 单元格指针数组
  4. 未分配空间
  5. 单元格内容区
  6. 保留区域。

100 字节的数据库文件头仅在第 1 页上找到,该页始终是表 B 树页。数据库文件中的所有其他 b 树页面都忽略了这个 100 字节的标头。

保留区域是每个页面末尾的未使用空间区域(锁定页面除外),扩展可以使用它来保存每页信息。保留区域的大小由在数据库文件头中偏移量 20 处找到的一字节无符号整数确定。保留区域的大小通常为零。

b-tree 页头的大小对于叶页为 8 字节,对于内部页为 12 字节。页眉中的所有多字节值都是大端。b-tree 页眉由以下字段组成:

B 树页眉格式
OffsetSizeDescription
01 The one-byte flag at offset 0 indicating the b-tree page type.
  • A value of 2 (0x02) means the page is an interior index b-tree page.
  • A value of 5 (0x05) means the page is an interior table b-tree page.
  • A value of 10 (0x0a) means the page is a leaf index b-tree page.
  • A value of 13 (0x0d) means the page is a leaf table b-tree page.
Any other value for the b-tree page type is an error.
12 The two-byte integer at offset 1 gives the start of the first freeblock on the page, or is zero if there are no freeblocks.
32 The two-byte integer at offset 3 gives the number of cells on the page.
52 The two-byte integer at offset 5 designates the start of the cell content area. A zero value for this integer is interpreted as 65536.
71 The one-byte integer at offset 7 gives the number of fragmented free bytes within the cell content area.
84 The four-byte page number at offset 8 is the right-most pointer. This value appears in the header of interior b-tree pages only and is omitted from all other pages.

b-tree 页的单元指针数组紧跟在 b-tree 页头之后。令 K 为 btree 上的单元数。单元指针数组由单元内容的 K 个 2 字节整数偏移量组成。单元格指针按键顺序排列,最左边的单元格(具有最小键的单元格)排在最前面,最右边的单元格(具有最大键的单元格)最后。

单元格内容存储在 b 树页面的单元格内容区域中。SQLite 努力将单元格放置在尽可能靠近 b 树页面末尾的位置,以便为单元格指针数组的未来增长留出空间。最后一个单元指针数组条目和第一个单元开始之间的区域是未分配区域。

如果页面不包含单元格(这仅适用于不包含行的表的根页面),则单元格内容区域的偏移量将等于页面大小减去保留空间的字节数。如果数据库使用 65536 字节的页面大小并且保留空间为零(保留空间的通常值),则空页的单元格内容偏移量应为 65536。但是,该整数太大而无法存储在2 字节无符号整数,因此使用值 0 代替它。

freeblock 是一种用于标识 b 树页面中未分配空间的结构。Freeblocks 被组织成一条链。空闲块的前 2 个字节是一个大端整数,它是链中下一个空闲块的 b 树页面中的偏移量,如果空闲块是链中的最后一个,则为零。每个空闲块的第三和第四个字节形成一个大端整数,它是空闲块的大小(以字节为单位),包括 4 字节的标头。空闲块总是按照增加偏移量的顺序连接。b 树页头的第二个字段是第一个空闲块的偏移量,如果页面上没有空闲块,则为零。在一个格式良好的 b-tree 页面中,在第一个空闲块之前总会有至少一个单元格。

一个空闲块至少需要 4 个字节的空间。如果在单元格内容区域内存在一组孤立的 1、2 或 3 个未使用字节,则这些字节构成一个片段。所有片段中的总字节数存储在 b-tree 页头的第五个字段中。在一个格式良好的 b-tree 页中,片段的总字节数不能超过 60。

B 树页面上的可用空间总量包括未分配区域的大小加上所有空闲块的总大小加上零碎的空闲字节数。SQLite 可能会不时地重组一个 b-tree 页面,这样就没有空闲块或片段字节,所有未使用的字节都包含在未分配的空间区域中,并且所有单元格都紧密地放在页面的末尾。这称为“碎片整理”b 树页面。

可变长度整数或“varint”是 64 位二进制补码整数的静态霍夫曼编码,它使用较少的空间来存储小的正值。varint 的长度在 1 到 9 个字节之间。varint 由零个或多个字节组成,其中高位设置后跟一个高位清除的单个字节,或者九个字节,以较短者为准。前八个字节的低七位和第九个字节的所有 8 位用于重建 64 位二进制补码整数。Varint 是大端字节序的:从 varint 的较早字节中提取的位比从后面字节中提取的位更重要。

单元格的格式取决于单元格出现在哪种 b-tree 页面上。下表按出现顺序显示了各种 b 树页面类型的单元格元素。

表 B 树叶单元(标头 0x0d):

  • 一个 varint,它是有效载荷的总字节数,包括任何溢出
  • 一个 varint,它是整数键,又名“ rowid
  • 不会溢出到溢出页面的有效负载的初始部分。
  • 溢出页面列表第一页的 4 字节 big-endian 整数页码 - 如果所有有效负载都适合 b-tree 页面,则省略。

表 B 树内部单元格(标题 0x05):

  • 一个 4 字节的大端页码,它是左子指针。
  • 一个 varint,它是整数键

索引 B 树叶单元(标头 0x0a):

  • 一个 varint,它是密钥负载的总字节数,包括任何溢出
  • 不会溢出到溢出页面的有效负载的初始部分。
  • 溢出页面列表第一页的 4 字节 big-endian 整数页码 - 如果所有有效负载都适合 b-tree 页面,则省略。

索引 B 树内部单元格(标题 0x02):

  • 一个 4 字节的大端页码,它是左子指针。
  • 一个 varint,它是密钥负载的总字节数,包括任何溢出
  • 不会溢出到溢出页面的有效负载的初始部分。
  • 溢出页面列表第一页的 4 字节 big-endian 整数页码 - 如果所有有效负载都适合 b-tree 页面,则省略。

上面的信息可以改写成表格格式如下:

B 树单元格格式
Datatype Appears in... Description
Table Leaf (0x0d) Table Interior (0x05) Index Leaf (0x0a) Index Interior (0x02)
4-byte integer     Page number of left child
varint   Number of bytes of payload
varint     Rowid
byte array   Payload
4-byte integer   Page number of first overflow page

溢出到溢出页面的负载量也取决于页面类型。对于以下计算,设 U 为数据库页面的可用大小,总页面大小减去每页末尾的保留空间。设 P 为有效负载大小。在下文中,符号 X 表示可以直接存储在 b-tree 页面上而不会溢出到溢出页面上的最大负载量,符号 M 表示在允许溢出之前必须存储在 b-tree 页面上的最小负载量.

表 B 树叶单元格:

令 X 为 U-35。如果有效载荷大小 P 小于或等于 X,则整个有效载荷存储在 b 树叶页上。令 M 为 ((U-12)*32/255)-23,令 K 为 M+((PM)%(U-4))。如果 P 大于 X,则如果 K 小于或等于 X,则存储在表 b 树叶页上的字节数为 K,否则为 M。叶页上存储的字节数永远不会少于 M。

表 B 树内部单元格:

表 B 树的内部页面没有有效载荷,因此永远不会溢出任何有效载荷。

索引 B 树叶或内部单元格:

令 X 为 ((U-12)*64/255)-23。如果有效载荷大小 P 小于或等于 X,则整个有效载荷存储在 b 树页面上。令 M 为 ((U-12)*32/255)-23,令 K 为 M+((PM)%(U-4))。如果 P 大于 X,则如果 K 小于或等于 X,则存储在索引 b 树页面上的字节数为 K,否则为 M。索引页存储的字节数永远不会少于 M。

这是同一计算的另一种描述:

  • X 是表 btree 叶页的 U-35 或索引页的 ((U-12)*64/255)-23。
  • M 总是 ((U-12)*32/255)-23。
  • 令 K 为 M+((PM)%(U-4))。
  • 如果 P<=X 则所有 P 字节的 payload 直接存储在 btree 页面上而不会溢出。
  • 如果 P>X 且 K<=X,则 P 的前 K 个字节存储在 btree 页上,其余 PK 个字节存储在溢出页上。
  • 如果 P>X 且 K>X,则 P 的前 M 个字节存储在 btree 页上,其余 PM 字节存储在溢出页上。

溢出阈值旨在为索引 b 树提供 4 的最小扇出,并确保 b 树页面上有足够的有效负载,通常可以在不咨询溢出页面的情况下访问记录标头。事后看来,SQLite b 树逻辑的设计者意识到这些阈值本来可以变得更简单。但是,如果不导致不兼容的文件格式,则无法更改计算。目前的计算效果很好,即使它们有点复杂。

1.7. 单元负载溢出页面

当 b-tree 单元的有效载荷对于 b-tree 页面来说太大时,多余的部分会溢出到溢出页面上。溢出页面形成一个链表。每个溢出页的前四个字节是一个大端整数,它是链中下一页的页码,或者链中最后一页的页码为零。第五个字节到最后一个可用字节用于保存溢出内容。

1.8. 指针映射或 Ptrmap 页面

指针映射或 ptrmap 页面是插入到数据库中的额外页面,以提高auto_vacuumincremental_vacuum模式的操作效率。数据库中的其他页面类型通常具有从父到子的指针。例如,内部 b-tree 页面包含指向其子 b-tree 页面的指针,而溢出链具有从链中较早链接指向较晚链接的指针。ptrmap 页面包含从子到父的相反方向的链接信息。

Ptrmap 页面必须存在于任何数据库文件中,该文件在数据库头的偏移量 52 处具有非零最大根 B 树页面值。如果最大的根 b 树页面值为零,则数据库不得包含 ptrmap 页面。

在具有 ptrmap 页的数据库中,第一个 ptrmap 页是第 2 页。ptrmap 页由 5 字节条目的数组组成。设 J 是适合页面可用空间的 5 字节条目的数量。(换句话说,J=U/5。)第一个 ptrmap 页面将包含页面 3 到 J+2(含)的后向指针信息。第二个指针映射页面将在页面 J+3 上,该 ptrmap 页面将为页面 J+4 到 2*J+3(含)提供反向指针信息。对整个数据库文件依此类推。

在使用 ptrmap 页面的数据库中,在上一段中计算确定的位置处的所有页面都必须是 ptrmap 页面,并且没有其他页面可以是 ptrmap 页面。除非,如果字节锁页面碰巧落在与 ptrmap 页面相同的页码上,那么对于这种情况,ptrmap 将移动到下一页。

ptrmap 页面上的每个 5 字节条目都提供有关紧跟在指针映射之后的页面之一的反向链接信息。如果页面 B 是 ptrmap 页面,则有关页面 B+1 的反向链接信息由指针映射上的第一个条目提供。第二个条目提供了有关页面 B+2 的信息。等等。

每个 5 字节的 ptrmap 条目都包含一个字节的“页面类型”信息,后跟一个 4 字节的大端页码。可识别五种页面类型:

  1. B 树根页面。页码应为零。
  2. 一个自由列表页面。页码应为零。
  3. 单元负载溢出链的第一页。页码是包含内容溢出的单元格的 b-tree 页。
  4. 溢出链中除第一页之外的页面。页码是溢出链的前一页。
  5. 非根 b 树页面。页码是父 b-tree 页。

在包含 ptrmap 页面的任何数据库文件中,所有 b-tree 根页面必须位于任何非根 b-tree 页面、单元负载溢出页面或空闲列表页面之前。此限制可确保在自动清理或增量清理期间永远不会移动根页面。自动清理逻辑不知道如何更新 sqlite_schema 表的 root_page 字段,因此有必要防止根页面在自动清理期间移动,以保持 sqlite_schema 表的完整性。通过 CREATE TABLE、CREATE INDEX、DROP TABLE 和 DROP INDEX 操作将根页面移动到数据库文件的开头。

2.模式层

前面的文字描述了 SQLite 文件格式的低级方面。b-tree 机制提供了一种访问大型数据集的强大而有效的方法。本节将介绍如何使用低级 b-tree 层来实现更高级别的 SQL 功能。

2.1. 记录格式

表 b-tree 叶页的数据和索引 b-tree 页的键在上面被描述为任意字节序列。前面的讨论提到一个键小于另一个,但没有定义“小于”的含义。当前部分将解决这些遗漏。

有效载荷,无论是表 B 树数据还是索引 B 树键,始终采用“记录格式”。记录格式定义了与表或索引中的列对应的一系列值。记录格式指定列数、每列的数据类型以及每列的内容。

记录格式广泛使用了 上面定义的 64 位有符号整数的可变长度整数varint表示。

记录按顺序包含标题和主体。标头以单个 varint 开头,它确定标头中的字节总数。varint 值是标头的大小(以字节为单位),包括 varint 本身的大小。在 size varint 之后是一个或多个附加的 varint,每列一个。这些额外的 varint 称为“序列类型”数字,并根据下表确定每一列的数据类型:

记录格式的序列类型代码
Serial TypeContent SizeMeaning
00 Value is a NULL.
11 Value is an 8-bit twos-complement integer.
22 Value is a big-endian 16-bit twos-complement integer.
33 Value is a big-endian 24-bit twos-complement integer.
44 Value is a big-endian 32-bit twos-complement integer.
56 Value is a big-endian 48-bit twos-complement integer.
68 Value is a big-endian 64-bit twos-complement integer.
78 Value is a big-endian IEEE 754-2008 64-bit floating point number.
80 Value is the integer 0. (Only available for schema format 4 and higher.)
90 Value is the integer 1. (Only available for schema format 4 and higher.)
10,11 variable Reserved for internal use. These serial type codes will never appear in a well-formed database file, but they might be used in transient and temporary database files that SQLite sometimes generates for its own use. The meanings of these codes can shift from one release of SQLite to the next.
N≥12 and even (N-12)/2 Value is a BLOB that is (N-12)/2 bytes in length.
N≥13 and odd (N-13)/2 Value is a string in the text encoding and (N-13)/2 bytes in length. The nul terminator is not stored.

标头大小 varint 和串行类型 varint 通常由一个字节组成。大字符串和 BLOB 的串行类型 varints 可能扩展到两个或三个字节的 varints,但这是例外而不是规则。varint 格式在对记录头进行编码时非常有效。

记录中每一列的值紧跟在标题之后。对于序列类型 0、8、9、12 和 13,该值的长度为零字节。如果所有列都是这些类型,则记录的正文部分为空。

一条记录的值可能少于相应表中的列数。例如,在 ALTER TABLE ... ADD COLUMN SQL 语句增加表模式中的列数而不修改表中预先存在的行之后,可能会发生这种情况。使用表模式中定义的相应列 的默认值填充记录末尾的缺失值 。

2.2. 记录排序顺序

索引 b 树中键的顺序由键所代表的记录的排序顺序决定。逐列记录比较进度。从左到右检查记录的列。第一对不相等的列决定了两条记录的相对顺序。各个列的排序顺序如下:

  1. NULL 值(序列类型 0)首先排序。
  2. 数值(序列类型 1 到 9)在 NULL 之后按数字顺序排序。
  3. 文本值(奇数序列类型 13 和更大)按照列整理函数确定的顺序在数值之后排序
  4. BLOB 值(甚至序列类型 12 和更大)最后排序并按照由 memcmp() 确定的顺序。

为了计算文本字段的顺序,每列都需要一个整理函数。SQLite 定义了三个内置的整理函数:

BINARY The built-in BINARY collation compares strings byte by byte using the memcmp() function from the standard C library.
NOCASE The NOCASE collation is like BINARY except that uppercase ASCII characters ('A' through 'Z') are folded into their lowercase equivalents prior to running the comparison. Only ASCII characters are case-folded. NOCASE does not implement a general purpose unicode caseless comparison.
RTRIM RTRIM is like BINARY except that extra spaces at the end of either string do not change the result. In other words, strings will compare equal to one another as long as they differ only in the number of spaces at the end.

可以使用sqlite3_create_collat​​ion()接口将其他特定于应用程序的整理功能添加到 SQLite 。

所有字符串的默认整理函数都是 BINARY。可以在 CREATE TABLE语句中使用列定义上的 COLLATE 子句指定表列的替代整理函数。当列被索引时,在 CREATE TABLE语句中指定的相同整理函数默认用于索引中的列,尽管这可以使用 CREATE INDEX语句中的 COLLATE 子句覆盖。

2.3. SQL 表的表示

数据库模式中的每个普通 SQL 表都在磁盘上由表 b 树表示。表 b-tree 中的每个条目对应于 SQL 表的一行。SQL 表的rowid是表 b 树中每个条目的 64 位带符号整数键。

每个 SQL 表行的内容存储在数据库文件中,方法是首先将各个列中的值组合成记录格式的字节数组,然后将该字节数组作为负载存储在表 b 树的条目中。记录中值的顺序与 SQL 表定义中列的顺序相同。当 SQL 表包含一个 INTEGER PRIMARY KEY列(别名为rowid)时,该列在记录中显示为 NULL 值。在引用 INTEGER PRIMARY KEY列时,SQLite 将始终使用表 b-tree 键而不是 NULL 值。

如果列的亲和力是 REAL 并且该列包含一个可以转换为整数而不会丢失信息的值(如果该值不包含小数部分并且不会太大而不能表示为整数)则该列可能是作为整数存储在记录中。当从记录中提取值时,SQLite 会将值转换回浮点数。

2.4. WITHOUT ROWID 表的表示

如果 SQL 表是在其 CREATE TABLE 语句末尾使用“WITHOUT ROWID”子句创建的,则该表是WITHOUT ROWID 表并使用不同的磁盘表示。WITHOUT ROWID 表使用索引 b 树而不是表 b 树进行存储。WITHOUT ROWID b-tree 中每个条目的键是由 PRIMARY KEY 的列和表的所有剩余列组成的记录。主键列按照它们在 PRIMARY KEY 子句中声明的顺序出现,其余列按照它们在 CREATE TABLE 语句中出现的顺序出现。

因此,WITHOUT ROWID 表的内容编码与普通 rowid 表的内容编码相同,只是重新排列了列的顺序,使 PRIMARY KEY 列排在第一位,并且内容用作索引 b-tree 而不是表 b-tree 中的数据。具有 REAL 亲和力的列的特殊编码规则适用于 WITHOUT ROWID 表,就像它们对 rowid 表所做的一样。

2.4.1. WITHOUT ROWID表的PRIMARY KEY中冗余列的抑制

如果 WITHOUT ROWID 表的 PRIMARY KEY 多次使用具有相同整理顺序的相同列,则忽略 PRIMARY KEY 定义中该列的第二次和后续出现。例如,以下 CREATE TABLE 语句都指定同一个表,该表在磁盘上具有完全相同的表示形式:

CREATE TABLE t1(a,b,c,d,PRIMARY KEY(a,c)) WITHOUT ROWID);
CREATE TABLE t1(a,b,c,d,PRIMARY KEY(a,c,a,c)) WITHOUT ROWID);
CREATE TABLE t1(a,b,c,d,PRIMARY KEY(a,A,a,C)) WITHOUT ROWID);
CREATE TABLE t1(a,b,c,d,PRIMARY KEY(a,a,a,a,c)) WITHOUT ROWID);

当然,上面的第一个示例是表的首选定义。所有示例都创建了一个 WITHOUT ROWID 表,其中包含两个 PRIMARY KEY 列“a”和“c”,顺序为“a”和“c”,后跟两个数据列“b”和“d”,顺序也是如此。

2.5. SQL 索引的表示

每个 SQL 索引,无论是通过CREATE INDEX语句显式声明还是由 UNIQUE 或 PRIMARY KEY 约束隐含,都对应于数据库文件中的索引 b 树。索引 b 树中的每个条目都对应于关联 SQL 表中的一行。索引 b 树的键是由正在索引的列和相应表行的键组成的记录。对于普通表,行键是rowid,对于WITHOUT ROWID表,行键是 PRIMARY KEY。因为表中的每一行都有一个唯一的行键,所以索引中的所有键都是唯一的。

在普通索引中,表中的行与与该表关联的每个索引中的条目之间存在一对一的映射。但是,在部分索引中,索引 b 树仅包含与 CREATE INDEX 语句中的 WHERE 子句表达式为真的表行对应的条目。索引和表 B 树中的相应行共享相同的 rowid 或主键值,并且所有索引列都包含相同的值。

2.5.1. WITHOUT ROWID 二级索引中冗余列的抑制

在 WITHOUT ROWID 表的索引中,如果 PRIMARY KEY 的列也是索引中的列并且具有匹配的排序顺序,则索引列在索引记录末尾的 table-key 后缀中不重复. 例如,考虑以下 SQL:

CREATE TABLE ex25(a,b,c,d,e,PRIMARY KEY(d,c,a)) WITHOUT rowid;
CREATE INDEX ex25ce ON ex25(c,e);
CREATE INDEX ex25acde ON ex25(a,c,d,e);
CREATE INDEX ex25ae ON ex25(a COLLATE nocase,e);

ex25ce 索引中的每一行都是包含以下列的记录:c、e、d、a。前两列是被索引的列,c 和 e。其余列是相应表行的主键。通常,主键是列 d、c 和 a,但是因为列 c 已经出现在索引的前面,所以从键后缀中省略了它。

在被索引的列覆盖 PRIMARY KEY 的所有列的极端情况下,索引将仅由被索引的列组成。上面的 ex25acde 示例演示了这一点。ex25acde 索引中的每个条目仅包含按顺序排列的列 a、c、d 和 e。

ex25ae 中的每一行包含五列:a、e、d、c、a。“a”列重复,因为第一次出现的“a”具有“nocase”的整理功能,而第二个出现的整理顺序为“binary”。如果“a”列不重复,并且如果表包含两个或多个具有相同“e”值的条目并且其中“a”仅大小写不同,则所有这些表条目将对应于索引中的单个条目,这将打破表和索引之间的一对一对应关系。

索引条目的键后缀中冗余列的抑制仅发生在 WITHOUT ROWID 表中。在普通的 rowid 表中,索引条目总是以 rowid 结尾,即使INTEGER PRIMARY KEY 列是被索引的列之一。

2.6. SQL 数据库模式的存储

数据库文件的第 1 页是表 b 树的根页,该表包含一个名为“ sqlite_schema ”的特殊表。这个 b 树被称为“模式表”,因为它存储了完整的数据库模式。sqlite_schema 表的结构就像是使用以下 SQL 创建的:

CREATE TABLE sqlite_schema(
  type text,
  name text,
  tbl_name text,
  rootpage integer,
  sql text
);

sqlite_schema 表包含数据库模式中每个表、索引、视图和触发器(统称为“对象”)的一行,除了 sqlite_schema 表本身没有条目。除了应用程序和程序员定义的对象之外, sqlite_schema 表还包含内部模式对象的条目。

sqlite_schema.type 列将是以下文本字符串之一:“table”、“index”、“view”或“trigger”,具体取决于定义的对象类型。'table' 字符串用于普通表和虚拟表

sqlite_schema.name 列将保存对象的名称。 表上的UNIQUEPRIMARY KEY约束导致 SQLite 创建 名称为“sqlite_autoindex_TABLE_N”形式的内部索引,其中 TABLE 被包含约束的表的名称替换,N 是一个从 1 开始并随着每个约束增加 1 的整数在表定义中看到。WITHOUT ROWID表中,没有 PRIMARY KEY 的 sqlite_schema 条目,但是为 PRIMARY KEY 预留了“sqlite_autoindex_TABLE_N”名称,就好像 sqlite_schema 条目确实存在一样。这将影响后续 UNIQUE 约束的编号。“sqlite_autoindex_TABLE_N” ,在 rowid 表或 WITHOUT ROWID 表中。

sqlite_schema.tbl_name 列包含对象关联的表或视图的名称。对于表或视图,tbl_name 列是 name 列的副本。对于索引,tbl_name 是被索引的表的名称。对于触发器,tbl_name 列存储导致触发器触发的表或视图的名称。

sqlite_schema.rootpage 列存储表和索引的根 b 树页的页码。对于定义视图、触发器和虚拟表的行,rootpage 列为 0 或 NULL。

sqlite_schema.sql 列存储描述对象的 SQL 文本。此 SQL 文本是CREATE TABLECREATE VIRTUAL TABLECREATE INDEXCREATE VIEWCREATE TRIGGER语句,如果在数据库文件是数据库连接的主数据库时对其进行评估, 则会重新创建对象。文本通常是用于创建对象的原始语句的副本,但应用了规范化,因此文本符合以下规则:

  • 语句开头的 CREATE、TABLE、VIEW、TRIGGER 和 INDEX 关键字将全部转换为大写字母。
  • 如果 TEMP 或 TEMPORARY 关键字出现在初始 CREATE 关键字之后,则会将其删除。
  • 任何出现在正在创建的对象名称之前的数据库名称限定符都将被删除。
  • 删除前导空格。
  • 前两个关键字之后的所有空格都将转换为一个空格。

sqlite_schema.sql 列中的文本是创建对象的原始 CREATE 语句文本的副本,但如上所述进行规范化和由后续ALTER TABLE语句修改的文本除外。对于由UNIQUEPRIMARY KEY约束自动创建的内部索引, sqlite_schema.sql 为 NULL 。

2.6.1. 模式表的替代名称

名称“sqlite_schema”没有出现在文件格式的任何地方。该名称只是数据库实现使用的约定。由于历史和操作方面的考虑,“sqlite_schema”表有时也可以通过以下别名之一调用:

  1. sqlite_master
  2. sqlite_temp_schema
  3. sqlite_temp_master

因为模式表的名称没有出现在文件格式中的任何地方,所以如果应用程序选择通过这些替代名称之一引用模式表,数据库文件的含义不会改变。

2.6.2. 内部架构对象

除了应用程序和/或开发人员使用 CREATE 语句 SQL 创建的表、索引、视图和触发器之外,sqlite_schema 表可能包含零个或多个 由 SQLite 创建供其内部使用的内部模式对象的条目。内部模式对象的名称始终以“sqlite_”开头,任何名称以“sqlite_”开头的表、索引、视图或触发器都是内部模式对象。SQLite 禁止应用程序创建名称以“sqlite_”开头的对象。

SQLite 使用的内部模式对象可能包括以下内容:

新的内部模式对象名称,总是以“sqlite_”开头,可能会在未来的版本中添加到 SQLite 文件格式中。

2.6.3. sqlite_sequence 表

sqlite_sequence 表是一个用于帮助实现 AUTOINCREMENT的内部表。每当创建任何具有 AUTOINCREMENT 整数主键的普通表时,都会自动创建 sqlite_sequence 表。sqlite_sequence表一旦创建,就永远存在于sqlite_schema表中;它不能被丢弃。sqlite_sequence 表的架构是:

CREATE TABLE sqlite_sequence(name,seq);

每个使用 AUTOINCREMENT 的普通表在 sqlite_sequence 表中都有一行。表名(出现在 sqlite_schema.name 中)位于 sqlite_sequence.name 字段中, 插入该表的最大INTEGER PRIMARY KEY位于 sqlite_sequence.seq 字段中。为 AUTOINCREMENT 表自动生成的新整数主键保证大于该表的 sqlite_sequence.seq 字段。如果 AUTOINCREMENT 表的 sqlite_sequence.seq 字段已经是最大整数值 (9223372036854775807),则尝试使用自动生成的整数主表向该表添加新行将失败并返回 SQLITE_FULL错误。当新条目插入 AUTOINCREMENT 表时,如果需要,sqlite_sequence.seq 字段会自动更新。AUTOINCREMENT 表的 sqlite_sequence 行在删除表时自动删除。如果更新 AUTOINCREMENT 表时 AUTOINCREMENT 表的 sqlite_sequence 行不存在,则会创建一个新的 sqlite_sequence 行。如果 AUTOINCREMENT 表的 sqlite_sequence.seq 值手动设置为整数以外的值,并且随后尝试插入或更新 AUTOINCREMENT 表,则行为未定义。

允许应用程序代码修改 sqlite_sequence 表、添加新行、删除行或修改现有行。但是,如果 sqlite_sequence 表不存在,则应用程序代码无法创建它。应用程序代码可以删除 sqlite_sequence 表中的所有条目,但应用程序代码不能删除 sqlite_sequence 表。

2.6.4. sqlite_stat1 表

sqlite_stat1 是一个由ANALYZE命令创建的内部表,用于保存有关表和索引的补充信息,查询计划器可以使用这些信息来帮助它找到执行查询的更好方法。应用程序可以更新、删除、插入或删除 sqlite_stat1 表,但不能创建或更改 sqlite_stat1 表。sqlite_stat1 表的架构如下:

CREATE TABLE sqlite_stat1(tbl,idx,stat);

每个索引通常有一行,索引由 sqlite_stat1.idx 列中的名称标识。sqlite_stat1.tbl 列是索引所属表的名称。在每一行中,sqlite_stat.stat 列将是一个字符串,由整数列表和后跟零个或多个参数组成。此列表中的第一个整数是索引中的近似行数。(索引中的行数与表中的行数相同,部分索引除外.) 第二个整数是在索引的第一列中具有相同值的索引中的近似行数。第三个整数是索引中前两列具有相同值的行数。第 N 个整数(对于 N>1)是索引中前 N-1 列具有相同值的估计平均行数。对于 K 列索引,stat 列中将有 K+1 个整数。如果索引是唯一的,那么最后一个整数将为 1。

stat 列中的整数列表可以选择后跟参数,每个参数都是一系列非空格字符。所有参数前面都有一个空格。无法识别的参数被默默地忽略。

如果存在“unordered”参数,则查询计划器假定索引是无序的,并且不会将索引用于范围查询或排序。

“sz=NNN”参数(其中 NNN 表示 1 个或多个数字的序列)表示表或索引的所有记录的平均行大小为每行 NNN 字节。SQLite 查询规划器可能会使用“sz=NNN”标记提供的估计行大小信息来帮助它选择需要较少磁盘 I/O 的较小表和索引。

索引的 sqlite_stat1.stat 字段上存在“noskipscan”标记会阻止该索引与 跳过扫描优化一起使用。

在未来对 SQLite 的增强中,可能会将新的文本标记添加到统计列的末尾。为了兼容性,stat 列末尾无法识别的标记将被忽略。

如果 sqlite_stat1.idx 列为 NULL,则 sqlite_stat1.stat 列包含一个整数,它是 sqlite_stat1.tbl 标识的表中的近似行数。如果 sqlite_stat1.idx 列与 sqlite_stat1.tbl 列相同,则该表是一个WITHOUT ROWID表,sqlite_stat1.stat 字段包含有关实现 WITHOUT ROWID 表的索引 btree 的信息。

2.6.5. sqlite_stat2 表

sqlite_stat2 仅在使用 SQLITE_ENABLE_STAT2 编译 SQLite 且 SQLite 版本号介于 3.6.18 (2009-09-11) 和 3.7.8 (2011-09-19) 之间时才创建和使用。sqlite_stat2 表在 3.6.18 之前和 3.7.8 之后的任何版本的 SQLite 既不读取也不写入。sqlite_stat2 表包含有关索引内键分布的附加信息。sqlite_stat2 表的架构如下:

CREATE TABLE sqlite_stat2(tbl,idx,sampleno,sample);

sqlite_stat2 表的每一行中的 sqlite_stat2.idx 列和 sqlite_stat2.tbl 列标识该行描述的索引。每个索引在 sqlite_stat2 表中通常有 10 行。

sqlite_stat2.sampleno 介于 0 和 9 之间(含 0 和 9)的索引的 sqlite_stat2 条目是索引中最左边键值的样本,取自索引上均匀分布的点。令 C 为索引中的行数。然后采样行由

行数 = (i*C*2 + C)/20

前面表达式中的变量 i 在 0 到 9 之间变化。从概念上讲,索引空间被划分为 10 个均匀的桶,样本是每个桶的中间行。

sqlite_stat2 的格式记录在这里以供遗留参考。SQLite 的最新版本不再支持 sqlite_stat2 并且 sqlite_stat2 表(如果存在)将被忽略。

2.6.6. sqlite_stat3 表

sqlite_stat3 仅在使用SQLITE_ENABLE_STAT3SQLITE_ENABLE_STAT4编译 SQLite 并且 SQLite 版本号为 3.7.9 (2011-11-01) 或更高版本时使用。sqlite_stat3 表既不被 3.7.9 之前的任何版本的 SQLite 读取也不写入。如果使用SQLITE_ENABLE_STAT4编译时选项并且 SQLite 版本号为 3.8.1 (2013-10-17) 或更高版本,则 sqlite_stat3 可能会被读取但不会被写入。sqlite_stat3 表包含有关索引中键分布的附加信息,查询计划程序可以使用这些信息来设计更好更快的查询算法。sqlite_stat3 表的架构如下:

CREATE TABLE sqlite_stat3(tbl,idx,nEq,nLt,nDLt,sample);

每个索引在 sqlite_stat3 表中通常有多个条目。sqlite_stat3.sample 列包含由 sqlite_stat3.idx 和 sqlite_stat3.tbl 标识的索引最左侧字段的值。sqlite_stat3.nEq 列包含索引中最左边的列与样本完全匹配的条目的近似数量。sqlite_stat3.nLt 包含索引中最左侧列小于样本的条目的近似数量。sqlite_stat3.nDLt 列包含索引中小于样本的不同最左侧条目的近似数量。

每个索引可以有任意数量的 sqlite_stat3 条目。ANALYZE命令通常会生成 sqlite_stat3 表,其中包含 10 到 40 个样本,这些样本分布在键空间中并具有较大的 nEq 值

在格式良好的 sqlite_stat3 表中,任何单个索引的样本必须按照它们在索引中出现的相同顺序出现。换句话说,如果最左边列 S1 的条目在索引 b 树中早于最左边列 S2 的条目,那么在 sqlite_stat3 表中,样本 S1 的 rowid 必须小于样本 S2。

2.6.7. sqlite_stat4 表

sqlite_stat4 仅在使用SQLITE_ENABLE_STAT4编译 SQLite且 SQLite 版本号为 3.8.1 (2013-10-17) 或更高时才创建和使用。sqlite_stat4 表既不被 3.8.1 之前的任何版本的 SQLite 读取也不写入。sqlite_stat4 表包含有关索引内键分布或WITHOUT ROWID主键中键分布的附加信息。查询规划器有时可以使用 sqlite_stat4 表中的附加信息来设计更好更快的查询算法。sqlite_stat4 表的架构如下:

CREATE TABLE sqlite_stat4(tbl,idx,nEq,nLt,nDLt,sample);

每个索引的 sqlite_stat4 表中通常有 10 到 40 个条目,这些条目的统计信息可用,但是这些限制不是硬性限制。sqlite_stat4表中各列的含义如下:

tbl: The sqlite_stat4.tbl column holds name of the table that owns the index that the row describes
idx: The sqlite_stat4.idx column holds name of the index that the row describes, or in the case of an sqlite_stat4 entry for a WITHOUT ROWID table, the name of the table itself.
sample: The sqlite_stat4.sample column holds a BLOB in the record format that encodes the indexed columns followed by the rowid for a rowid table or by the columns of the primary key for a WITHOUT ROWID table. The sqlite_stat4.sample BLOB for the WITHOUT ROWID table itself contains just the columns of the primary key. Let the number of columns encoded by the sqlite_stat4.sample blob be N. For indexes on an ordinary rowid table, N will be one more than the number of columns indexed. For indexes on WITHOUT ROWID tables, N will be the number of columns indexed plus the number of columns in the primary key. For a WITHOUT ROWID table, N will be the number of columns in the primary key.
nEq: The sqlite_stat4.nEq column holds a list of N integers where the K-th integer is the approximate number of entries in the index whose left-most K columns exactly match the K left-most columns of the sample.
nLt: The sqlite_stat4.nLt column holds a list of N integers where the K-th integer is the approximate number of entries in the index whose K left-most columns are collectively less than the K left-most columns of the sample.
nDLt: The sqlite_stat4.nDLt column holds a list of N integers where the K-th integer is the approximate number of entries in the index that are distinct in the first K columns and where the left-most K columns are collectively less than the left-most K columns of the sample.

sqlite_stat4 是 sqlite_stat3 表的概括。sqlite_stat3 表提供有关索引最左侧列的信息,而 sqlite_stat4 表提供有关索引所有列的信息。

每个索引可以有任意数量的 sqlite_stat4 条目。ANALYZE命令通常会生成 sqlite_stat4 表,其中包含 10 到 40 个样本,这些样本分布在键空间中并具有较大的 nEq 值

在格式良好的 sqlite_stat4 表中,任何单个索引的样本必须按照它们在索引中出现的相同顺序出现。换句话说,如果条目 S1 在索引 b 树中早于条目 S2,则在 sqlite_stat4 表中,样本 S1 的 rowid 必须小于样本 S2。

3.回滚日志

回滚日志是与每个 SQLite 数据库文件相关联的文件,它包含用于在事务过程中将数据库文件恢复到其初始状态的信息。回滚日志文件始终位于与数据库文件相同的目录中,并且与数据库文件同名,但附加了字符串“ -journal ”。只能有一个与给定数据库关联的回滚日志,因此一次只能有一个针对单个数据库打开的写事务。

如果事务因应用程序崩溃、操作系统崩溃或硬件电源故障或崩溃而中止,则数据库可能处于不一致状态。下次 SQLite 尝试打开数据库文件时,将检测到回滚日志文件的存在,并自动回放日志以将数据库恢复到未完成事务开始时的状态。

回滚日志仅在存在且包含有效标头时才被视为有效。因此,可以通过以下三种方式之一提交事务:

  1. 可以删除回滚日志文件,
  2. 回滚日志文件可以被截断为零长度,或者
  3. 回滚日志的标题可以用无效的标题文本(例如,全零)覆盖。

这三种提交事务的方式分别对应于 journal_mode pragma的 DELETE、TRUNCATE 和 PERSIST 设置。

有效的回滚日志以以下格式的标头开头:

回滚日志标题格式
OffsetSizeDescription
0 8 Header string: 0xd9, 0xd5, 0x05, 0xf9, 0x20, 0xa1, 0x63, 0xd7
8 4 The "Page Count" - The number of pages in the next segment of the journal, or -1 to mean all content to the end of the file
12 4 A random nonce for the checksum
16 4 Initial size of the database in pages
20 4 Size of a disk sector assumed by the process that wrote this journal.
24 4 Size of pages in this journal.

回滚日志头用零填充到单个扇区的大小(由偏移量 20 处的扇区大小整数定义)。标头本身位于一个扇区中,因此如果在写入该扇区时发生断电,标头后面的信息将(希望)完好无损。

在标题和零填充之后是零个或多个页面记录。每个页面记录都存储了数据库文件中页面内容在更改之前的副本。同一个页面在单个回滚日志中可能不会出现多次。要回滚未完成的事务,进程只需从头到尾读取回滚日志,并将在日志中找到的页面写回到数据库文件中的适当位置。

设数据库页大小(日志头中偏移量为24的整数的值)为N,那么一条页记录的格式如下:

回滚日志页面记录格式
OffsetSizeDescription
0 4 The page number in the database file
4 N Original content of the page prior to the start of the transaction
N+4 4 Checksum

校验和是一个无符号的 32 位整数,计算如下:

  1. 将校验和初始化为在日志头中偏移量 12 处找到的校验和现时值。
  2. 将索引 X 初始化为 N-200(其中 N 是数据库页面的大小,以字节为单位。
  3. 将页中偏移量 X 处的字节解释为 8 位无符号整数,并将该整数的值添加到校验和。
  4. 从 X 中减去 200。
  5. 如果 X 大于或等于零,则返回步骤 3。

校验和值用于防止电源故障后日志页面记录的不完整写入。每次开始交易时都会使用不同的随机数,以最大程度地降低未写入扇区可能偶然包含来自先前日志的同一页面的数据的风​​险。通过更改每笔交易的随机数,磁盘上的陈旧数据仍会生成不正确的校验和,并且很有可能被检测到。出于性能原因,校验和仅使用数据记录中的 32 位字的稀疏样本 - SQLite 3.0.0 规划阶段的设计研究表明,在对整个页面进行校验和时会显着降低性能。

令日志头中偏移量 8 处的页计数值为 M。如果 M 大于零,则在 M 页记录之后,日志文件可能会被零填充到扇区大小的下一个倍数,并且可能会插入另一个日志头。同一期刊中的所有期刊标题必须包含相同的数据库页面大小和扇区大小。

如果初始日志标题中的 M 为 -1,则通过计算日志文件剩余部分的可用空间可以容纳多少页记录来计算后面的页记录数。

4.预写日志

版本 3.7.0 (2010-07-21) 开始,SQLite 支持一种新的事务控制机制,称为“预写日志”或“ WAL ”。当数据库处于 WAL 模式时,与该数据库的所有连接都必须使用 WAL。特定数据库将使用回滚日志或 WAL,但不会同时使用两者。WAL 始终位于与数据库文件相同的目录中,并且与数据库文件具有相同的名称,但附加了字符串“ -wal ”。

4.1. 文件格式

WAL 文件由一个标头和后跟零个或多个“帧”组成。每个框架记录了数据库文件中单个页面的修改内容。对数据库的所有更改都通过将帧写入 WAL 来记录。当写入包含提交标记的帧时,事务提交。单个 WAL 可以并且通常确实记录多个事务。周期性地,WAL 的内容在称为“检查点”的操作中传输回数据库文件。

单个 WAL 文件可以重复使用多次。换句话说,WAL 可以填满帧,然后设置检查点,然后新帧可以覆盖旧帧。WAL 总是从头到尾增长。附加到每个帧的校验和和计数器用于确定 WAL 中哪些帧是有效的,哪些是先前检查点的剩余帧。

WAL 标头的大小为 32 字节,由以下八个大端 32 位无符号整数值组成:

WAL 标头格式
OffsetSizeDescription
04 Magic number. 0x377f0682 or 0x377f0683
44 File format version. Currently 3007000.
84 Database page size. Example: 1024
124 Checkpoint sequence number
164 Salt-1: random integer incremented with each checkpoint
204 Salt-2: a different random number for each checkpoint
244 Checksum-1: First part of a checksum on the first 24 bytes of header
284 Checksum-2: Second part of the checksum on the first 24 bytes of header

紧跟在 wal-header 之后的是零个或多个帧。每个帧都包含一个 24 字节的帧头,后跟一个页面大小字节的页面数据。frame-header 是六个 big-endian 32 位无符号整数值,如下所示:

WAL 帧头格式
OffsetSizeDescription
04 Page number
44 For commit records, the size of the database file in pages after the commit. For all other records, zero.
84 Salt-1 copied from the WAL header
124 Salt-2 copied from the WAL header
164 Checksum-1: Cumulative checksum up through and including this page
204 Checksum-2: Second half of the cumulative checksum.

当且仅当满足以下条件时,框架才被视为有效:

  1. frame-header 中的 salt-1 和 salt-2 值与 wal-header 中的盐值匹配

  2. 帧头最后 8 个字节中的校验和值与 WAL 头的前 24 个字节和前 8 个字节以及直到并包括当前帧的所有帧的内容连续计算的校验和完全匹配。

4.2. 校验和算法

通过将输入解释为偶数个无符号 32 位整数来计算校验和:x(0) 到 x(N)。如果 WAL 头的前 4 个字节中的幻数为 0x377f0683,则 32 位整数为大端;如果幻数为 0x377f0682,则整数为小端。无论使用哪种字节顺序计算校验和,校验和值始终以大端格式存储在帧头中。

校验和算法仅适用于长度为 8 字节的倍数的内容。换句话说,如果输入是 x(0) 到 x(N),那么 N 必须是奇数。校验和算法如下:

 
s0 = s1 = 0
for i from 0 to n-1 step 2:
   s0 += x(i) + s1;
   s1 += x(i+1) + s0;
endfor
# result in s0 and s1

输出 s0 和 s1 都是以相反顺序使用斐波那契权重的加权校验和。(最大的斐波那契权重出现在被求和的序列的第一个元素上。)s1 值跨越序列的所有 32 位整数项,而 s0 省略最后一项。

4.3. 检查点算法

检查点上,首先使用VFS的 xSync 方法将 WAL 刷新到持久存储然后将 WAL 的有效内容传输到数据库文件中。最后,使用另一个 xSync 方法调用将数据库刷新到持久存储。xSync 操作用作写屏障 - 在 xSync 之前启动的所有写操作必须在 xSync 开始之后启动的任何写操作之前完成。

检查点不需要运行完成。可能是某些读者仍在使用包含在数据库文件中的数据的旧事务。在那种情况下,将较新事务的内容从 WAL 文件传输到数据库中会从仍在使用较旧事务的读者中删除内容。为避免这种情况,只有当所有读取器都在使用 WAL 中的最后一个事务时,检查点才会运行到完成。

4.4. WAL 重置

在一个完整的检查点之后,如果没有其他连接在使用 WAL 的事务中,那么后续的写事务可以从头开始覆盖 WAL 文件。这称为“重置 WAL”。在第一个新写入事务开始时,WAL 标头 salt-1 值递增,salt-2 值随机化。这些对盐的更改使 WAL 中已经设置检查点但尚未覆盖的旧帧无效,并阻止它们再次设置检查点。

WAL 文件可以选择在重置时被截断,但它不是必须的。如果 WAL 没有被截断,性能通常会好一些,因为文件系统通常会比增长文件更快地覆盖现有文件。

4.5. 读者算法

要从数据库中读取一个页面(称之为页面编号 P),读取器首先检查 WAL 以查看它是否包含页面 P。如果是,那么页面 P 的最后一个有效实例后面跟着一个提交帧或者是一个提交框架本身成为读取的值。如果 WAL 不包含页面 P 的副本,这些副本是有效的并且是提交帧或后跟提交帧,则从数据库文件读取页面 P。

为了启动读取事务,读取器将 WAL 中的值帧数记录为“mxFrame”。更详细)读取器使用这个记录的 mxFrame 值进行所有后续读取操作。可以将新事务附加到 WAL,但只要读取器使用其原始 mxFrame 值并忽略随后附加的内容,读取器就会看到来自单个时间点的数据库的一致快照。该技术允许多个并发读者同时查看不同版本的数据库内容。

前面段落中的阅读器算法工作正常,但是因为页面 P 的框架可以出现在 WAL 中的任何地方,阅读器必须扫描整个 WAL 以寻找页面 P 框架。如果 WAL 很大(通常是几兆字节),扫描可能会很慢,并且读取性能会受到影响。为了克服这个问题,维护了一个称为 wal-index 的单独数据结构,以加快对特定页面框架的搜索。

4.6. WAL-索引格式

从概念上讲,wal-index 是共享内存,尽管当前的 VFS 实现使用内存映射文件来实现操作系统的可移植性。内存映射文件与数据库位于同一目录中,并与数据库同名,并附加“ -shm ”后缀。因为 wal-index 是共享内存,当客户端位于不同的机器上时,SQLite 不支持 网络文件系统上的journal_mode=WAL ,因为数据库的所有客户端必须能够共享相同的内存。

wal-index 的目的是快速回答这个问题:

给定页码 P 和最大 WAL 帧索引 M,返回页面 P 的最大 WAL 帧索引,该索引不超过 M,或者如果页面 P 没有帧不超过 M,则返回 NULL。

上一段中的M值是4.4 节中定义的“mxFrame”值,它在事务开始时读取,它定义了读取器将使用的 WAL 中的最大帧。

wal-index 是暂时的。崩溃后,wal-index 将从原始 WAL 文件中重建。当与它的最后一个连接关闭时,VFS 需要截断或清零 wal-index 的标头。因为 wal-index 是瞬态的,所以它可以使用特定于体系结构的格式;它不必是跨平台的。因此,与将所有值存储为大端的数据库和 WAL 文件格式不同,wal-index 以主机的本机字节顺序存储多字节值。

本文档关注的是数据库文件的持久化状态,由于 wal-index 是一个瞬态结构,这里不再提供有关 wal-index 格式的更多信息。有关 wal-index 格式的更多详细信息包含在单独的WAL-index 文件格式文档中。