一江春水向东流

做一个有思想的人,期待与每一位热爱思考的人交流,您的关注是对我最大的支持。

  BlogJava :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  44 随笔 :: 139 文章 :: 81 评论 :: 0 Trackbacks
此分析称为简易版,因为后面还计划分析一个更复杂的数据库文件,以深入理解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树组织的好处:查找,删除,增加的快速!把这个文件变大再分析!
posted on 2008-03-27 16:37 allic 阅读(565) 评论(0)  编辑  收藏 所属分类: 算法及数据结构开源数据库学习研究

只有注册用户登录后才能发表评论。


网站导航: