SQLite指南(0) 表和索引的文件存储结构

LXY3800

SQLite采用的是B+树来存储表中的索引和数据。
B树的键及其值既存储在内部节点上，也存储在叶节点上，所有的叶节点具有相同的深度。
B+树作了些微改变，键和数据会存储到叶节点上，并且按照键值排好序。而内部节点只存储键值。相当于有两条查找路径。

SQLite从根叶开始创建B+树，一般从页1开始。它以独立的页来存储树节点，每页一个节点，这些页要分内部页还是叶子页。对于每个节点，任何项(数据)及其键值组合成一个payload, 每页都会预设一个payload值，当实际的payload超过此值时，超出的字节就会填充到溢出页，多余的payload会依次存储到溢出页形成的链表里。内部页和叶子页都可以有溢出页。

SQLite的页结构：
SQLite数据库文件是由固定大小的页组成的。 也就是说该文件大小肯定是页大小的整数倍。其中的B+树模块管理着所有的页。每一个页，要么是普通页(内部页或者叶子页)，要么是溢出页，要么是自由页。

1. 页结构：
主要有4部分， 页头(内部页12字节，叶子页只要8字节), 单元指针数组，单元内容区，未分配空间区
页头构成：
起始地址：
0 (1字节), Flags. 1: intkey, 2: zerodata, 4: leafdata, 8: leaf
1 (2字节), 第一个自由块的起始位移
3 (2字节), 该页的单元数
5 (2字节), 单元内容区的第一个字节的位移
7 (1字节), 自由区的字节数
8 (4字节), 右孩子节点的地址(Ptr(n)), 对叶子节点，该值被忽略

对于第一个字节来说，是一个标志值，如果leaf为true, 表明它是叶子节点。如果zerodata为true,  表明该页只存储key值，不存储数据，如果intkey为true, 表明这里的key是一个整数，会存储到单元的头，而不是放到payload区。

Cell(单元)会存到页里最末尾的高地址区域里，它们会向页的开始方向增长。单元指针数组从页头末尾的第一个字节开始。每个指针是一个2字节的偏移地址(从页头开始)。 这些指针都是按照键值排好序的。

经过随机的insert, delete操作之后，页中的单元和空闲空间会变得分散。在单元内容区里的可用空间会被收集成自由块链表，以地址升序排列。该链表的头指针会从页头， 偏移值为1开始，每个自由块最少4字节大小。头4个字节存储着控制信息。头2个字节指向下一个自由块的偏移(值为0，意味着没有下一个自由块)，后两个字节表示本自由块的空间大小。一个页中所有碎片(可用字节)大小，会记录在页头的第7字节处。最大255。任何连续只有3个或更少字节的空间将被忽略。当碎片达到最大值之前，碎片会被合并。
单元内容区的第1个字节会在页头的第5个节处进行记录。该值充当内容区域和未分配空间的边界。

单元：
4字节,  左孩子的页号, 如果leaf flag设置为true,则忽略。
var (1-9), 数据字节数，如果zerodata为true,则忽略。
var (1-9), 键字节数，或者是键本身(如intkey为true)
* payload
4 ,   溢出链的第1页，没有溢出则忽略。

(To be cont...)