第1页 / 共13页
第2页 / 共13页
第3页 / 共13页
第4页 / 共13页
第5页 / 共13页
第6页 / 共13页
第7页 / 共13页
第8页 / 共13页
SQLite物理文件结构.doc
1概念介绍
1.1 Btree、B-tree和B+tree：
1.2 auto-vacuum数据库：
1.3 数据库映像、数据库文件和日志文件：
2数据库存储结构
2.1、数据库头结构
2.2 、sqlite_master表
2.3、页结构
2.3.1.页结构总体概述
2.3.2.页头结构分析
2.3.3表数据存储格式（B+Tree）
2.3.3.1 B+tree格式介绍
2.3.3.2 B+tree内部页格式分析
2.3.3.3 B+ tree叶子页格式分析
2.3.4索引数据存储格式（B-Tree）
2.3.4.1索引内部页
2.3.4.2索引叶子页
3附录
3.1可变长整数
3.2字段的数据类型和宽度说明
3.3参考资料
Contents
1 概念介绍 ......................................................................................................................................... 1
1.1 Btree、B-tree 和 B+tree：.................................................................................................. 1
1.2 auto-vacuum 数据库：........................................................................................................ 2
1.3 数据库映像、数据库文件和日志文件：.........................................................................3
2 数据库存储结构 ............................................................................................................................. 3
2.1、数据库头结构................................................................................................................... 3
2.2 、sqlite_master 表...............................................................................................................4
2.3、页结构 ............................................................................................................................... 4
2.3.1.页结构总体概述.......................................................................................................4
2.3.2.页头结构分析........................................................................................................... 5
2.3.3 表数据存储格式（B+Tree）...................................................................................6
2.3.3.1 B+tree 格式介绍 ............................................................................................6
2.3.3.2 B+tree 内部页格式分析...............................................................................7
2.3.3.3 B+ tree 叶子页格式分析..............................................................................8
2.3.4 索引数据存储格式（B-Tree）..............................................................................11
2.3.4.1 索引内部页 .................................................................................................. 11
2.3.4.2 索引叶子页 ..................................................................................................12
3 附录 ............................................................................................................................................... 12
3.1 可变长整数 ........................................................................................................................ 12
3.2 字段的数据类型和宽度说明 ............................................................................................13
3.3 参考资料 ............................................................................................................................ 13
1 概念介绍
1.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 的统称
1
B-树
B+树
1.2 auto-vacuum 数据库：
一般情况下，当一个事务从数据库中删除了数据并提交后，数据库文件的大小保持不变。即
使整页的数据都被删除，该页也会变成“空闲页”等待再次被使用，而不会实际地被从数据
库文件中删除。执行 vacuum 操作，可以通过重建数据库文件来清除数据库内所有的未用空
间，使数据库文件变小。但是，如果一个数据库在创建时被指定为 auto_vacuum 数据库，当
删除事务提交时，数据库文件会自动缩小。使用 auto_vacuum 数据库可以节省空间，但却会
增加数据库操作的时间，有利有弊。Auto_vacuum 数据库需要使用附加的格式，如指针图页，
本文重点讨论非 auto_vacuum 数据库。
2
1.3 数据库映像、数据库文件和日志文件：
“数据库映像”是 SQLite 数据库的磁盘映像。SQLite 数据库存储在单一的“数据库文件”
中。一般情况下，数据库映像和数据库文件是一致的，可以理解为数据库映像就是数据库文
件的内容，但有例外。如果事务对数据库进行了修改，这些修改会暂存在“日志文件”中，
此时可以认为数据库映像分布在数据库文件和日志文件两个文件中。日志文件有自己的格
式，本文第 3 章专门介绍。
从逻辑上来说，一个 SQLite 数据库文件由多个多重 Btree 构成。每个 Btree 存储一个表的数
据或一个表的索引，索引采用 B-tree，而表数据采用 B+tree，每个 Btree 占用至少一个完整
的页，每个页是 Btree 的一个结点。每个表或索引的第 1 个页称为根页，所有表或索引的根
页编号都存储在系统表 sqlite_master 中，表 sqlite_master 的根页为 page 1
2 数据库存储结构
2.1、数据库头结构
数据库中第一个页(page 1)永远是 Btree 页。Page 1 的前 100 个字节是一个对数据库文件进行
描述的“文件头”。它包括数据库的版本、格式的版本、页大小、编码等所有创建数据库时
设置的永久性参数。关于这个特殊文件头的文档在 btreeInt.h 中，具体格式如下：
偏移量 大小
0
16
18
16
2
1
19
20
21
22
23
24
28
32
36
3
1
1
1
1
1
4
4
4
4
说明
头字符串，如果不改源程序，此字符串永远是"SQLite format 3"。
页大小(以字节为单位)。
文件格式版本(写)。对于 SQLite 的当前版本，此值为 1。如果该值大于 1，
表示文件为只读。SQLite 将来版本对此域的规定可能改变。
文件格式版本(读)。对于 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 用此域的值
验证内存缓冲区中数据的有效性。
未使用。
空闲页链表首指针。参“空闲页”一节。
文件内空闲页的数量。
Schema 版本：每次 schema 改变(创建或删除表、索引、视图或触发器等对
60
15 个 4 字节的元数据变量。
40
从偏移 40 开始的 15 个 4 字节元数据变量在 btreeInt.h 中的定义如下：
40
象，造成 sqlite_master 表被修改)时，此值+1。
44
文件格式错。
48
52
据库中根页编号的最大值，非 0。对于非 auto-vacuum 数据库，此域值为 0。
56
60
64
vacuum 模式，此域值为 1。否则，此域值为 0。
68
72
未使用。
未使用。
4
4
4
4
4
4
4
4
4
File format of schema layer：当前允许值为 1~4，超过此范围，将被认为是
Size of page cache。
Largest root-page (auto/incr_vacuum)：对于 auto-vacuum 数据库，此域为数
1=UTF-8、2=UTF16le、3=UTF16be。
User version。此域值供用户应用程序自由存取，其含义也由用户定义。
Incremental vacuum mode：对于 auto-vacuum 数据库，如果是 Incremental
2.2 、sqlite_master 表
每个表或索引的第 1 个页称为根页，所有表或索引的根页编号都存储在系统表 sqlite_master
中，表 sqlite_master 的根页为 page 1。
sqlite_master 是一个系统表，保存了数据库的 schema 信息。在逻辑上 sqlite_master 包含 5 个
字段，如下表所示：
编号
1
2
3
4
5
字段
type
name
tbl_name
rootpage
SQL
说明
值为"table"、 "index"、 "trigger"或"view"之一。
对象名称，值为字符串。
如果是表或视图对象，此字段值与字段 2 相同。如果是索引或触发
器对象，此字段值为与其相关的表名。
对触发器或视图对象，此字段值为 0。对表或索引对象，此字段值
为其根页的编号。
字符串，创建此对象时所使用的 SQL 语句。
本文以我们的产品中的一个数据库为例，sqlite_master 表信息如下：
2.3、页结构
2.3.1.页结构总体概述
每个 Btree 页由四个部分构成：
4
1．页头
2．单元指针数组
3．未分配空间
4．单元内容区
首先介绍“单元”的概念：Btree 页内部以单元(cell)为单位来组织数据，一个单元包含一个(或
部分，当使用溢出页时)payload(也称为 Btree 记录)。由于各类数据大小各不相同，每个单元
的大小也就是可变的，所以 Btree 页内部的空间需要进行动态分配(程序内部动态分配，不是
动态申请空间)，单元是 Btree 页内部进行空间分配和回收的基本单位。
页内所有单元的内容集中在页的底部，称为“单元内容区”，由下向上增长。由于单元的大
小可变，因此需要对每个单元在页内的起始位置(称为单元指针)进行记录。单元指针保存在
单元指针数组中，位于页头之后。单元指针数组包含 0 个或多个指针，由上向下增长。
单元指针数组和单元内容区相向增长，中间部分为未分配空间。系统尽量保证未分配空间位
于最后的指针之后，这样，就很容易增加新的单元，而不需要整理碎片。
单元不需要是相邻和有序的，但单元指针是相邻和有序的。每个指针占 2 个字节，表示该单
元在单元内容区中距页开始处的偏移。页中单元的数量保存在页头中。
2.3.2.页头结构分析
页头的格式如下：
说明
页类型标志。1: intkey, 2: zerodata, 4: leafdata, 8: leaf。
第 1 个自由块的偏移量。
本页的单元数。
碎片的字节数。
最右儿子的页号(the Ptr(n) value)。仅内部页有此域。
1
2
2
2
1
4
单元内容区的起始地址。
偏移量 大小
0
1
3
5
7
8
下面对页头各域分别进行介绍。
页类型标志：
如果 leaf 位被设置，则该页是一个叶子页，没有儿子；
如果 zerodata 位被设置，则该页只有关键字，而没有数据；
如果 intkey 位被设置，则关键字是整型；
如果 leafdata 位设置，则 tree 只存储数据在叶子页。
注：
可以这样理解：就不用管各标志位的含义了，
如果是 B+tree 的叶子页，该字节值为 0X0D，
如果是 B+tree 的内部页，该字节值为 0X05，
如果是 B-tree 的叶子页，该字节值为 0X0A，
如果是 B-tree 的内部页，该字节值为 0X02。
5
由此可见：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.3.3 表数据存储格式（B+Tree）
2.3.3.1 B+tree 格式介绍
对于数据库表，从 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) |
6
----------------------------------------------------------------
内部页包含 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.3.2 B+tree 内部页格式分析
现在对 sqlite_master 表 B+tree 的内部页进行分析。
由 于 第 一 页 的 前 100 个 字 节 存 放 数 据 库 文 件 头 信 息 ， 所 以 该 页 的 页 头 开 始 位 置 为 ：
0X00000064（100）
文件第 1 页页头的内容如下：(图中深蓝色部分)
前文对页头格式已经有比较详细的介绍，这里不再赘述。直接对内容进行说明：
0X05：说明该页为 B+tree 的内部页。
0X0000：第 1 个自由块的偏移量。此处为 0，表示本页没自由块。
0X0003：本页有 3 个单元。
0X03F1：单元内容区的起始位置。
0X00：碎片的字节数，此处为 0。
0X000001D5：最右儿子的页号，即 Ptr(N)。由于本页有 3 个单元，所以此处即 Ptr(3)。其值
为 0X01D5，即 Ptr(3)指向第 469 页。第 469 页是表数据的最后一页。
单元指针数组在页头之后，有 3 个指针，分别为 0X03FB，0X03F6 和 0X03F1。
下面来看单元内容区的数据，内容如下：(图中深蓝色部分)
由于单元内容区中各单元是反向增长的，所以三个单元的数据分别为：
0X00000009，0X03
0X0000000A，0X05
0X0000000D，0X06
每个单元包括 No index entries found.-分内容：
一个 4 字节的页号，指向相应的儿子，即 Ptr(i)。此处分别指向第 9 页，第 10 页和第 13 页。
一个可变长整数，即 Key(i)。0X03 表示最左儿子(文件第 9 页)中关键字值都<=0X03。0X05
表示第 2 个儿子(文件第 10 页)中关键字都>0X03，都<=0X05。0X06 表示第 3 个儿子(文件
第 13 页)中关键字都>0X05，都<=0X06。注意：关键字值使用可变长整数，我们插入的记录
少，在此都只有 1 个字节，所以看不出来。
7
前文刚介绍过，最右儿子的页号存储在页头中，值为 0X000001D5，说明第 469 页中关键字
值都>0X06。
重画前文 B+tree 的逻辑结构图如下所示：
2.3.3.3 B+ tree 叶子页格式分析
这里对叶子页的格式进行分析
首先是页头：
文件第 10 页页头的内容如下：(图中深蓝色部分)
之所以选择第 10 页，是因为该页为中间叶子，其记录的关键值应该在 Key(0)和 Key(1)之间。
因为是 B+tree 的叶子页，所以页头只有 8 个字节。说明：
0X0D：说明该页为 B+tree 的叶子结点。
0X0000：第 1 个自由块的偏移量。0，说明当前自由块链表为空。
0X0002：本页的单元数。当前表中只有 2 条记录。
0X0216：单元内容区的起始地址。
0X00：碎片的字节数。当前为 0。
从上图可以看出，本页有 0X02=2 个单元。第 1 个单元的入口地址为 0X0216，第二个单元
的入口地址为 0X03C9。
注意：这两个指针后面还有一些乱七八糟内容，我也曾为此迷惑过。这些不是指针，而是属
于“未分配空间”的一部分。因为此页在还没有成为内部页(还是叶子页)时，曾经插入过不
少记录，有过不少指针。现在成为内部页了，只使用两个指针，但以前使用过的空间也没必
要清零，再次使用时自然会覆盖。提示：此页尾部的内容区也存在这个情况，不再单独解释。
B+tree 叶子页的单元分析：
单元是变长的字节串。一个单元包含一个(或部分，当使用溢出页时)payload。B+tree 叶子页
单元的结构如下：
大小
var(1–9)
var(1–9) 数据库记录的 Rowid 值。
Payload 大小，以字节为单位。
说明
8
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
