源码网资料下载：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