1. sqlITE存储分析
1.1sqlITE存储分析
1.1.1存储结构介绍
sqlite 有3 类数据库。除内存数据库外，sqlite 把每个数据库(main 或temp)都存储到一个单独的文件中。
sqlite 数据库文件由固定大小的“页(page)”组成。页的类型可以是：Btree 页、空闲(free)页或溢出(overflow)页。Btree 又可以是B-tree 或B+tree，每一种树的结点又区分为内部页和叶子页。一个数据库文件中可能没有空闲页或溢出页，但必然有Btree 页。其实sqlite 还有两种页。一种称为“锁页(lockingpage)”。只有1 页，位于数据库文件偏移为1G 开始的地方，如果文件不足1G，就没有此页。该页是用于文件加锁的区域，不能存储数据(参源代码io.h)。好在，如果只是读数据，即使文件大于1G，也不会有指针指向此页，因此下面我们就不再提它了。另一种称为“指针位图页(pointer-mappage)”，这类页用于在auto-vacuum的数据库中存储元数据。
一个sqlite 数据库文件由多个多重Btree 构成。每个Btree 存储一个表的数据或一个表的索引，索引采用B-tree，而表数据采用B+tree，每个Btree 占用至少一个完整的页，每个页是Btree 的一个结点。每个表或索引的第1 个页称为根页，所有表或索引的根页编号都存储在系统表sqlite_master 中，表sqlite_master 的根页为page 1。
///////////////////////////////////////////////////////////////////////////////////////////////////
B-tree结构，
///////////////////////////////////////////////////////////////////////////////////////////////////
** Each btree pages is divided intothree sections: The header,the
** cell pointer array,and the cellcontent area. Page 1 also has a 100-byte
** file header that occurs before thepage header.
**
**|----------------|
**| file header | 100 bytes.Page 1 only.
**|----------------|
**| page header | 8 bytes for leaves. 12 bytes for interior nodes
**|----------------|
**| cell pointer | | 2bytes per cell. Sorted order.
**| array | |Grows downward
**| | v
**|----------------|
**| unallocated |
**| space |
**|----------------| ^ Grows upwards
**| cell content | |Arbitrary order interspersed with freeblocks.
**| area | | andfree space fragments.
**|----------------|
Btree 页内部以 (cell)为单位来组织数据，一个cell包含一个(或
部分，当使用溢出页时)payload(也称为Btree 记录)。由于各类数据大小各不相同，cell
的大小也就是可变的，所以Btree 页内部的空间需要进行动态分配(程序内部动态分配，不是动态申请空间)，cell是Btree 页内部进行空间分配和回收的基本单位。
页内所有cell的内容集中在页的底部，称为“cell内容区”，由下向上增长。由于cell的大
小可变，因此需要对每个cell在页内的起始位置(称为cell指针数组)进行记录。cell指针保存在cell指针数组中，位于页头之后。cell指针数组包含0 个或多个指针，由上向下增长。
cell指针数组和cell内容区相向增长，中间部分为未分配空间。系统尽量保证未分配空间位
于最后的指针之后，这样，就很容易增加新的cell，而不需要整理碎片。
cell不需要是相邻和有序的，但cell指针是相邻和有序的。每个指针占2 个字节，表示该单
元在单元内容区中距页开始处的偏移。页中cell的数量保存在页头中。
文件头格式
页头格式
页头包含用来管理页的信息，它通常位于页的开始处。对于数据库文件的page 1，页头始于
第100 个字节处，因为前100 个字节是文件头(file header)。
页类型标志：
如果leaf 位被设置，则该页是一个叶子页，没有儿子；
如果zerodata 位被设置，则该页只有关键字，而没有数据；
如果intkey 位被设置，则关键字是整型；
如果leafdata 位设置，则tree 只存储数据在叶子页。
第1 个空闲块的偏移量：
由于随机地插入和删除单元，将会导致一个页上单元和空闲区域互相交错。cell内容区域中
没有使用的空间收集起来形成一个空闲块链表，这些空闲块按照它们地址的升序排列。页头
偏移为1 的2 个字节指向空闲块链表的头。每个空闲块至少4 个字节，因为一个空闲块的开
始4 个字节存储控制信息：前2 个字节指向下一个空闲块(0 意味着没有下一个空闲块了)，
后2 个字节为该空闲块的大小。
cell内容区的起始地址：
cell内容区的起始地址记录在页头偏移为5 的地方。这个值为cell内容区域和未使用区域的
分界线。
cell内容区碎片字节总数， offset 7。
由于空闲块大小至少为4 个字节，所以cell内容区中的3 个字节或更小的空闲空间(称为碎
片，fragment)不能存在于空闲块列表中。所有碎片的总的字节数将记录在页头偏移为7 的位置(碎片最多为255 个字节，在它达到最大值之前，页会被整理)。
最右儿子的页号：
如果本B-tree 页是叶子页，则无此域，页头长为8 个字节。如果本B-tree 页为内部页，则有
此域，页头长为12 个字节。页头偏移为8 的4 个字节包含指向最右儿子的指针，该指针的
含义将在第2 章介绍。
cell内容区空闲空间：被一个链表链接，每个数据块最少四个字节，链表块数据结构
Cell内容区：
cell是变长的字节串。一个单元包含一个(或部分，当使用溢出页时)payload。
大小 说明
4 left节点的页码，叶子节点无此字段。
var(1–9) Payload 大小，以字节为单位。
var(1–9) 数据库记录的Rowid 值。
* Payload 内容，存储数据库中某个表一条记录的数据。
4 溢出页链表中第1 个溢出页的页号。如果没有溢出页，无此域。
这里有个知识点很重要，如果不清楚，就分析不了对应的raw data，就是number是用可变长整数表示的，如何知道number占几个字节，如何知道它实际的大小，如果没有注意分析代码里的注释和实际的数据，是意识不到这一点的。可变长整数的解释如下，具体的实例后续会有分析。
溢出页：
(cell)具有可变的大小，而页的大小是固定的，这就有可能一个单元比一个
完整的页还大，这样的单元就会溢出到由溢出页组成的链表上，如下图所示：
溢出页号为0 时表示此页为溢出页链表的表尾页。
空闲页：
空闲页有两种类型：trunk page(主干页)和leaf page(叶子页)。
文件头偏移为32 处的指针指向空闲链表的第一个trunk page，每个trunk page 指向多个叶子页。
文件头偏移36 处的4 个字节为空闲页的总数量，包括所有的trunk page 和leaf page。
空闲页链表的结构如下图所示：
其中，trunk page 的格式(从页的起始处开始)如下：
(1)4 个字节，指向下一个trunk page 的页号，0 表示链表结束；
(2)4 个字节，该页leaf page 的数量；
(3)0 个或多个指向leafpage 的页号，每项4 个字节。
sqlite 对leafpage 的格式没有规定。
指针图页：
只有auto-vacuum 数据库才有指针图页(Pointer map page)。如果数据库文件头偏移为52 字节的地方为一非零值，该数据库为auto-vacuum数据库。
数据库中所有的指针图页共同构成一个查找表，利用该表可以确定数据库中各页的类型及其
父亲页的页号。查找表将页按下表分类：
指针图页本身不出现在指针图查找表中。Page 1 也不出现在指针图查找表中。指针图入口格
式如下图所示：
每个指针图查找表入口使用5 个字节。第1 个字节为页类型，后4 个字节为父亲页号(高位
字节在前)。每个指针图页可以包含
num-entries := usable-size / 5
个入口，其中“可用大小”为页大小减页尾部保留空间的大小（参1.2 节）。
如果数据库是auto-vacuum 的，page 2 永远是指针图页。它保存了从第3 页到第(2 +
num-entries)页的指针图查找表入口。其中page 2 的头5 个字节保存的是第3 页的指针图查
找表入口，5~9 字节保存的是第4 页的指针图查找表入口，依此类推。
数据库中下一个指针图页的页号是(3 +num-entries)，它保存了从第(4 + num-entries)页到第
(3+2*num-entries)页的指针图查找表入口。一般而言，对于任何大于0 的n，页号为(2 + n*
num-entries)的页为指针图页。非auto-vacuum数据库没有指针图页。
1.1.1实践分析
在http://www.sqlite.org/download.html下载sqlite-tools-win32-x86-3170000.zip工具包，调出DOS控制台，
创建数据库：
C:\zdoc\doc_shah\sqlite\sqlite-tools-win32-x86-3170000>sqlite3student.db
sqlite version 3.17.02017-02-13 16:02:40
Enter ".help" forusage hints.
创建表：
CREATE TABLE basic(
id intefer primady key,
name text,
sex text,
age integer,
class text,
number integer,
phone text,
address text);
插入数据：
INSERTINTO "basic" VALUES(1,'Bagels','M',18,'3-3',980303006,'13246789876','guangdong shenzhen');
INSERTINTO "basic" VALUES(1,'Peter',980303008,'13940709836','shandong jinan');
INSERTINTO "basic" VALUES(1,'Robot',16,980303004,'13646709872','guangdong heyuan');
INSERTINTO "basic" VALUES(1,'Alice','F',17,980303026,'13246357876','hunan changsha');
可以看到生成了一个8K的.db文件，根据后面的分析我们知道，这个db文件有两个page，每个page为4K。
///////////////////////////////////////////////////////////////////////////////////////////////////
可以用sqlitespy打开.db文件，看到我们建立的数据库和表。
还可以用其他编辑工具打开.db文件，以二进制的方式查看文件。
1.1表数据页
表数据用B+tree 来存储。
1.1.1Page1
File header文件头从db文件0位置开始，100 个字节
前16 个字节为头字符串，程序中固定设为"sqlite format 3"。
0X1000：页大小，0X1000=4096 字节。
0X01：文件格式版本(写)，值为1。
0X01：文件格式版本(读)，值为1。
0X40：Btree 内部页中一个cell最多能够使用的空间。0X40=64，即25%。
0X20：Btree 内部页中一个cell使用空间的最小值。0X20=32，即12.5%。
0X20：Btree 叶子页中一个cell使用空间的最小值。0X20=32，即12.5%。
0X00000005：文件修改计数，现在已经修改了5 次，分别是1 次创建表和4次插入记录。
从0X20 开始的4 个字节：空闲页链表首指针。当前值为0，表示该链表为空。
从0X24 开始的4 个字节：文件内空闲页的数量。当前值为0。
从0X28 开始的4 个字节：Schema version。当前值为0X00000001。以后，每次sqlite_master
表被修改时，此值+1。
从0X38 开始的4 个字节：采用的字符编码。此处为0X00000001，表示采用的是UTF-8 编
码。
注意：在sqlite 文件中，所有的整数都采用大端格式，即高位字节在前。
Page header页头从0X64=100 处开始，8个字节(叶子页8字节，内部页12字节)。
说明：
0X0D：说明该页为B+tree 的叶子结点。可以看出，如果是B+tree
的叶子页，该字节值为0X0D，如果是B+tree 的内部页，该字节值为0X05，如果是B-tree
的叶子页，该字节值为0X0A，如果是B-tree 的内部页，该字节值为0X02。
0X0000：第1 个空闲块的偏移量。值为0，说明当前空闲块链表为空。
0X0001：本页的cell数。当前系统表中只有一条记录，所以本页当前只有1 个cell。
0X0F63：cell内容区的起始地址。
0X00：碎片的字节数。当前值为0。
Cell内容区分析，根据page header的offset，找到cell内容区的地址为0X0F63。
这是个叶子节点，所以没有left child的page number，datanumber是可变长整形，为0x81 1a，实际数值为0x009a，就是154，0X0F62+0x009a=0x0ffc，加上这两个var字段，一个为2，一个为1，地址就是0x0fff，刚好到达页尾。
0X01：（table 对象)在sqlite_master 表中对应记录的rowid，值为0X01。
每个payload 由两部分组成。第1 部分是记录头，由N+1 个可变长整数组成，N 为记录中的
字段数。第1 个可变长整数(header-size)的值为记录头的字节数。跟着的N 个可变长整数与
记录的各字段一一对应，表示各字段的数据类型和宽度。用可变长整数表示各字段类型和宽
度的规定如下表所示：
header-size 的值包括header-size 本身的字节和Type1~TypeN 的字节。
Data1~Datan为各字段数据，与Type1~TypeN一一对应，类型和宽度由Type1~TypeN指定。
本例的payload 数据为：
0X07：记录头包括7 个字节。
0X17：字段1。TEXT，长度为：(23-13)/2=5。值为：table。
0X17：字段2。TEXT，长度为：(23-13)/2=5。值为：basic。
0X17：字段3。TEXT，长度为：(23-13)/2=5。值为：basic。
0X01：字段4。整数，长度为1。值为：0X02。表示本表B+tree 的根页编号为2。
0X8213：字段5。TEXT。0X8213 为可变长整数，转换为定长为0X113=275。可知字段长度
为：(275-13)/2=131=0X83。就是create语句的部分。
1.1.1Page2
这里首先就是page header，只有一个结点，既是根页，也是叶子页。
说明：
0X0D：说明该页为B+tree 的叶子结点。可以看出，如果是B+tree
的叶子页，该字节值为0X0D，如果是B+tree 的内部页，该字节值为0X05，如果是B-tree
的叶子页，该字节值为0X0A，如果是B-tree 的内部页，该字节值为0X02。
0X0000：第1 个空闲块的偏移量。值为0，说明当前空闲块链表为空。
0X0004：本页的cell数。当前表中有4条记录，所以本页当前有4 个cell。
0X0F31：cell内容区的起始地址。
0X00：碎片的字节数。当前值为0。
Cell指针数组：存在4个cell的指针，因为是反向生长，所以第一个cell的地址偏移最大，按顺序排列。注意虽然在pageheader部分，cell内容区的起始地址是0X0F31，但本表的第1 条记录地址是0X0FC9.
Payload的分析也如同page1.
1.1索引B-tree
1.1.1Index Page
索引页数据结构为B-tree，有内部页和叶子页。B-tree 中只存储关键字段的值和对应记录的rowid 值。
可以使用如下语句生成一个索引页，
CREATE INDEX basic_number_idx onbasic(number COLLATE NOCASE);
之后db文件大小增加4k，为一个页面（页面数依赖记录的数目）。
说明：
0X0a：说明该页为B-tree 的叶子页，内部页0X02。
0X0000：第1 个自由块的偏移量。0，说明当前自由块链表为空。
0X0004：本页有4 个cell。
0X0fdd：cell内容区的起始位置。
0X00：碎片的字节数，当前为0。
叶子页无子节点，故字段无。
cell指针数组在页头之后，有4 个指针。
cell内容区的数据如下：
最后的一个cell，即0X0fdd对应的数据解释如下：
0X08：Payload 数据的字节数。
0X03：记录头包括3 个字节，含自己。
0X04：字段1。TEXT，长度为：4。字段值为：0X3A6E3CB2,即number列的值98030326。
0X01：字段2。整数，长度为1。字段值为：0X04，表示索引值所对应记录的关键值(即记录的rowid 值)为4。
其他的解释类似，需要注意几点，1是索引表的cell记录是按顺序排列的；2是第一行的rowid在数据里面是忽略的，所以只要7个字节；3是习惯这种payload格式的表示方法，通过pageheader和cell pointer array找到每个cell的起始地址，然后每段字节数据的解析和对对应关系。
