求索阁

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创建文件时先初始化文件头，文件头的格式如下：

Structure of database file header
Offset	Size	Description
0	16	Header string
16	2	Page size in bytes
18	1	File format write version
19	1	File format read version
20	1	Bytes reserved at the end of each page
21	1	Max embedded payload fraction
22	1	Min embedded payload fraction
23	1	Min leaf payload fraction
24	4	File change counter
28	4	Reserved for future use
32	4	First freelist page
36	4	Number of freelist pages
40	60	15 4-byte meta values

示例数据（100个字节）：

53 51 4C 69 74 65 20 66 6F 72 6D 61 74 20 33 00 ; SQLite format 3. 04 00 01 01 00 40 20 20 00 00 00 11 00 00 00 00 ; .....@........ 00 00 00 00 00 00 00 00 00 00 00 01 00 00 00 01 ; ................ 00 00 00 00 00 00 00 00 00 00 00 01 00 00 00 00 ; ................ 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 ; ................ 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 ; ................ 00 00 00 00

前16个字节-Header string(头字符串)："SQLite format 3."

0x04 00 ：页面大小-Page size，即1024

0x01 01 ：文件格式-File format（写、读各一字节），在当前的版本都为1。

0x00 ： 保留空间-Reserved space，1个字节，SQLite在每个页面的末尾都会保留一定的空间，留作它用，默认为0。

0x40 20 20 ：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%，这不用保存。

0x00 00 00 11 ：文件修改计数-File change counter，通常被事务使用，它由事务增加其值。该值的主要目的是数据库改变时，pager避免对缓存进行刷盘。

空闲页面链表(Freelist)：在文件头偏移32的4个字节记录着空闲页面链的第一个页面。

空闲页面的数量：偏移36处的4个字节为空闲页面的数量。

空闲页面链表的组织形式如下：

空闲页面分为两种页面：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有关。如下：

** Meta values are as follows: **    meta[0]   Schema cookie. Changes with each schema change. **    meta[1]   File format of schema layer. **    meta[2]   Size of the page cache. **    meta[3]   Use freelist if 0. Autovacuum if greater than zero. **    meta[4]   Db text encoding. 1:UTF-8 2:UTF-16LE 3:UTF-16BE **    meta[5]   The user cookie. Used by the application. **    meta[6]  **    meta[7] **    meta[8] **    meta[9]

1.2.4、读取文件头

当应用程序调用sqlite3_open(API)打开数据库文件时，SQLite就会读取文件头进行数据库的初始化。

 

int sqlite3BtreeOpen(

const char *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]);

//…

}

2.页面结构(page structure)

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

2.1、Tree page structure

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

一个tree page分成四个部分：

(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：

Offset	Size	Description
0	1	Flags. 1: intkey, 2: zerodata, 4: leafdata, 8: leaf
1	2	Byte offset to the first free block
3	2	Number of cells on this page
5	2	First byte of the cell content area
7	1	Number of fragmented free bytes
8	4	Right child (the Ptr(n) value). Omitted on leaves.

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的地方。这个值为单元内容区域和未使用区域的分界线。

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

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

Structure of a cell
Size	Description
4	Page number of the left child. Omitted if leaf flag bit is set.
var(1–9)	Number of bytes of data. Omitted if the zerodata flag bit is set.
var(1–9)	Number of bytes of key. Or the key itself if intkey flag bit is set.
*	Payload
4	First page of the overflow chain. Omitted if no overflow.

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

2.3、溢出页面

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

溢出页面的格式：

2.4、实例分析

数据库为test.db，其中有一个表和索引如下：

CREATE TABLE episodes( id integer primary key,name text, cid int);CREATE INDEX name_idx on episodes(name);

2.4.1、叶子页面格式分析

episodes表的根页面为第2个页面(此时episodes表只占一个页面)，表中的数据如下：

sqlite> select * from episodes; 1|Cinnamon Babka|2 2|Mackinaw Peaches|1 3|Mackinaw Peaches|1 4|cat|1 5|cat|1 6|cat|1 7|cat|1 8|cat|1 9|cat|1 10|cat|1 11|cat|1 12|cat|1 13|cat2|40 14|hustcat|5 15|gloriazzz|41 16|eustcat|5 17|xloriazzz|41

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

Offset	Size	值 及含义
0	1	0x0D: 1: intkey, 2: zerodata, 4: leafdata, 8: leaf（1+4+8）
1	2	0x0000:第一个空闲块的偏移为0
3	2	0x0011:页面的单元数为17
5	2	0x031C:单元内容区的第一个字节的偏移(距页面起始位置)
7	1	0x00：碎片字节数
8	4	Right child (the Ptr(n) value). Omitted on leaves.

来看第2个页面的数据（0x400——0x7ff(255字节)）：

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

0x13：数据的字节数，19个字节，即04 00 2B … 61 32。

0x01：关键字的字节数，对于整型，则为关键字本身，即1。

0x04：从该字节开始为payload，即记录。0x04为记录头的大小，即04 00 2B 00为记录头。

0x00：NULL，id字段的值，由于关键字保存在key size中，这里为NULL。

0x2B：name字段值的长度，为字符串，长度为(43-13)/2=15。后面15字节43 69 ... 61 32为name字段值。

0x00：NULL，第一条记录cid的值。

2.4.2、索引页面格式

sqlite> select * from sqlite_master;table|episodes|episodes|2|CREATE TABLE episodes( id integer primary key,name tex

t, cid int)index|name_index|episodes|3|CREATE INDEX name_index on episodes(name)

第3个页面保存表episodes的索引(也只占一个页面)。

前8个字节为页面头：

0x0A：leaf+zerodata，表示叶子页面，且页面中只有关键字，没有数据（即索引页面）。

0x0000：表示第一个空闲块的偏移为0。

0x0011：页面的单元数(记录数)，该页面含有17个记。

0x030D：单元内容区的第一个字节的偏移(距页面起始位置)。

0x00： 碎片字节数。

接下来34个字节为17个单元（记录）的指针数组。第一个单元的偏移为0x03EC，如

来看看索引单元的格式：

0x13：数据的字节数，19个字节，从0x03开始。

0x03：记录头的字节数。即03 2B 01为记录头。

0x2B：第一个字段的长度，15个字节，该索引是对episodes表的name字段建的，其值为episodes表name字段的值。

0x01：第二个字段的长度，其值为0x01，即episodes表中的对应记录rowid的值。

2.4.3、索引与order by(索引与查询优化的关系)

Order by是查询中经常用到的，一些通用DBMS(比如DM，Mysql)都提供基于索引的形式来实现Order by。SQLite也是通过索引来实现Order by的。当字段有索引时，则直接通过索引很容易实现排序；另一方面，如果排序的字段没有索引，则以该字段为索引(这种情况下是聚集索引)建立一张临时表，再将临时表按顺序输出。来看看sqlite的实现吧。

在SQLite中，默认以rowid来建立聚集索引(对于没有整型值主键的情况)。如果主键字段为整型，则将其直接保存在rowid中，实现聚集索引；另一方面，如果主键是字符串，则对主键建立二级索引。非主键的索引都属于二级索引。

先来看看以整型ID为主键的情况：

 

//以ID(rowid)为索引(即聚集索引)
sqlite> explain select * from episodes order by id;
0|Trace|0|0|0|explain select * from episodes order by id;|00|
1|Noop|0|0|0||00|
2|Goto|0|13|0||00|
3|SetNumColumns|0|3|0||00|
4|OpenRead|0|2|0||00|        //打开表episodes,p2(=2)为其根页面
5|Rewind|0|11|0||00|         //游标指向第一条记录
6|Rowid|0|1|0||00|           //取出记录的rowid
7|Column|0|1|2||00|          //取出第1列的值
8|Column|0|2|3||00|          //取出第2列的值
9|ResultRow|1|3|0||00|       //生成记录结果
10|Next|0|6|0||01|           //取下一条记录
11|Close|0|0|0||00|
12|Halt|0|0|0||00|
13|Transaction|0|0|0||00|
14|VerifyCookie|0|2|0||00|
15|TableLock|0|2|0|episodes|00|
16|Goto|0|3|0||00|

属性有索引的情况：

//排序的实现——有索引
//算法思想:
//(1)从索引中依次读取记录(索引记录的形式如:原索引属性-rowid的键值),并取出rowid.
//(2)根据(1)中取出的rowid,在原表中查找记录,并生成记录结果.
sqlite> explain select * from episodes order by name;
0|Trace|0|0|0|explain select * from episodes order by name;|00|
1|Noop|0|0|0||00|
2|Goto|0|18|0||00|
3|SetNumColumns|0|3|0||00|
4|OpenRead|0|2|0||00|                  //打开表,p1为表游标(0),p2为表根页面
5|SetNumColumns|0|2|0||00|
6|OpenRead|2|3|0|keyinfo(1,BINARY)|00| //打开索引,p1为索引游标,p2为根页面
7|Rewind|2|15|1|0|00|
8|IdxRowid|2|1|0||00|                  //从索引记录中取出rowid
9|Seek|0|1|0||00|                      //根据rowid从表中查找记录
10|IdxRowid|2|2|0||00|
11|Column|2|0|3||00|
12|Column|0|2|4||00|
13|ResultRow|2|3|0||00|
14|Next|2|8|0||00|
15|Close|0|0|0||00|
16|Close|2|0|0||00|
17|Halt|0|0|0||00|
18|Transaction|0|0|0||00|
19|VerifyCookie|0|2|0||00|
20|TableLock|0|2|0|episodes|00|
21|Goto|0|3|0||00|

对于没有索引的属性排序：

//排序的实现——没有索引
//算法思路：
//(1)按查询属性为聚集索引建立一个临时表.
//(2)按索引顺序输出结果.
sqlite> explain select * from episodes order by cid;
0|Trace|0|0|0|explain select * from episodes order by cid;|00|
1|OpenEphemeral|1|3|0|keyinfo(1,BINARY)|00| //p1为临时表游标,p2为临时表列数
2|Goto|0|30|0||00|
3|SetNumColumns|0|3|0||00|
4|OpenRead|0|2|0||00|       //打开表episodes
5|Rewind|0|16|0||00|        //游标移到表的第1条记录,p1为游标下标
6|Rowid|0|1|0||00|          //p1为表的下标,p2指向表的记录
7|Column|0|1|2||00|         //读取表p1(=0)的第1列
8|Column|0|2|3||00|         //读取表p1(=0)的第2列
9|MakeRecord|1|3|4||00|
10|SCopy|3|5|0||00|
11|Sequence|1|6|0||00|
12|Move|4|7|1||00|
13|MakeRecord|5|3|8||00|
14|IdxInsert|1|8|0||00|     //该指令在索引中插入记录,相当于对表的Insert. p1为索引下标,即OpenEphemeral打开的临时表
15|Next|0|6|0||01|
16|Close|0|0|0||00|         //关闭表episodes
17|SetNumColumns|0|3|0||00|
18|OpenPseudo|2|1|0||00|    //打开临时表
19|Sort|1|28|0||00|         //与Rewind功能类似
20|Column|1|2|4||00|
21|Integer|1|8|0||00|
22|Insert|2|4|8||00|
23|Column|2|0|1||00|
24|Column|2|1|2||00|
25|Column|2|2|3||00|
26|ResultRow|1|3|0||00|     //输出临时记录
27|Next|1|20|0||00|
28|Close|2|0|0||00|        
29|Halt|0|0|0||00|
30|Transaction|0|0|0||00|
31|VerifyCookie|0|2|0||00|
32|TableLock|0|2|0|episodes|00|
33|Goto|0|3|0||00|