SQLite文件格式分析_v102

源码网资料下载:www.codepub.com INSERT INTO \ALUES(88, 4, 'Dijon Mustard'); INSERT INTO \ALUES(89, 4, 'Dill'); INSERT INTO \ALUES(90, 4, 'Ginger'); INSERT INTO \ALUES(91, 4, 'Gravy');

INSERT INTO \ALUES(92, 4, 'Honey Mustard');

INSERT INTO \ALUES(93, 4, 'Ketchup and Mustard together'); INSERT INTO \ALUES(94, 4, 'Ketchup');

INSERT INTO \ALUES(95, 4, 'Ketchup (secret)'); INSERT INTO \ALUES(96, 4, 'Maple Syrup'); INSERT INTO \ALUES(97, 4, 'Mustard (fancy)'); INSERT INTO \ALUES(98, 4, 'Parsley'); INSERT INTO \ALUES(99, 4, 'Pepper'); INSERT INTO \ALUES(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.2 B+tree内部页格式介绍

Page 2仍然是表foods的根页,但已经变成了内部页,格式有较大的变化。

对于数据库表,从SQLite3开始采用了B+tree,在此,先对B+tree的结构做一个简单介绍。B+tree与B-tree的主要区别在于,B-tree的所有页上都包含数据,而B+tree的数据只存在于叶子页上,内部页只存储导航信息。B+tree所有的叶子页都在同一层上,并按关键字排序,所有的关键字必须唯一,其逻辑结构举例如下图所示:

下载源码就到源码网,www.codepub.com

源码网资料下载:www.codepub.com

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.3 B+tree内部页格式分析

现在对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。

注意:这两个指针后面还有一些乱七八糟内容,我也曾为此迷惑过。这些不是指针,而是属于“未分配空间”的一部分。因为此页在还没有成为内部页(还是叶子页)时,曾经插入过不少记录,有过不少指针。现在成为内部页了,只使用两个指针,但以前使用过的空间也没必要清零,再次使用时自然会覆盖。提示:此页尾部的内容区也存在这个情况,不再单独解释。 下载源码就到源码网,www.codepub.com

源码网资料下载:www.codepub.com

下面来看单元内容区的数据,内容如下:(图中深蓝色部分)

由于单元内容区中各单元是反向增长的,所以两个单元的数据分别为: 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的逻辑结构图如下所示: Ptr(0) 3 Key(0) 0X2C Ptr(1) 4 Key(1) 0X56 Ptr(2) 5 Page 3,Key<=0X2C Page 4,Key<=0X56 Page 5,Key>0X56 2.4 叶子页格式分析

其实在上一章中分析page 1和page 2时,这两个页都是叶子页。这里再次对叶子页的格式进行分析,主要是为了验证前一节对内部页的分析结果,所以,咱就别嫌麻烦了。 文件第4页页头的内容如下:(图中深蓝色部分)

之所以选择第4页,是因为该页为中间叶子,其记录的关键值应该在Key(0)和Key(1)之间。 从上图可以看出,本页有0X2A=42个单元。第1个单元的入口地址为0X03E7,最后一个单元的入口地址为0X006F。 0X03E7单元的内容为:

这是本页关键值最小的记录,可以看出其rowid值为0X2D,恰大于0X2C。 0X006F单元的内容为:

这是本页关键值最大的记录,可以看出其rowid值为0X56=0X56。 下载源码就到源码网,www.codepub.com

源码网资料下载:www.codepub.com 3 索引格式分析

前面分析的都是表数据页的格式。表数据用B+tree来存储,而索引用B-tree来存储。两者的区别主要是:B-tree中只存储关键字段的值和对应记录的rowid值;B-tree树中的内部页也可以存储数据。

3.1 准备数据库

为表创建一个索引。

CREATE INDEX foods_name_idx on foods (name COLLATE NOCASE);

创建索引后文件大小为9K,说明索引有4个页,其B-tree的逻辑结构如下图所示: Page 6,内部页。 Page 7,叶子页。 Page 8,叶子页。 Page 9,叶子页。 此处4个页是连续的,如果在创建表时同时创建索引,然后再插入记录,则用于存储数据的页和用于存储索引的页应该是交叉的。

此时观察page 1的内容,单元指针数组中多了一个单元指针,sqlite_master表中多了索引对象记录,从其数据可以看出其根页为第6页。另外,Schema版本的值变成了2。

3.2 索引页的内部页

现在我们对索引B-tree唯一内部页(也就是根页,文件第6页)的格式进行分析。 文件第6页页头的内容如下:(图中深蓝色部分)

说明:

0X02:说明该页为B-tree的内部页。

0X0000:第1个自由块的偏移量。0,说明当前自由块链表为空。 0X0002:本页有2个单元。

0X03DC:单元内容区的起始位置为0X03DC。 0X00:碎片的字节数,当前为0。

0X00000009:最右儿子的页号,即Ptr(N)。由于本页有2个单元,所以此处即Ptr(2)。其值为0X09,即Ptr(2)指向第9页。第9页是索引数据的最后一页,也是当前文件的最后一页。

单元指针数组在页头之后,有2个指针,分别为0X03F1和0X03DC。

下面来看单元内容区的数据。

0X03F1单元的内容如下:(图中深蓝色部分)

下载源码就到源码网,www.codepub.com

联系客服:779662525#qq.com(#替换为@)