SQLite 存储模型(1)

╰半夏微凉° 2022-07-26 12:21 207阅读 0赞

写在前面：SQLite作为嵌入式数据库，通常针对的应用的数据量相对于通常DBMS的数据量是较小的。所以它的存储模型设计得非常简单，总的来说，SQLite把一个数据文件分成若干大小相等的页面，然后以B树的形式来组织这些页面。而对于大型的数据库管理系统，比如Oracle，或者DM ，存储模型要复杂得多。就拿Oracle来说吧，它对数据文件不仅从物理进行分块，而且从逻辑上进行分段，盘区和页的一个层次划分，DM也一样。不管怎么说，数据库文件要存储大量的数据，为了更好管理，查询和操作数据文件，DBMS不得不从物理上、逻辑上对数据文件的数据进行复杂的组织。本节主要讨论文件格式，下节讨论页面格式。

1、文件格式

1.1、数据库名称  
应用程序通过sqlite3\_open API来打开数据库，该函数的一个参数为数据库文件的名称。SQLite内部命名为main数据库(除了临时数据库和内存数据库)。SQLite对每一个数据库都创建一个独立的文件。  
在SQLite内部，数据文件名不是数据库名。SQLite对应用程序的每一个连接都维护着一个单独的临时数据库(temp数据库)，临时数据库存临时对象，例如：表以及相应的索引。这些临时对象仅仅对同一个连接可见（对同一个线程，进程的其它连接是不可见的），SQLite存储临时数据库到一个单独的临时文件中，当应用程序关闭对main数据库的连接时，就删除临时文件。  
  
1.2、数据库文件结构

除了内存数据库，SQLite把一个数据库(main和temp)都存储到一个单独的文件。

1.2.1、页面(page)  
为了更好的管理和读/写数据库，SQLite把一个数据库(包括内存数据库)分成一个个固定大小的页面。页面大小的范围从512－32768（两者都包含），页面默认大小为1024个字节(1KB)，实际上，页面的上限由2个字节的有符号整数决定。整个数据库可以看成这些页面的数组，页面数组的下标为页面的编号(page number)，page number从1开始，一直到2,147,483,647 (2^31– 1)。实际上，数组上界还受文件系统允许的最大文件大小决定。0号页面视为空页面(NULL page)，物理上不存在，1号页面从文件的0偏移处开始，一个页面接着下一个页面。

注：一旦数据库创建，SQLite使用编译时确定的默认的页面大小。当然，在创建第一个表之前，可以通过pragma命令改变页面大小。SQLite把该值作为元数据的一部分存储在文件中。

1.2.2、页面类型  
页面(page)分四种类型：叶子页面(leaf)，内部页面(internal)，溢出页面(overflow)和空闲页面(free)。内部页面包含查询时的导航信息，叶子页面存储数据，例如元组。如果一个元组的数据太大，一个页面容纳不下，则一些数据存储在B树的页面中，余下的存储在溢出页面中。  
1.2.3、文件头（file header）

作为文件开始的1号页面比较特殊，它包括100个字节的文件头。当SQLite创建文件时例初始化文件头，文件头的格式如下：

<table style="margin:0px 0px 0px 0.45pt; padding:0px; border-collapse:collapse; border-spacing:0px; border:medium none; word-break:break-word; color:rgb(0,0,0); font-family:Verdana,Arial,Helvetica,sans-serif; font-size:12px; line-height:18px; width:952px; background-color:rgb(245,250,254)"> 
 <tbody style="margin:0px; padding:0px"> 
 <tr style="margin:0px; padding:0px"> 
 <td colspan="3" style="margin:0px; padding:0cm 5.4pt; border:1pt solid windowtext; border-collapse:collapse"> <h5 style="margin:15px auto 2px; padding:0px; font-size:12px; color:rgb(51,51,51)"> Structure of database file header</h5> </td> 
 </tr> 
 <tr style="margin:0px; padding:0px"> 
 <td style="margin:0px; padding:0cm 5.4pt; border-width:medium 1pt 1pt; border-style:none solid solid; border-color:silver; border-collapse:collapse"> Offset </td> 
 <td style="margin:0px; padding:0cm 5.4pt; border-width:medium 1pt 1pt medium; border-style:none solid solid none; border-color:silver; border-collapse:collapse"> Size </td> 
 <td style="margin:0px; padding:0cm 5.4pt; border-width:medium 1pt 1pt medium; border-style:none solid solid none; border-color:silver; border-collapse:collapse"> Description </td> 
 </tr> 
 <tr style="margin:0px; padding:0px"> 
 <td style="margin:0px; padding:0cm 5.4pt; border-width:medium 1pt 1pt; border-style:none solid solid; border-color:silver; border-collapse:collapse"> 0 </td> 
 <td style="margin:0px; padding:0cm 5.4pt; border-width:medium 1pt 1pt medium; border-style:none solid solid none; border-color:silver; border-collapse:collapse"> 16 </td> 
 <td style="margin:0px; padding:0cm 5.4pt; border-width:medium 1pt 1pt medium; border-style:none solid solid none; border-color:silver; border-collapse:collapse"> Header string &nbsp; </td> 
 </tr> 
 <tr style="margin:0px; padding:0px"> 
 <td style="margin:0px; padding:0cm 5.4pt; border-width:medium 1pt 1pt; border-style:none solid solid; border-color:silver; border-collapse:collapse"> 16 </td> 
 <td style="margin:0px; padding:0cm 5.4pt; border-width:medium 1pt 1pt medium; border-style:none solid solid none; border-color:silver; border-collapse:collapse"> 2 </td> 
 <td style="margin:0px; padding:0cm 5.4pt; border-width:medium 1pt 1pt medium; border-style:none solid solid none; border-color:silver; border-collapse:collapse"> Page size in bytes </td> 
 </tr> 
 <tr style="margin:0px; padding:0px"> 
 <td style="margin:0px; padding:0cm 5.4pt; border-width:medium 1pt 1pt; border-style:none solid solid; border-color:silver; border-collapse:collapse"> 18 </td> 
 <td style="margin:0px; padding:0cm 5.4pt; border-width:medium 1pt 1pt medium; border-style:none solid solid none; border-color:silver; border-collapse:collapse"> 1 </td> 
 <td style="margin:0px; padding:0cm 5.4pt; border-width:medium 1pt 1pt medium; border-style:none solid solid none; border-color:silver; border-collapse:collapse"> File format write version &nbsp; </td> 
 </tr> 
 <tr style="margin:0px; padding:0px"> 
 <td style="margin:0px; padding:0cm 5.4pt; border-width:medium 1pt 1pt; border-style:none solid solid; border-color:silver; border-collapse:collapse"> 19 </td> 
 <td style="margin:0px; padding:0cm 5.4pt; border-width:medium 1pt 1pt medium; border-style:none solid solid none; border-color:silver; border-collapse:collapse"> 1 </td> 
 <td style="margin:0px; padding:0cm 5.4pt; border-width:medium 1pt 1pt medium; border-style:none solid solid none; border-color:silver; border-collapse:collapse"> File format read version </td> 
 </tr> 
 <tr style="margin:0px; padding:0px"> 
 <td style="margin:0px; padding:0cm 5.4pt; border-width:medium 1pt 1pt; border-style:none solid solid; border-color:silver; border-collapse:collapse"> 20 </td> 
 <td style="margin:0px; padding:0cm 5.4pt; border-width:medium 1pt 1pt medium; border-style:none solid solid none; border-color:silver; border-collapse:collapse"> 1 </td> 
 <td style="margin:0px; padding:0cm 5.4pt; border-width:medium 1pt 1pt medium; border-style:none solid solid none; border-color:silver; border-collapse:collapse"> Bytes reserved at the end of each page </td> 
 </tr> 
 <tr style="margin:0px; padding:0px"> 
 <td style="margin:0px; padding:0cm 5.4pt; border-width:medium 1pt 1pt; border-style:none solid solid; border-color:silver; border-collapse:collapse"> 21 </td> 
 <td style="margin:0px; padding:0cm 5.4pt; border-width:medium 1pt 1pt medium; border-style:none solid solid none; border-color:silver; border-collapse:collapse"> 1 </td> 
 <td style="margin:0px; padding:0cm 5.4pt; border-width:medium 1pt 1pt medium; border-style:none solid solid none; border-color:silver; border-collapse:collapse"> Max embedded payload fraction </td> 
 </tr> 
 <tr style="margin:0px; padding:0px"> 
 <td style="margin:0px; padding:0cm 5.4pt; border-width:medium 1pt 1pt; border-style:none solid solid; border-color:silver; border-collapse:collapse"> 22 </td> 
 <td style="margin:0px; padding:0cm 5.4pt; border-width:medium 1pt 1pt medium; border-style:none solid solid none; border-color:silver; border-collapse:collapse"> 1 </td> 
 <td style="margin:0px; padding:0cm 5.4pt; border-width:medium 1pt 1pt medium; border-style:none solid solid none; border-color:silver; border-collapse:collapse"> Min embedded payload fraction </td> 
 </tr> 
 <tr style="margin:0px; padding:0px"> 
 <td style="margin:0px; padding:0cm 5.4pt; border-width:medium 1pt 1pt; border-style:none solid solid; border-color:silver; border-collapse:collapse"> 23 </td> 
 <td style="margin:0px; padding:0cm 5.4pt; border-width:medium 1pt 1pt medium; border-style:none solid solid none; border-color:silver; border-collapse:collapse"> 1 </td> 
 <td style="margin:0px; padding:0cm 5.4pt; border-width:medium 1pt 1pt medium; border-style:none solid solid none; border-color:silver; border-collapse:collapse"> Min leaf payload fraction </td> 
 </tr> 
 <tr style="margin:0px; padding:0px"> 
 <td style="margin:0px; padding:0cm 5.4pt; border-width:medium 1pt 1pt; border-style:none solid solid; border-color:silver; border-collapse:collapse"> 24 </td> 
 <td style="margin:0px; padding:0cm 5.4pt; border-width:medium 1pt 1pt medium; border-style:none solid solid none; border-color:silver; border-collapse:collapse"> 4 </td> 
 <td style="margin:0px; padding:0cm 5.4pt; border-width:medium 1pt 1pt medium; border-style:none solid solid none; border-color:silver; border-collapse:collapse"> File change counter </td> 
 </tr> 
 <tr style="margin:0px; padding:0px"> 
 <td style="margin:0px; padding:0cm 5.4pt; border-width:medium 1pt 1pt; border-style:none solid solid; border-color:silver; border-collapse:collapse"> 28 </td> 
 <td style="margin:0px; padding:0cm 5.4pt; border-width:medium 1pt 1pt medium; border-style:none solid solid none; border-color:silver; border-collapse:collapse"> 4 </td> 
 <td style="margin:0px; padding:0cm 5.4pt; border-width:medium 1pt 1pt medium; border-style:none solid solid none; border-color:silver; border-collapse:collapse"> Reserved for future use </td> 
 </tr> 
 <tr style="margin:0px; padding:0px"> 
 <td style="margin:0px; padding:0cm 5.4pt; border-width:medium 1pt 1pt; border-style:none solid solid; border-color:silver; border-collapse:collapse"> 32 </td> 
 <td style="margin:0px; padding:0cm 5.4pt; border-width:medium 1pt 1pt medium; border-style:none solid solid none; border-color:silver; border-collapse:collapse"> 4 </td> 
 <td style="margin:0px; padding:0cm 5.4pt; border-width:medium 1pt 1pt medium; border-style:none solid solid none; border-color:silver; border-collapse:collapse"> First freelist page </td> 
 </tr> 
 <tr style="margin:0px; padding:0px"> 
 <td style="margin:0px; padding:0cm 5.4pt; border-width:medium 1pt 1pt; border-style:none solid solid; border-color:silver; border-collapse:collapse"> 36 </td> 
 <td style="margin:0px; padding:0cm 5.4pt; border-width:medium 1pt 1pt medium; border-style:none solid solid none; border-color:silver; border-collapse:collapse"> 4 </td> 
 <td style="margin:0px; padding:0cm 5.4pt; border-width:medium 1pt 1pt medium; border-style:none solid solid none; border-color:silver; border-collapse:collapse"> Number of freelist pages </td> 
 </tr> 
 <tr style="margin:0px; padding:0px"> 
 <td style="margin:0px; padding:0cm 5.4pt; border-width:medium 1pt 1pt; border-style:none solid solid; border-color:silver; border-collapse:collapse"> 40 </td> 
 <td style="margin:0px; padding:0cm 5.4pt; border-width:medium 1pt 1pt medium; border-style:none solid solid none; border-color:silver; border-collapse:collapse"> 60 </td> 
 <td style="margin:0px; padding:0cm 5.4pt; border-width:medium 1pt 1pt medium; border-style:none solid solid none; border-color:silver; border-collapse:collapse"> 15 4-byte meta values </td> 
 </tr> 
 </tbody> 
</table>

示例数据（100个字节）：

<table style="margin:0px; padding:0px; border-collapse:collapse; border-spacing:0px; border:medium none; word-break:break-word; color:rgb(0,0,0); font-family:Verdana,Arial,Helvetica,sans-serif; font-size:12px; line-height:18px; background-color:rgb(245,250,254)"> 
 <tbody style="margin:0px; padding:0px"> 
 <tr style="margin:0px; padding:0px"> 
 <td style="margin:0px; padding:0cm 5.4pt; border:1pt solid windowtext; border-collapse:collapse; width:426.1pt"> 53 51 4C 69 74 65 20 66&nbsp;SQLite f 6F 72 6D 61 74 20 33 00&nbsp;ormat 3. 04 00 01 01 00 40 20 20&nbsp;.....@&nbsp; 00 00 00 11 00 00 00 00&nbsp;........ 00 00 00 00 00 00 00 00&nbsp;........ 00 00 00 01 00 00 00 01&nbsp;........ 00 00 00 00 00 00 00 00&nbsp;........ 00 00 00 01 00 00 00 00&nbsp;........ 00 00 00 00 00 00 00 00&nbsp;........ 00 00 00 00 00 00 00 00&nbsp;........ 00 00 00 00 00 00 00 00&nbsp;........ 00 00 00 00 00 00 00 00&nbsp;........ 00 00 00 00 </td> 
 </tr> 
 </tbody> 
</table>

Header string(头字符串)：  
16个字节："SQLite format 3."  
  
Page size：  
页面大小：0x04 00 ，即1024  
File format：  
文件格式：0x01 ，0x01，在当前的版本都为1。  
  
Reserved space：  
保留空间：0x00，1个字节，SQLite在每个页面的末尾都会保留一定的空间，留作它用，默认为0。  
  
Embedded payload：  
max embedded payload fraction(偏移21)的值限定了B树内节点（页面）中一个元组（记录，单元）最多能够使用的空间。255意味着100%，默认值为0x40，即64（25%），这保证了一个结点（页面）至少有4个单元。如果一个单元的负载(payload，即数据量)超过最大值，则溢出的数据保存到溢出的页面，一旦SQLite分配了一个溢出页面，它会尽可能多的移动数据到溢出页面，下限为min embedded payload fraction value（偏移为22），默认的值为32，即12.5% 。  
  
min leaf payload fraction的含义与min embedded payload fraction类似，只不过是它是针对B树的叶子结点，默认值为32，即12.5%，叶子结点最大的负载为通常是100%，这不用保存。  
  
File change counter：  
文件修改计数，通常被事务使用，它由事务增加其值。该值的主要目的是数据库改变时，pager避免对缓存进行刷盘。  
Freelist：  
空闲页面链表，在文件头偏移32的4个字节记录着空闲页面链的第一个页面，偏移36处的4个字节为空闲页面的数量。空闲页面链表的组织形式如下：  
![sqlite_file_1.JPG][]

空闲页面分为两种页面：trunk pages（主页面）和leaf pages(叶子页面)。文件头的指针指向空闲链表的第一个trunk page，每个trunk page指向多个叶子页面。  
Trunk page的格式如下，从页面的起始处开始：  
(1)4个字节，指向下一个trunk page的页面号；  
(2)4个字节，该页面的叶子页面指针的数量；  
(3)指向叶子页面的页面号，每项4个字节。  
  
当一个页面不再使用时，SQLite把它加入空闲页面链表，并不从本地文件系统中释放掉。当添加新的数据到数据库时，SQLite就从空闲链表上取出空闲页面用来在存储数据。当空闲链表为空时，SQLite就通过本地文件系统增加新的页面，添加到数据库文件的末尾。  
  
注：可以通过vacuum命令删除空闲链表，该命令通过把数据库中数据拷贝到临时文件，然后在事务的保护下，用临时文件中的复本覆盖原数据库文件。  
  
Meta variables  
元数据变量：从偏移为40开始，为15个4字节的元数据变量，这些元数据主要与B树和VM有关。如下：

<table style="margin:0px; padding:0px; border-collapse:collapse; border-spacing:0px; border:medium none; word-break:break-word; color:rgb(0,0,0); font-family:Verdana,Arial,Helvetica,sans-serif; font-size:12px; line-height:18px; background-color:rgb(245,250,254)"> 
 <tbody style="margin:0px; padding:0px"> 
 <tr style="margin:0px; padding:0px"> 
 <td style="margin:0px; padding:0cm 5.4pt; border:1pt solid windowtext; border-collapse:collapse; width:426.1pt"> &nbsp;** Meta values are as follows: &nbsp;**&nbsp;&nbsp;&nbsp;&nbsp;meta[0]&nbsp;&nbsp; Schema cookie.&nbsp;Changes with each schema change. &nbsp;**&nbsp;&nbsp;&nbsp;&nbsp;meta[1]&nbsp;&nbsp; File format of schema layer. &nbsp;**&nbsp;&nbsp;&nbsp;&nbsp;meta[2]&nbsp;&nbsp; Size of the page cache. &nbsp;**&nbsp;&nbsp;&nbsp;&nbsp;meta[3]&nbsp;&nbsp; Use freelist if 0.&nbsp;Autovacuum if greater than zero. &nbsp;**&nbsp;&nbsp;&nbsp;&nbsp;meta[4]&nbsp;&nbsp; Db text encoding. 1:UTF-8 2:UTF-16LE 3:UTF-16BE &nbsp;**&nbsp;&nbsp;&nbsp;&nbsp;meta[5]&nbsp;&nbsp; The user cookie. Used by the application. &nbsp;**&nbsp;&nbsp;&nbsp;&nbsp;meta[6]&nbsp;&nbsp; &nbsp;**&nbsp;&nbsp;&nbsp;&nbsp;meta[7] &nbsp;**&nbsp;&nbsp;&nbsp;&nbsp;meta[8] &nbsp;**&nbsp;&nbsp;&nbsp;&nbsp;meta[9]&nbsp; </td> 
 </tr> 
 </tbody> 
</table>

1.2.4、读取文件头  
当应用程序调用API sqlite3\_open打开数据库文件时，SQLite就会读取文件头进行数据库的初始化。

int sqlite3BtreeOpen(  
constchar\*zFilename, /\* Name of the file containing the BTree database \*/  
sqlite3 \*pSqlite, /\* Associated database handle \*/  
Btree \*\*ppBtree, /\* Pointer to new Btree object written here \*/  
int flags /\* Options \*/  
)\{  
//读取文件头  
 sqlite3pager\_read\_fileheader(pBt\->pPager, sizeof(zDbHeader), zDbHeader);  
//设置页面大小  
pBt\->pageSize = get2byte(&zDbHeader\[16\]);  
//…  
\}![复制代码][copycode.gif]

3、页面结构（page structure）

数据库文件分成固定大小的页面。SQLite通过B+tree模型来管理所有的页面。页面(page)分三种类型：要么是tree page，或者是overflow page，或者是free page。

3.1、Tree page structure  
每个tree page分成许多单元(cell)，一个单元包含一个(或部分)payload。Cell是tree page进行分配或回收的基本单位。  
一个tree page分成四个部分：

![sqlite8-2-1.JPG][]

(1)The page header  
(2)The cell content area  
(3)The cell pointer array  
(4)Unallocated space  
Cell 指针数组与cell content相向增长。一个page header仅包含用来管理页面的信息，它通常位于页面的开始处(但是对于数据库文件的第一个页面，它开始第100个字节处，前100个字节包含文件头信息(file header))。  
Structure of tree page header

<table style="margin:0px 0px 0px 0.25pt; padding:0px; border-collapse:collapse; border-spacing:0px; border:medium none; word-break:break-word; color:rgb(0,0,0); font-family:Verdana,Arial,Helvetica,sans-serif; font-size:12px; line-height:18px; width:957px; background-color:rgb(245,250,254)"> 
 <tbody style="margin:0px; padding:0px"> 
 <tr style="margin:0px; padding:0px"> 
 <td style="margin:0px; padding:0cm 5.4pt; border:1pt solid windowtext; border-collapse:collapse"> Offset </td> 
 <td style="margin:0px; padding:0cm 5.4pt; border-width:1pt 1pt 1pt medium; border-style:solid solid solid none; border-color:silver; border-collapse:collapse"> Size </td> 
 <td style="margin:0px; padding:0cm 5.4pt; border-width:1pt 1pt 1pt medium; border-style:solid solid solid none; border-color:silver; border-collapse:collapse"> Description </td> 
 </tr> 
 <tr style="margin:0px; padding:0px"> 
 <td style="margin:0px; padding:0cm 5.4pt; border-width:medium 1pt 1pt; border-style:none solid solid; border-color:silver; border-collapse:collapse"> 0 </td> 
 <td style="margin:0px; padding:0cm 5.4pt; border-width:medium 1pt 1pt medium; border-style:none solid solid none; border-color:silver; border-collapse:collapse"> 1 </td> 
 <td style="margin:0px; padding:0cm 5.4pt; border-width:medium 1pt 1pt medium; border-style:none solid solid none; border-color:silver; border-collapse:collapse"> Flags. 1: intkey, 2: zerodata, 4: leafdata, 8: leaf </td> 
 </tr> 
 <tr style="margin:0px; padding:0px"> 
 <td style="margin:0px; padding:0cm 5.4pt; border-width:medium 1pt 1pt; border-style:none solid solid; border-color:silver; border-collapse:collapse"> 1 </td> 
 <td style="margin:0px; padding:0cm 5.4pt; border-width:medium 1pt 1pt medium; border-style:none solid solid none; border-color:silver; border-collapse:collapse"> 2 </td> 
 <td style="margin:0px; padding:0cm 5.4pt; border-width:medium 1pt 1pt medium; border-style:none solid solid none; border-color:silver; border-collapse:collapse"> Byte offset to the first free block </td> 
 </tr> 
 <tr style="margin:0px; padding:0px"> 
 <td style="margin:0px; padding:0cm 5.4pt; border-width:medium 1pt 1pt; border-style:none solid solid; border-color:silver; border-collapse:collapse"> 3 </td> 
 <td style="margin:0px; padding:0cm 5.4pt; border-width:medium 1pt 1pt medium; border-style:none solid solid none; border-color:silver; border-collapse:collapse"> 2 </td> 
 <td style="margin:0px; padding:0cm 5.4pt; border-width:medium 1pt 1pt medium; border-style:none solid solid none; border-color:silver; border-collapse:collapse"> Number of cells on this page </td> 
 </tr> 
 <tr style="margin:0px; padding:0px"> 
 <td style="margin:0px; padding:0cm 5.4pt; border-width:medium 1pt 1pt; border-style:none solid solid; border-color:silver; border-collapse:collapse"> 5 </td> 
 <td style="margin:0px; padding:0cm 5.4pt; border-width:medium 1pt 1pt medium; border-style:none solid solid none; border-color:silver; border-collapse:collapse"> 2 </td> 
 <td style="margin:0px; padding:0cm 5.4pt; border-width:medium 1pt 1pt medium; border-style:none solid solid none; border-color:silver; border-collapse:collapse"> First byte of the cell content area </td> 
 </tr> 
 <tr style="margin:0px; padding:0px"> 
 <td style="margin:0px; padding:0cm 5.4pt; border-width:medium 1pt 1pt; border-style:none solid solid; border-color:silver; border-collapse:collapse"> 7 </td> 
 <td style="margin:0px; padding:0cm 5.4pt; border-width:medium 1pt 1pt medium; border-style:none solid solid none; border-color:silver; border-collapse:collapse"> 1 </td> 
 <td style="margin:0px; padding:0cm 5.4pt; border-width:medium 1pt 1pt medium; border-style:none solid solid none; border-color:silver; border-collapse:collapse"> Number of fragmented free bytes </td> 
 </tr> 
 <tr style="margin:0px; padding:0px"> 
 <td style="margin:0px; padding:0cm 5.4pt; border-width:medium 1pt 1pt; border-style:none solid solid; border-color:silver; border-collapse:collapse"> 8 </td> 
 <td style="margin:0px; padding:0cm 5.4pt; border-width:medium 1pt 1pt medium; border-style:none solid solid none; border-color:silver; border-collapse:collapse"> 4 </td> 
 <td style="margin:0px; padding:0cm 5.4pt; border-width:medium 1pt 1pt medium; border-style:none solid solid none; border-color:silver; border-collapse:collapse"> Right child (the Ptr(n) value). Omitted on leaves. </td> 
 </tr> 
 </tbody> 
</table>

Flag定义页面的格式：如果leaf位被设置，则该页面是一个叶子节点，没有孩子；如果zerodata位被设置，则该页面只有关键字，而没有数据；如果intkey位设置，则关键字是整型；如果leafdata位设置，则tree只存储数据在叶子节点。另外，对于内部页面(internal page)，header在第8个字节处包含指向最右边子节点的指针。  
Cell位于页面的高端，而cell 指针数组位于页面的page header之后，cell指针数组包含0个或者多个的指针。每个指针占2个字节，表示在cell content区域的cell距页面开始处的偏移。页面Cell单元的数量位于偏移3处。  
由于随机的插入和删除单元，将会导致一个页面上Cell和空闲区域互相交错。Cell内容区域(cell content area)中没有使用的空间收集起来形成一个空闲块链表，这些空闲块按照它们地址的升序排列。页面头1偏移处的2个字节指向空闲块链表的头。每一个空闲块至少4个字节，每个空闲块的开始4个字节存储控制信息：头2个字节指向下一个空闲块（0意味着没有下一个空闲块了），剩余的2个字节为该空闲块的大小。由于空闲块至少为4个字节大小，所以单元内容空间中的3个字节或更小的空间（叫做fragment）不能存在于空闲块列表中。所有碎片(fragment)的总的字节数将记录在页面头偏移为7的位置(所以太碎片最多为255个字节，在它达到最大值之前，页面会被整理)。单元内容区域的第一个字节记录在页面头偏移为5的地方。这个值为单元内容区域和未使用区域的分界线。

3.2、单元格式(Structure of a cell)

单元是变长的字节串。一个单元存储一个负载(payload)，它的结构如下：

<table style="margin:0px 0px 0px 0.3pt; padding:0px; border-collapse:collapse; border-spacing:0px; border:medium none; word-break:break-word; color:rgb(0,0,0); font-family:Verdana,Arial,Helvetica,sans-serif; font-size:12px; line-height:18px; width:954px; background-color:rgb(245,250,254)"> 
 <tbody style="margin:0px; padding:0px"> 
 <tr style="margin:0px; padding:0px"> 
 <td colspan="2" style="margin:0px; padding:0cm 5.4pt; border:1pt solid windowtext; border-collapse:collapse"> <h5 style="margin:15px auto 2px; padding:0px; font-size:12px; color:rgb(51,51,51)"> Structure of a cell</h5> </td> 
 </tr> 
 <tr style="margin:0px; padding:0px"> 
 <td style="margin:0px; padding:0cm 5.4pt; border-width:medium 1pt 1pt; border-style:none solid solid; border-color:silver; border-collapse:collapse"> Size </td> 
 <td style="margin:0px; padding:0cm 5.4pt; border-width:medium 1pt 1pt medium; border-style:none solid solid none; border-color:silver; border-collapse:collapse"> Description </td> 
 </tr> 
 <tr style="margin:0px; padding:0px"> 
 <td style="margin:0px; padding:0cm 5.4pt; border-width:medium 1pt 1pt; border-style:none solid solid; border-color:silver; border-collapse:collapse"> 4 </td> 
 <td style="margin:0px; padding:0cm 5.4pt; border-width:medium 1pt 1pt medium; border-style:none solid solid none; border-color:silver; border-collapse:collapse"> Page number of the left child. Omitted if&nbsp;leaf&nbsp;flag bit is set. </td> 
 </tr> 
 <tr style="margin:0px; padding:0px"> 
 <td style="margin:0px; padding:0cm 5.4pt; border-width:medium 1pt 1pt; border-style:none solid solid; border-color:silver; border-collapse:collapse"> var(1–9) </td> 
 <td style="margin:0px; padding:0cm 5.4pt; border-width:medium 1pt 1pt medium; border-style:none solid solid none; border-color:silver; border-collapse:collapse"> Number of bytes of data. Omitted if the&nbsp;zerodata&nbsp;flag bit is set. </td> 
 </tr> 
 <tr style="margin:0px; padding:0px"> 
 <td style="margin:0px; padding:0cm 5.4pt; border-width:medium 1pt 1pt; border-style:none solid solid; border-color:silver; border-collapse:collapse"> var(1–9) </td> 
 <td style="margin:0px; padding:0cm 5.4pt; border-width:medium 1pt 1pt medium; border-style:none solid solid none; border-color:silver; border-collapse:collapse"> Number of bytes of key. Or the key itself if&nbsp;intkey&nbsp;flag bit is set. </td> 
 </tr> 
 <tr style="margin:0px; padding:0px"> 
 <td style="margin:0px; padding:0cm 5.4pt; border-width:medium 1pt 1pt; border-style:none solid solid; border-color:silver; border-collapse:collapse"> * </td> 
 <td style="margin:0px; padding:0cm 5.4pt; border-width:medium 1pt 1pt medium; border-style:none solid solid none; border-color:silver; border-collapse:collapse"> Payload </td> 
 </tr> 
 <tr style="margin:0px; padding:0px"> 
 <td style="margin:0px; padding:0cm 5.4pt; border-width:medium 1pt 1pt; border-style:none solid solid; border-color:silver; border-collapse:collapse"> 4 </td> 
 <td style="margin:0px; padding:0cm 5.4pt; border-width:medium 1pt 1pt medium; border-style:none solid solid none; border-color:silver; border-collapse:collapse"> First page of the overflow chain. Omitted if no overflow. </td> 
 </tr> 
 </tbody> 
</table>

对于内部页面，每个单元包含4个字节的左孩子页面指针；对于叶子页面，单元不需要孩子指针。接下来是数据的字节数，和关键字的长度，下图描述了单元格式：(a)一个单元的格式 (b)负载的结构。

![sqlite8-2-2.JPG][]

3.3、溢出页面  
小的元组能够存储在一个页面中，但是一个大的元组可能要扩展到溢出页面，一个单元的溢出页面形成一个单独的链表。每一个溢出页面(除了最后一个页面)全部填充数据(除了最开始处的4个字节)，开始处的4个字节存储下一个溢出页面的页面号。最后一个页面甚至可以只有一个字节的数据，但是一个溢出页面绝不会存储两个单元的数据。  
溢出页面的格式：

![sqlite8-2-3.JPG][]

3.4、实例分析  
数据库为test.db，其中有一个表和索引如下：  
CREATE TABLE episodes( id integer primary key,name text, cid int);  
CREATE INDEX name\_idx on episodes(name);  
3.4.1、叶子页面格式分析：  
Episodes表的根页面为第2个页面(此时episodes表只上一个页面)，表中的数据如下：

下面为2号页面页面头(开始的8个字节)：

![sqlite8-2-4.JPG][]

<table style="margin:0px 0px 0px 0.25pt; padding:0px; border-collapse:collapse; border-spacing:0px; border:medium none; word-break:break-word; color:rgb(0,0,0); font-family:Verdana,Arial,Helvetica,sans-serif; font-size:12px; line-height:18px; width:957px; background-color:rgb(245,250,254)"> 
 <tbody style="margin:0px; padding:0px"> 
 <tr style="margin:0px; padding:0px"> 
 <td style="margin:0px; padding:0cm 5.4pt; border:1pt solid windowtext; border-collapse:collapse"> Offset </td> 
 <td style="margin:0px; padding:0cm 5.4pt; border-width:1pt 1pt 1pt medium; border-style:solid solid solid none; border-color:silver; border-collapse:collapse"> Size </td> 
 <td style="margin:0px; padding:0cm 5.4pt; border-width:1pt 1pt 1pt medium; border-style:solid solid solid none; border-color:silver; border-collapse:collapse"> 值 及含义 </td> 
 </tr> 
 <tr style="margin:0px; padding:0px"> 
 <td style="margin:0px; padding:0cm 5.4pt; border-width:medium 1pt 1pt; border-style:none solid solid; border-color:silver; border-collapse:collapse"> 0 </td> 
 <td style="margin:0px; padding:0cm 5.4pt; border-width:medium 1pt 1pt medium; border-style:none solid solid none; border-color:silver; border-collapse:collapse"> 1 </td> 
 <td style="margin:0px; padding:0cm 5.4pt; border-width:medium 1pt 1pt medium; border-style:none solid solid none; border-color:silver; border-collapse:collapse"> 0x0D: 1: intkey, 2: zerodata, 4: leafdata, 8: leaf </td> 
 </tr> 
 <tr style="margin:0px; padding:0px"> 
 <td style="margin:0px; padding:0cm 5.4pt; border-width:medium 1pt 1pt; border-style:none solid solid; border-color:silver; border-collapse:collapse"> 1 </td> 
 <td style="margin:0px; padding:0cm 5.4pt; border-width:medium 1pt 1pt medium; border-style:none solid solid none; border-color:silver; border-collapse:collapse"> 2 </td> 
 <td style="margin:0px; padding:0cm 5.4pt; border-width:medium 1pt 1pt medium; border-style:none solid solid none; border-color:silver; border-collapse:collapse"> 0x0000:第一个空闲块的偏移为0 </td> 
 </tr> 
 <tr style="margin:0px; padding:0px"> 
 <td style="margin:0px; padding:0cm 5.4pt; border-width:medium 1pt 1pt; border-style:none solid solid; border-color:silver; border-collapse:collapse"> 3 </td> 
 <td style="margin:0px; padding:0cm 5.4pt; border-width:medium 1pt 1pt medium; border-style:none solid solid none; border-color:silver; border-collapse:collapse"> 2 </td> 
 <td style="margin:0px; padding:0cm 5.4pt; border-width:medium 1pt 1pt medium; border-style:none solid solid none; border-color:silver; border-collapse:collapse"> 0x0011:页面的单元数为17 </td> 
 </tr> 
 <tr style="margin:0px; padding:0px"> 
 <td style="margin:0px; padding:0cm 5.4pt; border-width:medium 1pt 1pt; border-style:none solid solid; border-color:silver; border-collapse:collapse"> 5 </td> 
 <td style="margin:0px; padding:0cm 5.4pt; border-width:medium 1pt 1pt medium; border-style:none solid solid none; border-color:silver; border-collapse:collapse"> 2 </td> 
 <td style="margin:0px; padding:0cm 5.4pt; border-width:medium 1pt 1pt medium; border-style:none solid solid none; border-color:silver; border-collapse:collapse"> 0x031C:单元内容区的第一个字节的偏移(距页面起始位置) </td> 
 </tr> 
 <tr style="margin:0px; padding:0px"> 
 <td style="margin:0px; padding:0cm 5.4pt; border-width:medium 1pt 1pt; border-style:none solid solid; border-color:silver; border-collapse:collapse"> 7 </td> 
 <td style="margin:0px; padding:0cm 5.4pt; border-width:medium 1pt 1pt medium; border-style:none solid solid none; border-color:silver; border-collapse:collapse"> 1 </td> 
 <td style="margin:0px; padding:0cm 5.4pt; border-width:medium 1pt 1pt medium; border-style:none solid solid none; border-color:silver; border-collapse:collapse"> 0x00：碎片字节数 </td> 
 </tr> 
 <tr style="margin:0px; padding:0px"> 
 <td style="margin:0px; padding:0cm 5.4pt; border-width:medium 1pt 1pt; border-style:none solid solid; border-color:silver; border-collapse:collapse"> 8 </td> 
 <td style="margin:0px; padding:0cm 5.4pt; border-width:medium 1pt 1pt medium; border-style:none solid solid none; border-color:silver; border-collapse:collapse"> 4 </td> 
 <td style="margin:0px; padding:0cm 5.4pt; border-width:medium 1pt 1pt medium; border-style:none solid solid none; border-color:silver; border-collapse:collapse"> Right child (the Ptr(n) value). Omitted on leaves. </td> 
 </tr> 
 </tbody> 
</table>

来看第2个页面的数据（0x400——0x7ff）：

![sqlite8-2-5.JPG][]

页面头之后为cell指针数组，第一个cell的相对页面起始位置偏移为0x03EB，即文件的0x07EB。该单元的数据为：

![sqlite8-2-6.JPG][]

0x13：数据的字节数，19个字节，即04 00 2B … 61 32。  
0x01：关键字的字节数，对于整型，则为关键字本身，即1。  
0x04：从该字节开始为payload，即记录。0x04为记录头的大小。  
0x00：NULL，id字段的值，由于关键字保存在key size中，这里为NULL  
0x2B：name字段值的长度，为字符串，长度为(43-13)/2=15。  
0x00：NULL，第一条记录cid的值。

[sqlite_file_1.JPG]: /images/20220724/ebfd988a45ca424193b676af52935886.png
[copycode.gif]: /images/20220724/c840c02bd3c44ebca9f7286e53a52e0e.png
[sqlite8-2-1.JPG]: /images/20220724/b3cb8da95d6e4e07b1ff33b57d0f8b4e.png
[sqlite8-2-2.JPG]: /images/20220724/83266645c78d4e69b2621ea3b33df108.png
[sqlite8-2-3.JPG]: /images/20220724/bbca40dad80e474ea6345115416f334e.png
[sqlite8-2-4.JPG]: /images/20220724/ea755913e773491787c7072a21abb216.png
[sqlite8-2-5.JPG]: /images/20220724/f76f0a65c7cf4506a7887fde17814f21.png
[sqlite8-2-6.JPG]: /images/20220724/b30f5236f97f4c65bb21c030216334da.png