SQLite数据库文件格式,sqlite文件格式
相关源代码: btreeInt.h(以下很多内容都在这个文件的注释中) Btree.h Btree.csqlite数据库内部由一组可扩展的数组组成,每个数组项是一个页(page),页号从1开始,页号0为null,物理上不存在。从sqlite数据库文件的0偏移开始这些页一个接一个的排列着。
页类型
leaf, internal, overflow, and free
叶子页、内部页、溢出页,空闲页页结构如下:
** |----------------| ** | file header | 100 bytes. Page 1 only. 文件头(100字节) ** |----------------| ** | page header | 8 bytes for leaves. 12 bytes for interior nodes (叶子页8字节,内部页12字节) ** |----------------| ** | cell pointer | | 2 bytes per cell. Sorted order.(单元指针数组) ** | array | | Grows downward ** | | v ** |----------------| ** | unallocated | ** | space | ** |----------------| ^ Grows upwards (未分配空间) ** | cell content | | Arbitrary order interspersed with freeblocks. ** | area | | and free space fragments. (单元内容区) ** |----------------|Btree页内部以单元(cell)为单位来组织数据,一个单元包含一个(或部分,当使用溢出页时)payload(也称为Btree记录)。由于各类数据大小各不相同,每个单元的大小也就是可变的,所以Btree页内部的空间需要进行动态分配(程序内部动态分配,不是动态申请空间),单元是Btree页内部进行空间分配和回收的基本单位。页内所有单元的内容集中在页的底部,称为“单元内容区”,由下向上增长。由于单元的大小可变,因此需要对每个单元在页内的起始位置(称为单元指针)进行记录。单元指针保存在单元指针数组中,位于页头之后。单元指针数组包含0个或多个指针,由上向下增长。单元指针数组和单元内容区相向增长,中间部分为未分配空间。系统尽量保证未分配空间位于最后的指针之后,这样,就很容易增加新的单元,而不需要整理碎片。 单元不需要是相邻和有序的,但单元指针是相邻和有序的。每个指针占2个字节,表示该单元在单元内容区中距页开始处的偏移。页中单元的数量保存在页头中。
文件头: 每个btree页由三部分组成:页头、单元指针数组、单元内容。数据库第一页还有额外100字节地文件头。
除了在页号1的位置,sqlite可以使用任何类型的页。1号页总是一个B+树的内部页。这个页在偏移0的位置包含了100字节的文件头,描述了这个数据库的特性。sqlite创建数据库文件的时候初始化文件头。文件头结构如下:
Table 2-1. Structure of database file header
Offset Size Description 内容 0 16 Header string SQLITE format 3 16 2 Page size in bytes 每页的大小(字节数) 18 1 File format write version 默认为1 19 1 File format read version 默认为1 20 1 Bytes reserved at the end of each page 页预留空间(字节) 21 1 Max embedded payload fraction 一个cell/record在内部页中可占用的最大空间 22 1 Min embedded payload fraction 一个cell/record在内部页中可占用的最小空间23 1 Min leaf payload fraction 一个cell/record在叶子页中可占用的最小空间
24 4 File change counter 用于事务,每个事务都会引起该值增加,由pager管理 28 4 Reserved for future use
32 4 First freelist page 空闲页链表,下面有详细说明 36 4 Number of freelist pages 空闲页数量 40 60 15 4-byte meta values
关于这个文件头结构在sqlite源码sqliteInt.h中有详细介绍。 ** OFFSET SIZE DESCRIPTION ** 0 16 Header string: "SQLite format 3\000" ** 16 2 Page size in bytes. (1 means 65536) ** 18 1 File format write version ** 19 1 File format read version ** 20 1 Bytes of unused space at the end of each page ** 21 1 Max embedded payload fraction (must be 64) ** 22 1 Min embedded payload fraction (must be 32) ** 23 1 Min leaf payload fraction (must be 32) ** 24 4 File change counter ** 28 4 Reserved for future use ** 32 4 First freelist page ** 36 4 Number of freelist pages in the file ** 40 60 15 4-byte meta values passed to higher layers ** ** 40 4 Schema cookie ** 44 4 File format of schema layer ** 48 4 Size of page cache ** 52 4 Largest root-page (auto/incr_vacuum) ** 56 4 1=UTF-8 2=UTF16le 3=UTF16be ** 60 4 User version ** 64 4 Incremental vacuum mode ** 68 4 Application-ID ** 72 20 unused ** 92 4 The version-valid-for number ** 96 4 SQLITE_VERSION_NUMBER
** 页头格式如下: ** ** OFFSET SIZE DESCRIPTION ** 0 1 Flags. 1: intkey, 2: zerodata, 4: leafdata, 8: leaf 页类型 ** 1 2 byte offset to the first freeblock 第一个自由块的偏移 ** 3 2 number of cells on this page 本页cell的数量 ** 5 2 first byte of the cell content area 第一个cell内容的起始地址 ** 7 1 number of fragmented free bytes 碎片字节数 ** 8 4 Right child (the Ptr(N) value). Omitted on leaves.右孩子页号。叶子页没有此属性。 页类型: 如果leaf位被设置,则该页是一个叶子页,没有儿子; 如果zerodata位被设置,则该页只有关键字,而没有数据; 如果intkey位被设置,则关键字是整型; 如果leafdata位设置,则tree只存储数据在叶子页。 注: 以上内容见于大多数SQLite介绍性文档,btreeInt.h中也这么说。但通过分析程序代码,结论如下: 上述描述与实际实现是矛盾的。可以这样理解:就不用管各标志位的含义了,如果是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的地方。这个值为单元内容区域和未使用区域的分界线。
空闲块格式: ** SIZE DESCRIPTION ** 2 Byte offset of the next freeblock 下一个空闲块的偏移量 ** 2 Bytes in this freeblock 当前空闲块的字节数
最右儿子的页号: 如果本Btree页是叶子页,则无此域,页头长为8个字节。如果本Btree页为内部页,则有此域,页头长为12个字节。页头偏移为8的4个字节包含指向最右儿子的指针。
溢出页: 溢出页形成了一个链表。除了最后一页的所有页都填满数据,最后一个页甚至有可能只有1字节的数据。一个溢出页不会存储来自两个单元的数据。
空闲页:
文件头32字节偏移处的空闲链表结构如下:
主干页格式如下: 4字节页号,指向下一个主干页 4字节整数表示该页叶子页指针的数量 0或多于4字节的叶子页
当一个页变得不活跃时(无用)时,sqlite就把它加入空闲链中,而不会归还给文件系统。当有新的数据加入数据库时,sqlite就从空闲链中取出新的页面来存储信息。如果空闲链为空,sqlite就向操作系统申请新的页来扩展。 命令“vacuum”可以重写当前数据库,在事务的保护下释放空闲链表,缩小数据库文件。
cell结构: ** SIZE DESCRIPTION ** 4 Page number of the left child. Omitted if leaf flag is set. (左孩子页号,叶子页忽略) ** var Number of bytes of data. Omitted if the zerodata flag is set. (数据的字节数) ** var Number of bytes of key. Or the key itself if intkey flag is set. (key的字节数) ** * Payload ** 4 First page of the overflow chain. Omitted if no overflow (溢出页的首页页号,无溢出页则忽略)
一、叶子页
单元是一个变长的字节串。一个单元包含一个(或部分,当使用溢出页时)payload。 payload格式: 每个payload由两部分组成。第1部分是记录头,由N+1个可变长整数组成,N为记录中的字段数。第1个可变长整数(header-size)的值为记录头的字节数。跟着的N个可变长整数与记录的各字段一一对应, 表示各字段的数据类型和宽度。用可变长整数表示各字段类型和宽度的规定如下表所示: header-size的值包括header-size本身的字节和Type1~TypeN的字节。
二、内部页 ** ---------------------------------------------------------------- ** | Ptr(0) | Key(0) | Ptr(1) | Key(1) | ... | Key(N-1) | Ptr(N) | ** ---------------------------------------------------------------- B+tree中根页(rootpage)和内部页(internalpages)都是用来导航的,这些页的指针域都是指向下级页的指针,数据域仅仅包含关键字。所有的数据库记录都存储在叶子页(leafpages)内。 在叶节点一级,页和页内的单元都是按照关键字的顺序排列的,所以B+tree可以沿水平方向遍历,时间复杂度为O(1)。 内部页包含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)。
注: 参考资料: 1、inside SQLite第二章 数据库文件格式(我尝试翻译了下,但是翻的太烂了。。。嘿嘿) 2、百度文库一篇文章,分析得非常详细,非常棒。我有很大一部分是整理的这位作者的,附上原作者。 http://wenku.baidu.com/link?url=SlUW-5xFiU4mLCJy9PWw5xdEbFoNVmYd8k-Nq1dgFqs-lhmS5ldEoJKLoySjFMufBPywwLHu04_hPsc5INvRmD66CZHhf4e7pvuURLLTdNq 3、源码注释说明
本站文章为和通数据库网友分享或者投稿,欢迎任何形式的转载,但请务必注明出处.
同时文章内容如有侵犯了您的权益,请联系QQ:970679559,我们会在尽快处理。