首页
学习
活动
专区
工具
TVP
发布

Database File Format

1.数据库文件

1.1.网页

1.2.数据库标题

1.2.1.魔术标题字符串

1.2.2.页面大小

1.2.3.文件格式版本号

1.2.4.每页保留字节数

1.2.5.有效载荷分数

1.2.6.文件更改计数器

1.2.7.数据库头内数据库大小

1.2.8.免费网页列表

1.2.9.架构cookie

1.2.10.架构格式编号

1.2.11.建议的缓存大小

1.2.12.增量真空设置

1.2.13.文本编码

1.2.14.用户版本号

1.2.15.应用程序ID

1.2.16.编写库版本号和版本有效号码

1.2.17.标题空间保留用于扩展

1.3.锁定字节页

1.4.Freelist

1.5.B树页

1.6.Cell Payload溢出页面

1.7.指针映射或Ptrmap页面

2.架构层

2.1.记录格式

2.2.记录排序顺序

2.3.SQL表的表示

2.4.WITHOUT ROWID表的表示

2.5.SQL索引的表示

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

2.6.存储SQL数据库模式

2.6.1.内部架构对象

2.6.2.sqlite_sequence表

2.6.3.sqlite_stat1表

2.6.4.sqlite_stat2表

2.6.5.sqlite_stat3表

2.6.6.sqlite_stat4表

3.回滚日志

4.预写日志

4.1.WAL文件格式

4.2.校验和算法

4.3.检查点算法

4.4.读者算法

4.5.WAL索引格式

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

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

在事务期间,SQLite会将附加信息存储在称为“回滚日志”的第二个文件中,或者如果SQLite处于WAL模式,则会存储预写日志文件。如果应用程序或主机在事务完成前崩溃,则回滚日志或预写日志包含将主数据库文件恢复到一致状态所需的信息。当回滚日志或预写日志包含恢复数据库状态所需的信息时,它们被称为“热日志”或“热WAL文件”。热日志和WAL文件只是错误恢复场景中的一个因素,所以不常见,但它们是SQLite数据库状态的一部分,因此不能忽略。本文档定义了回滚日志和预写日志文件的格式,

1.1.网页

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

页面从1开始编号。最大页码为2147483646(231 - 2)。最小大小的SQLite数据库是一个单一的512字节页面。最大数据库大小为2147483646页,每页65536字节或140,737,488,224,256字节(大约140太字节)。通常,SQLite会在达到其内部大小限制之前达到底层文件系统或磁盘硬件的最大文件大小限制。

通常情况下,SQLite数据库的大小范围从几千字节到几千兆字节,但已知存在于生产环境中的TB数据库的SQLite数据库。

在任何时候,主数据库中的每个页面都有一次使用,这是以下情况之一:

  • 锁定字节页面
  • 一个freelist页面
    • freelist树干页面
    • 一个freelist页面
  • 一个B树页面
    • 表b-树内页
    • 一个表b-树叶页
    • 索引b-tree内部页面
    • 一个索引b-tree叶页
  • 有效载荷溢出页面
  • 指针映射页面

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

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

1.2.数据库标题

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

数据库标题格式

抵消

尺寸

描述

0

16

标题字符串:“SQLite格式3 \ 000”

16

2

数据库页面大小以字节为单位。必须是512和32768(含)之间的两个幂,或者值1代表页面大小为65536。

18

1

文件格式写入版本。1为遗产; 2为WAL。

19

1

文件格式读取版本。1为遗产; 2为WAL。

20

1

每页末尾未使用的“保留”空间的字节数。通常为0。

21

1

最大嵌入净荷分数。必须是64。

22

1

最小嵌入净荷分数。必须是32。

23

1

叶有效负载分数。必须是32。

24

4

文件更改计数器。

28

4

数据库文件的大小在页面中。“头内数据库大小”。

32

4

第一个freelist树干页面的页码。

36

4

空闲列表页面的总数。

40

4

架构cookie。

44

4

架构格式编号。支持的模式格式是1,2,3和4。

48

4

默认页面缓存大小。

52

4

在自动真空或增量真空模式下,最大根b-页面的页码,否则为零。

56

4

数据库文本编码。值1表示UTF-8。值2表示UTF-16le。值3表示UTF-16be。

60

4

由user_version附注读取并设置的“用户版本”。

64

4

真(非零)增量真空模式。假(零),否则。

68

4

由PRAGMA application_id设置的“应用程序ID”。

72

20

保留用于扩展。必须为零。

92

4

版本有效的号码。

96

4

SQLITE_VERSION_NUMBER

1.2.1.魔术标题字符串

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

1.2.2.页面大小

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

1.2.3.文件格式版本号

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

1.2.4.每页保留字节数

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

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

1.2.5.有效载荷分数

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

1.2.6.文件更改计数器

文件更改计数器是一个偏移量为24的4字节的big-endian整数,只要数据库文件在修改后被解锁,该整数就会递增。当两个或更多进程正在读取同一个数据库文件时,每个进程都可以通过监视更改计数器来检测来自其他进程的数据库更改。当另一个进程修改了数据库时,进程通常需要刷新其数据库页面缓存,因为缓存已过时。文件更改计数器便于实现。

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

1.2.7.数据库头内数据库大小

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

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

1.2.8.免费网页列表

数据库文件中未使用的页面存储在freelist中。偏移量32的4字节大端整数存储freelist第一页的页码,如果freelist为空,则存储0。偏移量为36的商店中的4字节大端整数存储了freelist上的总页数。

1.2.9.架构cookie

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

1.2.10.架构格式编号

模式格式编号是位于偏移量44的4字节大端编号。模式格式编号与偏移量18和19处的文件格式读取和写入版本编号类似,只是模式格式编号引用了高级SQL格式化而不是低级别的b-tree格式。当前定义了四种模式格式数字:

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

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

1.2.11.建议的缓存大小

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

1.2.12.增量真空设置

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

1.2.13.文本编码

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

1.2.14.用户版本号

偏移量为60的4字节big-endian整数是由user_version编译指示设置和查询的用户版本。用户版本不被SQLite使用。

1.2.15.应用程序ID

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

1.2.16.编写库版本号和版本有效号码

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

1.2.17.标题空间保留用于扩展

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

1.3.锁定字节页

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

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

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

1.4.Freelist

数据库文件可能包含一个或多个未处于活动状态的页面。例如,当从数据库中删除信息时,可能会出现未使用的页面。未使用的页面存储在自由列表中,并在需要额外页面时重新使用。

freelist被组织为freelist中继页面的链表,每个中继页面包含零页或多页freelist页面的页码。

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

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

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

freelist页面的数量作为一个4字节的big-endian整数存储在数据库头文件中,距文件开头的偏移量为36。数据库头还将第一个freelist trunk页面的页码存储为一个4字节的big-endian整数,其偏移量为32,距离文件的开头。

1.5.B树页面

b-tree算法为面向页面的存储设备上的唯一键和有序键提供键/数据存储。有关b-trees的背景信息,请参见Knuth,“计算机编程的艺术”,第3卷“排序和搜索”,第471-479页。SQLite使用两种b-树。Knuth称之为“B * -Tree”的算法将所有数据存储在树叶中。SQLite将这种b-tree称为“表b-tree”。Knuth简称为“B-Tree”的算法将密钥和数据一起存储在叶子和内部页面中。在SQLite实现中,原始的B-Tree算法仅存储密钥,完全省略数据,并被称为“索引b-tree”。

B树页面是内部页面或叶子页面。叶页包含密钥,对于表b树,每个密钥都有关联的数据。内部页面包含K键和K + 1指向子B树页面的指针。内部b-tree页面中的“指针”仅仅是子页面的31位整数页码。

将叶子b树的深度定义为1,并且将任何内部b树的深度定义为其任何子树的最大深度。在一个格式良好的数据库中,内部B树的所有孩子都有相同的深度。

在内部的b-tree页面中,指针和键在逻辑上与两端的指针交替。(前面的句子在概念上应该被理解 - 页面中的键和指针的实际布局更加复杂,并且将在后续部分中进行描述。)同一页面内的所有键都是唯一的,按照从左向右的升序进行逻辑组织向右。(同样,这个顺序是逻辑的,而不是物理的,页面内的键的实际位置是任意的。)对于任何键X,指向X左边的指针指向所有键小于或等于的b-树页面到X.右侧的指针指的是所有键大于X的页面。

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

每个B树页面最多只有一个父B树页面。没有父级的B树页面被称为根页面。一个根b树页面连同其子元素的关闭形成一个完整的b树。有可能(并且实际上很常见)有一个完整的b-tree,它由一个既是叶子又是叶子的页面组成。因为有父母指向儿童的指针,所以如果仅知道根页面,则可以找到完整B树的每个页面。因此,B树是由它们的根页码来标识的。

B树页面可以是表格B树页面或索引B树页面。每个完整b-树中的所有页面都是相同的类型:表或索引。数据库模式中的每个rowid表在数据库文件中都有一个表b-树,包括系统表(如sqlite_master)。数据库文件中的每个索引都有一个索引b-tree,包括由唯一性约束创建的隐含索引。没有与虚拟表关联的b-树。特定的虚拟表实现可以使用影子表进行存储,但这些影子表在数据库模式中将具有单独的条目。WITHOUT ROWID表使用索引b-trees而不是表b-树,因此数据库文件中有一个索引b-tree用于每个WITHOUT ROWID表。

表b树中的每个条目由一个64位有符号整数密钥和多达2147483647个字节的任意数据组成。(表b树的关键字对应于b树实现的SQL表的rowid。)内部表b树只保存键和指向子项的指针。所有数据都包含在表格中的树叶中。

索引b-tree中的每个条目由长达2147483647字节的任意密钥组成,并且没有数据。

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

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

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

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

100字节的数据库文件头只能在页面1上找到,该页面始终是一个表格B树页面。数据库文件中的所有其他b-tree页面均忽略此100个字节的标题。

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

b-tree页面标题的页面大小为8个字节,内部页面的大小为12个字节。页眉中的所有多字节值都是大写字母。B树页面标题由以下字段组成:

B树页面标题格式

抵消

尺寸

描述

0

1

偏移量为0的单字节标志指示b树页面类型。值2(0x02)表示页面是内部索引b-tree页面。值为5(0x05)表示页面是内部表格b-tree页面。值为10(0x0a)表示页面是叶索引b-tree页面。值为13(0x0d)表示页面是叶表的b-tree页面。b-tree页面类型的任何其他值都是错误的。

1

2

偏移量为1的双字节整数表示页面上第一个空闲块的开始,如果没有空闲块,则为零。

3

2

偏移3处的双字节整数给出页面上的单元格数量。

5

2

偏移5处的双字节整数表示单元内容区域的开始。此整数的零值被解释为65536。

7

1

偏移7处的单字节整数给出了单元格内容区域内碎片空闲字节的数量。

8

4

偏移量为8的四字节页码是最右边的指针。该值仅出现在内部B树页面的标题中,并且在所有其他页面中都被忽略。

  • 值2(0x02)表示页面是内部索引b-tree页面。
  • 值为5(0x05)表示页面是内部表格b-tree页面。
  • 值为10(0x0a)表示页面是叶索引b-tree页面。
  • 值为13(0x0d)表示页面是叶表的b-tree页面。

b-tree页面类型的任何其他值都是错误的。1 2偏移量为1的双字节整数表示页面上第一个空闲块的开始,如果没有空闲块,则为零。3 2偏移3处的双字节整数给出页面上的单元格数量。5 2偏移5处的双字节整数表示单元格内容区域的开始。此整数的零值被解释为65536. 7 1偏移量为7的单字节整数给出了单元格内容区域内碎片空闲字节的数量。8 4偏移量为8的四字节页码是最右边的指针。该值仅出现在内部B树页面的标题中,并且在所有其他页面中都被忽略。

B树页面的单元指针数组紧跟在B树页面标题之后。设K是b树上的单元格数量。单元指针数组由K单元内容的2字节整数偏移量组成。单元指针按键顺序排列,最左边的单元格(具有最小的键的单元格)首先排在最右边的单元格(具有最大的键的单元格)。

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

如果一个页面不包含单元格(这仅对不包含行的表的根页面可能),那么单元格内容区域的偏移量将等于页面大小减去保留空间的字节数。如果数据库使用65536字节页面大小并且保留空间为零(通常保留空间的值),那么空页面的单元格内容偏移量应该是65536.但是,该整数太大而不能存储在2字节的无符号整数,所以其值为0。

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

一个空闲块需要至少4个字节的空间。如果在单元内容区域内存在隔离的1,2或3个未使用字节的组,则这些字节包含一个片段。所有片段中的总字节数存储在B树页面标题的第五个字段中。在格式良好的B树页面中,分段中的总字节数不得超过60。

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

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

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

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

  • varint是有效负载的总字节数,包括任何溢出
  • varint是整数键,又名“rowid”
  • 有效负载的初始部分不会溢出页面。
  • 溢出页面列表第一页的4字节大端整数页码 - 如果所有有效载荷都适合b树页面,则忽略该页码。

表B-Tree内部单元(标头0x05):

  • 一个4字节的big-endian页码,它是左边的子指针。
  • varint是整数键

索引B-Tree叶子单元(标头0x0a):

  • varint是密钥负载的总字节数,包括任何溢出
  • 有效负载的初始部分不会溢出页面。
  • 溢出页面列表第一页的4字节大端整数页码 - 如果所有有效载荷都适合b树页面,则忽略该页码。

索引B-Tree内部单元(标头0x02):

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

上面的信息可以按如下格式重新表格化:

B树细胞格式

数据类型

出现在...

描述

表叶(0x0d)

表格内部(0x05)

索引叶(0x0a)

索引内部(0x02)

4字节整数

左孩子的页码

Vrint

有效载荷的字节数

Vrint

ROWID

字节数组

有效载荷

4字节整数

第一溢出页面的页码

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

表B-树叶细胞:

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

表B-树内部细胞:

表b-树的内部页面没有有效载荷,所以不会有任何有效载荷泄漏。

索引B-Tree叶子或内部细胞:

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

以下是相同计算的另一种描述:

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

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

1.6.Cell Payload溢出页面

当b树单元的负载对于b树页面来说太大时,剩余溢出到溢出页面上。溢出页面形成一个链表。每个溢出页面的前四个字节是一个大端整数,它是链中下一页的页码,或者是链中最后一页的零。通过最后一个可用字节的第五个字节用于保存溢出内容。

1.7.指针映射或Ptrmap页面

指针映射或ptrmap页面是插入到数据库中的额外页面,以使auto_vacuum和incremental_vacuum模式的操作更高效。数据库中的其他页面类型通常具有从父到子的指针。例如,内部b-tree页面包含指向其子b-树页面的指针,并且溢出链具有链中早期链接指向后面链接的指针。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字节的big-endian页码组成。五种页面类型被识别:

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

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

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

2.1.记录格式

表b-树叶页的数据和索引b-tree页的关键字在上面被表征为任意的字节序列。前面的讨论提到一个关键比另一个关键要少,但没有定义“少于”的含义。本节将解决这些遗漏。

有效载荷(无论是表b-树数据还是索引b-树键)始终处于“记录格式”。记录格式定义了与表或索引中的列对应的值序列。记录格式指定列的数量,每列的数据类型以及每列的内容。

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

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

记录格式的串行类型代码

串行类型

内容大小

含义

0

0

值是一个NULL。

1

1

值是一个8位二进制补码整数。

2

2

值是一个大端的16位二进制补码整数。

3

3

值是一个大端的24位二进制补码整数。

4

4

值是一个大端的32位二进制补码整数。

5

6

值是一个大端的48位二进制补码整数。

6

8

值是一个大端的64位二进制补码整数。

7

8

Value是一个大端的IEEE 754-2008 64位浮点数。

8

0

值是整数0.(仅适用于架构格式4和更高版本。)

9

0

值是整数1.(仅适用于架构格式4和更高版本。)

10,11

不曾用过。保留用于扩展。

N≥12,甚至

(N-12)/ 2

值是一个长度为(N-12)/ 2个字节的BLOB。

N≥13且奇数

(N-13)/ 2

值是文本编码中的一个字符串,长度为(N-13)/ 2个字节。nul结束符未被存储。

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

记录中每个列的值紧跟在标题后面。对于串行类型0,8,9,12和13,该值为零字节。如果所有列都是这些类型,那么记录的主体部分是空的。

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

2.2.记录排序顺序

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

  1. NULL值(串行类型0)首先排序。
  2. 数字值(序列类型1到9)按NULL和数字顺序排序。
  3. 文本值(奇数序列类型13和更大)按列排序功能确定的顺序按数值排序。
  4. BLOB值(甚至序列类型为12或更大)按memcmp()确定的顺序进行排序。

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

BINARY内置BINARY排序规则使用标准C库中的memcmp()函数逐字节比较字符串。NOCASE NOCASE排序规则与二进制规则类似,只是在运行比较之前将大写ASCII字符('A'到'Z')折叠为小写字母。只有ASCII字符被大小写折叠。NOCASE不执行通用unicode无格式比较。RTRIM RTRIM与BINARY类似,只是任何一个字符串末尾的额外空格都不会改变结果。换句话说,只要字符串的末尾空格数量不同,字符串之间的比较就会相等。

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

所有字符串的默认整理函数是BINARY。可以使用列定义上的COLLATE子句在CREATE TABLE语句中指定表列的替代整理函数。当索引列时,默认情况下,在CREATE TABLE语句中指定的同一个比较函数用于索引中的列,尽管可以在CREATE INDEX语句中使用COLLATE子句覆盖此项。

2.3.SQL表的表示

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

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

如果列的相似性为REAL,并且该列包含可以在不丢失信息的情况下转换为整数的值(如果该值不包含小数部分并且不是太大而不能表示为整数),则该列可能是以整数形式存储在记录中。从记录中提取时,SQLite会将该值转换回浮点。

2.4.WITHOUT ROWID表的表示

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

因此,WITHOUT ROWID表的内容编码与普通rowid表的内容编码相同,不同之处在于重新排列了列的顺序,以便PRIMARY KEY列排在第一位,并且内容被用作关键字索引b-tree,而不是表B-树中的数据。具有REAL亲和性的列的特殊编码规则适用于WITHOUT ROWID表,它们与rowid表相同。

2.5.SQL索引的表示

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

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

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

在WITHOUT ROWID表的索引中,如果表PRIMARY 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);

ex25ce索引中的每一行都是包含这些列的记录:c,e,d,a。前两列是被索引的列,c和e。其余列是相应表格行的主键。通常,主键将是列d,c和a,但由于列c已经出现在索引的较早部分,因此它将从关键字后缀中省略。

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

禁用索引条目的键后缀中的冗余列仅在WITHOUT ROWID表中出现。在普通的rowid表中,即使INTEGER PRIMARY KEY列是被索引的列之一,索引条目始终以rowid结尾。

2.6.存储SQL数据库模式

数据库文件的页面1是表b-树的根页面,其中存储了一个名为“sqlite_master”(或TEMP数据库的“sqlite_temp_master”)的特殊表,用于存储完整的数据库模式。sqlite_master表的结构就像使用以下SQL创建的一样:

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

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

根据定义的对象的类型,sqlite_master.type列将是以下文本字符串之一:'table','index','view'或'trigger'。'table'字符串用于普通表和虚拟表。

sqlite_master.name列将保存对象的名称。表上的UNIQUE和PRIMARY KEY约束会导致SQLite创建名称形式为“sqlite_autoindex_TABLE_N”的内部索引,其中TABLE由包含该约束的表的名称替换,N是一个以1开头并且每个约束增加1的整数在表中定义。在WITHOUT ROWID表中,PRIMARY KEY没有sqlite_master条目,但为PRIMARY KEY预留了“sqlite_autoindex_TABLE_N”名称,就好像sqlite_master条目确实存在一样。这将影响后续UNIQUE约束的编号。在rowid表或WITHOUT ROWID表中,“sqlite_autoindex_TABLE_N”名称永远不会分配给INTEGER PRIMARY KEY。

sqlite_master.tbl_name列包含对象所关联的表或视图的名称。对于表或视图,tbl_name列是名称列的副本。对于索引,tbl_name是索引表的名称。对于触发器,tbl_name列存储引起触发器触发的表或视图的名称。

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

sqlite_master.sql列存储描述对象的SQL文本。此SQL文本是CREATE TABLE,CREATE VIRTUAL TABLE,CREATE INDEX,CREATE VIEW或CREATE TRIGGER语句,如果在数据库文件是数据库连接的主数据库时对数据库文件进行评估,则会重新创建该对象。文本通常是用于创建对象的原始语句的副本,但应用了标准化,以便文本符合以下规则:

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

sqlite_master.sql列中的文本是创建该对象的原始CREATE语句文本的副本,除了如上所述进行规范化以及后续ALTER TABLE语句修改之外。对于由UNIQUE或PRIMARY KEY约束自动创建的内部索引,sqlite_master.sql为NULL。

2.6.1.内部架构对象

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

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

  • 具有“sqlite_autoindex_TABLE_N”形式名称的索引,用于在普通表上实现UNIQUE和PRIMARY KEY约束。
  • 一个名为“sqlite_sequence”的表,用于跟踪使用AUTOINCREMENT的表的最大历史INTEGER PRIMARY KEY。
  • 表格名称为“sqlite_statN”的表格,其中N是一个整数。这些表存储由ANALYZE命令收集并由查询计划程序使用的数据库统计信息,以帮助确定每个查询使用的最佳算法。

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

2.6.2.sqlite_sequence表

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

CREATE TABLE sqlite_sequence(name,seq);

对于使用AUTOINCREMENT的每个普通表,sqlite_sequence表中有一行。表的名称(出现在sqlite_master.name中)位于sqlite_sequence.main字段中,并且插入该表的最大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.3.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列中的整数列表可以选择性地跟随参数,其中每个参数都是非空格字符序列。所有参数前面都有一个空格。无法识别的参数被忽略。

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

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

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

在将来对SQLite进行增强时,新的文本标记可能会添加到统计信息列的末尾。为了兼容性,统计列末尾的无法识别的令牌将被忽略。

如果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.4.sqlite_stat2表

sqlite_stat2仅创建,并且仅在SQLite使用SQLITE_ENABLE_STAT2进行编译并且SQLite版本号介于3.6.18(2009-09-11)和3.7.8(2011-09-19)之间时使用。sqlite_stat2表在3.6.18之前和之后都不会被任何版本的SQLite读取或写入。sqlite_stat2表包含有关索引内键的分布的附加信息。sqlite_stat2表的模式如下所示:

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

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

sqlite_stat2.sampleno在0到9之间的索引的sqlite_stat2条目是沿着索引在均匀间隔点获取的索引中最左边的键值的样本。设C是索引中的行数。然后,采样的行由给出

rownumber = (i*C*2 + C)/20

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

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

2.6.5.sqlite_stat3表

sqlite_stat3仅在SQLite使用SQLITE_ENABLE_STAT3或SQLITE_ENABLE_STAT4编译并且SQLite版本号为3.7.9(2011-11-01)或更高版本时使用。在3.7.9之前,sqlite_stat3表不会被任何版本的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表中,任何单个索引的样本必须以与它们在索引中出现的顺序相同的顺序出现。换句话说,如果索引b-tree中最左列S1的条目早于最左列S2的条目,则在sqlite_stat3表中,样本S1必须具有比样本S2小的rowid。

2.6.6.sqlite_stat4表

sqlite_stat4仅创建,并且仅在SQLite使用SQLITE_ENABLE_STAT4进行编译时使用,并且SQLite版本号为3.8.1(2013-10-17)或更高版本时才会使用。在3.8.1之前,sqlite_stat4表不被任何版本的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:

sqlite_stat4.tbl列包含拥有该行所描述索引的表的名称

IDX:

sqlite_stat4.idx列包含行描述的索引的名称,或者在WITHOUT ROWID表的sqlite_stat4条目中包含表本身的名称。

sample :

sqlite_stat4.sample列包含记录格式的BLOB,它对索引列进行编码,后跟rowid表的rowid,或者对WITHOUT ROWID表的主键列进行编码。WITHOUT ROWID表的sqlite_stat4.sample BLOB本身仅包含主键的列。让sqlite_stat4.sample blob编码的列数为N.对于普通rowid表上的索引,N将比索引的列数多一个。对于WITHOUT ROWID表中的索引,N将是索引的列数加上主键中的列数。对于WITHOUT ROWID表,N将是主键中的列数。

NEQ:

sqlite_stat4.nEq列包含N个整数的列表,其中第K个整数是索引中其最左边的K列与样本的K个最左列匹配的近似条目数。

NLT:

sqlite_stat4.nLt列包含N个整数的列表,其中第K个整数是索引中K个最左列总体上小于样本的K个最左列的索引条目的近似数目。

nDLt:

sqlite_stat4.nDLt列包含N个整数的列表,其中第K个整数是索引中的前几个K列中不同的近似数目,并且其中最左边的K列总体上小于最左边的列K列的样本。

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

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

在格式正确的sqlite_stat4表中,任何单个索引的样本必须以与它们在索引中出现的顺序相同的顺序出现。换句话说,如果条目S1在索引b-tree中比在条目S2中更早,则在sqlite_stat4表中,样本S1必须具有比样本S2更小的rowid。

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

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

回滚日志只有在存在并且包含有效标题的情况下才被认为是有效的。因此,交易可以通过以下三种方式之一进行:

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

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

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

回滚日记报头格式

抵消

尺寸

描述

0

8

标题字符串:0xd9,0xd5,0x05,0xf9,0x20,0xa1,0x63,0xd7

8

4

“页数” - 日志下一部分的页数,-1表示文件末尾的所有内容

12

4

校验和的随机数

16

4

页面中数据库的初始大小

20

4

由写日志的进程假定的磁盘扇区的大小。

24

4

本期刊物的页面大小。

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

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

让数据库页面大小(日志标题中偏移量为24的整数值)为N.然后,页面记录的格式如下所示:

回滚日记页面记录格式

抵消

尺寸

描述

0

4

数据库文件中的页码

4

ñ

交易开始前页面的原始内容

N + 4

4

校验

校验和是一个无符号的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页面记录日志文件之后,可能会将0填充到扇区大小的下一个倍数,并插入另一个日志标题。同一日志中的所有日记标题必须包含相同的数据库页面大小和扇区大小。

如果初始日记头中的M为-1,则通过计算有多少页记录适合日记文件其余部分的可用空间,计算出后续页记录的数量。

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

4.1.WAL文件格式

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

单个WAL文件可以重复使用多次。换句话说,WAL可以填满框架,然后被检查点,然后新框架可以覆盖旧框架。WAL总是从开始到结束。附加到每个帧的校验和和计数器用于确定WAL内的哪些帧是有效的,哪些是来自先前检查点的剩余物。

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

WAL标题格式

抵消

尺寸

描述

0

4

魔术数字。0x377f0682或0x377f0683

4

4

文件格式版本。目前3007000。

8

4

数据库页面大小。例如:1024

12

4

检查点序列号

16

4

Salt-1:随每个检查点递增的随机整数

20

4

Salt-2:每个检查点的不同随机数

24

4

校验和-1:校验和的头24个字节的第一部分

28

4

校验和-2:校验和的头24个字节的第二部分

紧跟在wal-header之后的是零个或多个帧。每个帧由一个24字节的帧头和一个页面大小的页面数据字节组成。帧头是六个大端的32位无符号整数值,如下所示:

WAL帧头格式

抵消

尺寸

描述

0

4

页码

4

4

对于提交记录,提交后页面中数据库文件的大小。对于所有其他记录,零。

8

4

Salt-1从WAL标题中复制而来

12

4

Salt-2从WAL标题中复制而来

16

4

Checksum-1:通过并包括此页面的累积校验和

20

4

Checksum-2:累计校验和的后半部分。

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

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

4.2.校验和算法

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

校验和算法仅适用于长度为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标头salt-1值递增,并且salt-2值被随机化。对盐进行的这些更改会使WAL中已经设置了检查点但尚未覆盖的旧框架失效,并防止它们再次被检查点。

4.4.读者算法

为了从数据库中读取页面(称为页码P),阅读器首先检查WAL以查看其是否包含页面P.如果是,则接着是提交框架的最后一个有效页面P的实例或者是提交框架本身成为读取的值。如果WAL不包含任何有效页面P的副本,并且这些副本是提交框架或后跟提交框架,则从数据库文件中读取页面P.

为了开始一个读事务,阅读器记录WAL中最后一个有效帧的索引。阅读器使用此记录的“mxFrame”值进行所有后续读取操作。新事务可附加到WAL,但只要读者使用其原始mxFrame值并忽略随后添加的内容,阅读器将从单一时间点看到数据库的一致快照。该技术允许多个并发读取器同时查看不同版本的数据库内容。

前面段落中的阅读器算法正常工作,但由于页面P的帧可以出现在WAL内的任何位置,读者必须扫描整个WAL寻找页面P帧。如果WAL很大(通常是几兆字节),那么扫描速度可能会很慢,并且读取性能会受到影响。为了克服这个问题,维护了一个叫做wal-index的独立数据结构,以加速搜索特定页面的帧。

4.5.WAL索引格式

从概念上讲,wal-index是共享内存,尽管当前的VFS实现为wal-index使用了mmapped文件。mmapped文件与数据库位于同一目录中,并且与-shm附加了后缀“ ” 的数据库名称相同。由于wal-index是共享内存,因此当客户机位于不同的计算机上时,SQLite不支持网络文件系统上的journal_mode = WAL。数据库的所有用户必须能够共享相同的内存。

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

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

前一段中的M值是4.4节中定义的“mxFrame”值,该值在事务开始时读取,并定义读者将使用的WAL的最大帧。

wal-index是暂时的。崩溃后,wal-index从原WAL文件重建。当最后一次连接到它时,VFS需要截断或归零wal-index的头部。由于沃尔玛索引是暂时的,因此它可以使用特定于体系结构的格式; 它不一定是跨平台的。因此,不同于将所有值存储为大端的数据库和WAL文件格式,wal-index以主机的本地字节顺序存储多字节值。

本文档涉及数据库文件的持久状态,由于wal-index是一种瞬态结构,因此在此不再提供有关wal-index格式的更多信息。关于wal-index格式的完整细节包含在SQLite源代码的注释中。

 SQLite is in the Public Domain.

扫码关注腾讯云开发者

领取腾讯云代金券