SQLite在外部数据库中以B-Tree组织。有关B树的详细信息，请参阅****DonaldE.Knuth，计算机编程艺术，第3卷：**“排序和搜索”，第473-480页。Addison-Wesley**PublishingCompany,Reading,Massachusetts。**基本思想是文件中包含的每个页面都包含N个数据库条目和N+1个指向子页面的指针。文件存储在页面中。为什么要这样做，是因为内存分页管理机制在作怪。外部存储器中的每个页面都是B树的一个节点。------------------------------------------------------------|指针(0)|钥匙(0)|指针(1)|钥匙(1)|...|键(N-1)||--------------------------------------------------------------Ptr(0)指向的页面上所有key的值都小于Key(0)。Ptr(1)指向的所有页面和子页面的所有键值都大于Key(0)小于Key(1)。Ptr(N)指向的所有页面和子页面的键值都大于Key(N-1)，以此类推。为了知道一个特定的密钥，需要在O(long(M))中从磁盘读取它，其中M是树的顺序。如果在内存中找不到，则会发生页面错误。主要是解决内存中找不到的问题。一方面，更换一些。一方面，改变一些。改进去的时候需要找出他们在硬盘的哪一页。（B-tree的优点是它适用于使用块存储的存储设备。）使用这个，你可以知道它们在哪些页面上。在SQLite的实现中，一个文件可以包含1个或多个独立的BTree。每个BTree都由其根页面的索引标识。所有条目的密钥和数据构成有效载荷。数据库的页面具有固定的总有效负载。如果负载大于预设值，则将剩余字节存储在溢出页上。条目的有效载荷加上前面的指针构成一个单元。每个页面都有一个小头，其中包含Ptr(N)指针和一些其他信息，例如键和数据大小。格式详细信息文档分为页面。第一页称为第1页，第二页称为第2页，依此类推。页数为0表示没有页。页面大小可以从512到65536。每个页面都是btree页面、freelist页面或溢出页面。第一页必须是btree页面。第一页的前100个字节包含一个特殊的文件头（文件头），它是对文件的描述。文件头数量如下：**OFFSETSIZEDESCRIPTION**016Headerstring（第一个字符串）："SQLiteformat3\000"**162Pagesizeinbytes（页面中的字节数）.**181Fileformatwriteversion（文件写入版本）**191Fileformatreadversion（文件读取版本）**201Bytesofunusedspaceateachpage(unusedwordsattheendofeachpage)section)**211Maxembeddedpayloadfraction**221Minembeddedpayloadfraction**231MinleafpayloadfractionFragmentation)**244Filechangecounter（文件更改计数器）**284Reservedforfutureuse（保留）bytes)**324Firstfreelistpage（第一个freelist页）**364Numberoffreelistpagesinthefile（本文件中的freelist页数）**4060154-bytemetavaluespassedtohigherlayers()**所有整数都是大端。每次修改文件时，文件更改计数器都会递增。该计数器让其他进程知道文件何时被修改以及是否需要清除它们的缓存。最大嵌入式负载片段是一个页面上所有可用空间的总量，可由单个标准B树（非叶数据）表使用。值255表示100%。默认情况下，最大单元格数限制为至少4个单元格才能填满一页。因此，默认的最大嵌入有效负载分片为64。如果页面的有效负载大于最大有效负载，则剩余数据存储在溢出页面中。一旦分配了溢出页，大量数据也可能会被移动到该溢出页，但单元格大小不会小于最小的嵌入有效载荷片段。最小页面负载分片与最小嵌入式负载分片类似，但它应用于LEAFDATA树中的叶节点。LEAFDATA的最大负载分段为100%（或值为255），无需在标头中指定。BTree的每一页分为三部分：表头、单元指针数组、单元内容。页1的页眉中也将有一个100字节的页眉。****|----------------|**|文件头|100字节。仅限第1页。**|----------------|**|页眉|8字节用于叶子。内部节点12个字节**|----------------|**|细胞指针||每个单元格2个字节。已排序。**|数组||向下增长**||v**|----------------|**|未分配|**|空格|**|----------------|^向上生长**|单元格内容||任意顺序散布着自由块。**|面积||和空闲空间碎片。**|-----------------|**页面的标题如下图所示：****OFFSETSIZEDESCRIPTION**01旗帜。1:intkey,2:zerodata,4:leafdata,8:leaf**12byteoffsettothefirstfreeblock**32此页面上的单元格数**52单元格内容区域的第一个字节**71碎片化空闲字节数**84右孩子（Ptr(N)值）。在叶子上省略。**标志定义了这个BTree页面的格式。叶子标志意味着这个页面没有孩子。zerodata0数据表示该页只包含key，没有数据；intkey标志表示密钥是一个整数，并且存储在信元头的密钥大小，而不是在有效载荷区域。网格单元指针数组从页眉开始。网格单元指针数组包含0个或2个以上字节的数字，表示网格单元内容区中网格单元内容相对于文件起始位置的偏移量。网格单元指针是有序的。系统会尽力确保空闲空间位于最后一个网格单元指针之后，以便可以快速添加新的网格单元而无需对页面进行碎片整理。单元格内容存储在页面末尾并向文件开头增长。单元格内容区域中未使用的空间被收集在链表freeblocks上。每个空闲块至少有4个字节。第一个空闲块的偏移量在页眉中给出。Freeblocks的顺序是递增的。因为一个freeblock至少有4个字节，所以cell内容区的3或oh和3个未使用的空间都不能存在于freeblock链表上。这3个或更少的空闲空间称为片段。所有片段的总数被记录并存储在页眉的偏移量7处。**大小说明**下一个空闲块的2字节偏移量**此空闲块中的2字节**单元格的长度可变。网格单元格存储在页面末尾的网格单元格内容区域中。指向网格单元格的单元格指针数组位于页眉之后。网格单元不必连续或有序，但网格单元指针是连续且有序的。单元格内容充分利用了可变长度整数。变长整数从1到9个字节，每个字节的低7位被使用。整个整数由8位字节组成，其中第一个字节的第8位被清除。整数的最高有效字节最先出现。变长整数一般不超过9个字节。作为一种特殊情况，第9个字节的所有8个字节都被视为数据。这允许将64位整数编码为9个字节。**0x00becomes0x00000000**0x7fbecomes0x0000007f**0x810x00becomes0x00000080**0x820x00becomes0x00000100**0x800x7fbecomes0x0000007f**0x8a0x910xd10xac0x78becomes0x12345678**0x810x810x810x810x01becomes0x10204081本篇文章来源Linux公社网站（www.tuohang.net）原文链接：http://www.tuohang.net/Linux/2012-11/75009.htm
