SQLite数据库文件格式分析(B树的基本组织)

此分析称为简易版，因为后面还计划分析一个更复杂的数据库文件，以深入理解SQLite数据库B树实现的结构，从简易的开始不失为一种好的学习方法，这里的简易版本文件是指大 小为2K字节，即每个B树页1K字节，共两个B树页，补充说明一下，这里的B树页就是指经典数据结构书上所讲的B树节点，在这里称为页是因为SQLite 在实现B树时就是使用页page的概念来组织的。创建方法如下：

CREATE TABLE tbl1(one varchar(10),two varchar(10));

INSERT INTO "tbl1" VALUES('first', 'xxx');

INSERT INTO "tbl1" VALUES('second', 'yyy');

然后退出，用UltraEdit打开这个数据库文件：

00000000h: 53 51 4C 69 74 65 20 66 6F 72 6D 61 74 20 33 00 ; SQLite format 3.

00000010h: 04 00 01 01 00 40 20 20 00 00 00 07 00 00 00 00 ; .....@ ........

00000020h: 00 00 00 00 00 00 00 00 00 00 00 03 00 00 00 01 ; ................

00000030h: 00 00 00 00 00 00 00 00 00 00 00 01 00 00 00 00 ; ................

00000040h: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 ; ................

00000050h: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 ; ................

00000060h: 00 00 00 00 0D 00 00 00 01 03 B8 00 03 B8 00 00 ; ..........?.?.

00000070h: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 ; ................

这中间部分全部都是零。省去！

000003a0h: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 ; ................

000003b0h: 00 00 00 00 00 00 00 00 46 01 06 17 15 15 01 71 ; ........F......q

000003c0h: 74 61 62 6C 65 74 62 6C 31 74 62 6C 31 02 43 52 ; tabletbl1tbl1.CR

000003d0h: 45 41 54 45 20 54 41 42 4C 45 20 74 62 6C 31 28 ; EATE TABLE tbl1(

000003e0h: 6F 6E 65 20 76 61 72 63 68 61 72 28 31 30 29 2C ; one varchar(10),

000003f0h: 74 77 6F 20 76 61 72 63 68 61 72 28 31 30 29 29 ; two varchar(10))

这是第一个B树页，这个B树页里存放了表sqlite_master的信息，这就是SQLite数据库的系统表了。

下面分析一下这些二进制的具体涵义，SQLite统一采用大端法来表示数据，不同与一般intel机器的小端法了：

偏移地址 大小 涵义

0 16 "SQLite format 3/000"

16 2 400H＝1024个字节，每个页面的字节数

18 2 0101H表示版本号而已

20 1 每页末端的未用空间，这里为零表示数据都是从每页最后一个字节开始存放

21 1 最大负载分片数，类似与IP分片，一页存不下，要分片

22 1 最小负载分片数

23 1 最小叶子负载分片数

24 4 文件修改计数，用于实现并行访问

28 4 保留未用

32 4 第一个freelist页

36 4 文件中的freelist页数

40 60 这里未用

上面的这一百个字节称为数据库文件的文件头，这个文件头只有第一个B树页才有，后面的每一个B树页都没有这个结构，后面每一页结构都相同：

依次为：B树页头结构，B树指针结构，未用空间，B树实际数据负载。

这里和经典数据结构书上的B树结构有些出入，这里的目的是实际应用方便，而书上的结构目的是解释清楚B树的原理。所以有些不同：

一般书上讲的一个B树页的结构为：指针，数据，指针，数据，指针，数据，...，指针

而SQLite组织为：指针，指针，指针，...，指针，数据，数据，...数据。

第一个页面中从00000060h行第五个字节开始就表示B树页头结构了：

偏移地址 大小 涵义

0 1 0Dh＝1101b各位意义为1: intkey, 2: zerodata, 4: leafdata, 8: leaf

1 2 第一个空闲块的字节偏移量，这里为0

3 2 01，这个B树页存放的记录数为1个，即系统表中只存放了一条记录，因为只创建了一个表tbl1

5 2 负载区首地址，03B8，往下看到000003b0h行那个46就是负载区的开始了

7 1 分片数，这里数据少，不考虑，所以为0

到0000006Bh偏移处B数头结束了，接下来的就是B数指针结构了，此处只有一项，只有一个指针03B8h处。

从000003B8h偏移到结束都是sqlite_master表的实际数据了。当然这些数据也是有结构的。46h表示这条记录有70个字节，除去其本身46，和后面的01是索引外，整个记录刚好是70个字节，01索引后面都是payload负载数据了。

如法炮制，下面列出第二个B树页：

00000400h: 0D 00 00 00 02 03 E5 00 03 F3 03 E5 00 00 00 00 ; ......?.??...

00000410h: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 ; ................

这中间部分全部为零。省去！

000007d0h: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 ; ................

000007e0h: 00 00 00 00 00 0C 02 03 19 13 73 65 63 6F 6E 64 ; ..........second

000007f0h: 79 79 79 0B 01 03 17 13 66 69 72 73 74 78 78 78 ; yyy.....firstxxx

由于不是第一页，所以不存在文件头的100个字节了，一开始就是B树页头结构了，这里有两个指针03F3和03E5，其它的和上面一样。整个数据库管理系统就是准确无误地对这个文件进行管理。

进一步的工作：只有数据多了，才能看出B树组织的好处：查找，删除，增加的快速！把这个文件变大再分析！