源码网资料下载:www.codepub.com 从0X24开始的4个字节:文件内空闲页的数量。当前值为0。
从0X28开始的4个字节:Schema version。当前值为0X00000001。以后,每次sqlite_master表被修改时,此值+1。
从0X38开始的4个字节:采用的字符编码。此处为0X00000001,表示采用的是UTF-8编码。
注意:在SQLite文件中,所有的整数都采用大端格式,即高位字节在前。
1.3 Btree页格式介绍 1.3.1 Btree页的分区
页的类型有Btree页、空闲页和溢出页,本文前3章介绍的都是Btree页,其他类型的页在第4、5章介绍。
每个Btree页由四个部分构成: 1.页头 2.单元指针数组 3.未分配空间 4.单元内容区 首先介绍“单元”的概念:Btree页内部以单元(cell)为单位来组织数据,一个单元包含一个(或部分,当使用溢出页时)payload(也称为Btree记录)。由于各类数据大小各不相同,每个单元的大小也就是可变的,所以Btree页内部的空间需要进行动态分配(程序内部动态分配,不是动态申请空间),单元是Btree页内部进行空间分配和回收的基本单位。 页内所有单元的内容集中在页的底部,称为“单元内容区”,由下向上增长。由于单元的大小可变,因此需要对每个单元在页内的起始位置(称为单元指针)进行记录。单元指针保存在单元指针数组中,位于页头之后。单元指针数组包含0个或多个指针,由上向下增长。 单元指针数组和单元内容区相向增长,中间部分为未分配空间。系统尽量保证未分配空间位于最后的指针之后,这样,就很容易增加新的单元,而不需要整理碎片。
单元不需要是相邻和有序的,但单元指针是相邻和有序的。每个指针占2个字节,表示该单元在单元内容区中距页开始处的偏移。页中单元的数量保存在页头中。
1.3.2 页头格式
页头包含用来管理页的信息,它通常位于页的开始处。对于数据库文件的page 1,页头始于第100个字节处,因为前100个字节是文件头(file header)。 页头的格式如下: 偏移量 0 大小 1 说明 页类型标志。1: intkey, 2: zerodata, 4: leafdata, 8: leaf。 下载源码就到源码网,www.codepub.com
源码网资料下载:www.codepub.com 1 3 5 7 8 2 2 2 1 4 第1个自由块的偏移量。 本页的单元数。 单元内容区的起始地址。 碎片的字节数。 最右儿子的页号(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.4 Page 1格式分析
Btree的基本原理这里就不详细介绍了。Btree有多种实现方法,各类《数据结构》教材中的介绍也各不相同,但原理大同小异,随便找一本参考一下吧。最简单的Btree只有一个结点,既是根页,也是叶子页。
下载源码就到源码网,www.codepub.com
源码网资料下载:www.codepub.com 当前foods_test.db(大小为2K)只有两个页,都是Btree页。每个页都是一个Btree(B+tree,因为存储的是表数据),都是上述的单结点Btree。其中page 1为系统表sqlite_master的根页,下面我们对该页进行详细分析。
1.4.1 页头分析
该页的页头从0X64=100处开始(前面100个字节是文件头),8个字节(因为是叶子页)。如下图中深蓝色部分所示:
说明:
0X0D:说明该页为B+tree的叶子结点。
0X0000:第1个自由块的偏移量。值为0,说明当前自由块链表为空。
0X0001:本页的单元数。当前sqlite_master表中只有一条记录,所以本页当前只有1个单元。
0X0399:单元内容区的起始地址。 0X00:碎片的字节数。当前值为0。
1.4.2 单元指针数组
单元指针数组在页头之后,当前只有一个指针,为0X0399。
1.4.3 关于可变长整数
可变长整数是SQLite的特色之一,使用它既可以处理大整数,又可以节省存储空间。由于单元中大量使用可变长整数,故在此先加以介绍。
可变长整数由1~9个字节组成,每个字节的低7位有效,第8位是标志位。在组成可变长整数的各字节中,前面字节(整数的高位字节)的第8位置1,只有最低一个字节的第8位置0,表示整数结束。
可变长整数可以不到9个字节,即使使用了全部9个字节,也可以将它转换为一个64-bit整数。
下面是一些可变长整数的例子:
0x00 转换为 0x00000000 0x7f 转换为 0x0000007f 0x81 0x00 转换为 0x00000080 0x82 0x00 转换为 0x00000100 0x80 0x7f 转换为 0x0000007f 0x8a 0x91 0xd1 0xac 0x78 转换为 0x12345678 0x81 0x81 0x81 0x81 0x01 转换为 0x10204081
可变长整数可用于存储rowid、字段的字节数或Btree单元中的数据。
下载源码就到源码网,www.codepub.com
源码网资料下载:www.codepub.com 1.4.4 关于sqlite_master表
sqlite_master是一个系统表,保存了数据库的schema信息。在逻辑上sqlite_master包含5个字段,如下表所示: 编号 1 2 3 4 5 字段 type name tbl_name rootpage SQL 对象名称,值为字符串。 如果是表或视图对象,此字段值与字段2相同。如果是索引或触发器对象,此字段值为与其相关的表名。 对触发器或视图对象,此字段值为0。对表或索引对象,此字段值为其根页的编号。 字符串,创建此对象时所使用的SQL语句。 说明 值为\、 \、 \或\之一。 1.4.5 B+tree叶子页的单元格式
单元是变长的字节串。一个单元包含一个(或部分,当使用溢出页时)payload。B+tree叶子页单元的结构如下: 大小 var(1–9) var(1–9) * 4 Payload大小,以字节为单位。 数据库记录的Rowid值。 Payload内容,存储数据库中某个表一条记录的数据。 溢出页链表中第1个溢出页的页号。如果没有溢出页,无此域。 说明 结合实例来说明吧。
当前的单元内容区中只有一个单元,从0X0399开始,内容如下图所示:
0X65:Payload数据的字节数。可以看出Payload数据是从07 17 ~20 29。 0X01:foods(table对象)在sqlite_master表中对应记录的rowid,值为0X01。 Payload的格式如下图所示:
每个payload由两部分组成。第1部分是记录头,由N+1个可变长整数组成,N为记录中的字段数。第1个可变长整数(header-size)的值为记录头的字节数。跟着的N个可变长整数与记录的各字段一一对应,表示各字段的数据类型和宽度。用可变长整数表示各字段类型和宽度的规定如下表所示: 类型值 0 N in 1..4 5 NULL 有符号整数 有符号整数 含义 0 N 6 数据宽度(字节数) 下载源码就到源码网,www.codepub.com