小文件分析 - （二）
页
主数据库文件头之后的都是页的内容了，页的分类主要有5种：b-tree 页，overflow 页，free 页，lock-byte页以及pointer map page。
主要使用到的是前三者，lock-byte页只要是为了支持某些文件系统使用的是强制性加文件锁，而pointer map page是为了支持 auto_vacuum和incremental_vacuum模式，这两个以后再说。
页的格式
空闲页 free page
空闲页分为chunk 和 leaf，前者存放着多个leaf空闲页（里面没有任何数据），并且chunk会串起来成为一个freelist，官网是这么说的：The freelist is organized as a linked list of freelist trunk pages with each trunk page containing page numbers for zero or more freelist leaf pages.
| Offset | Size | Description |
|---|---|---|
| 0 | 4 | 下一个freelist chunk page的页号 |
| 4 | 4 | L=当前chunk存放的freelist leaf page的数目 |
| 8 | L*4 |
freelist leaf page页号组成的数组，长度等于L |
b-tree页 B-tree page
关于b树和b+树的，参考博客：B树与B+树
b-tree页格式
- The 100-byte database file header (found on page 1 only)
- The 8 or 12 byte b-tree page header
- The cell pointer array
- Unallocated space
- The cell content area
- The reserved region.
主数据库文件头只在页1有，保留区间默认也是没有的，所以剩下的就是
| 页头 |
|---|
cell指针数组 |
| 未使用区间 |
cell内容区 |
先不着急看页头和cell的具体定义，回到我们那个小文件分析中，还是利用刚才的showdb工具依次输入./showdb small.db NbdCCC，N为页号（例子中N=1~3）：
PS G:\code-2\sqlite3> ./showdb small.db 1bdCCC
Pagesize: 4096
Available pages: 1..2
Header on btree page 1:
000: 0d 13 table leaf
001: 00 00 0 Offset to first freeblock
003: 00 01 1 Number of cells on this page
005: 0f a3 4003 Offset to cell content area
007: 00 0 Fragmented byte count
Cell[0]:
f3f: 5b payload-size: 91
f40: 01 rowid: 1
f41: 07 record-header-size: 7
f42: 17 typecode[0]: 23 - text(5)
f43: 21 typecode[1]: 33 - text(10)
f44: 21 typecode[2]: 33 - text(10)
f45: 01 typecode[3]: 1 - int8
f46: 81 01 typecode[4]: 129 - text(58)
f48: 74 61 62 6c 65 data[0]: 'table'
f4d: 64 65 70 61 72 74 6d 65 6e data[1]: 'department'
f57: 64 65 70 61 72 74 6d 65 6e data[2]: 'department'
f61: 02 data[3]: 2
f62: 43 52 45 41 54 45 20 54 41 data[4]: 'CREATE TABLE department...'
这里涉及提前涉及到了sqlite_schema的概念，它存放着其他所有表、索引、触发器对应的根b-tree页号，而这由一张虚拟的表组成，并且sqlite3默认该表的根b-tree页号为1。sqlite_schema的定义如下
CREATE TABLE sqlite_schema(
type text,
name text,
tbl_name text,
rootpage integer,
sql text
);
暂时了解到这里即可，回头看页1，可以看到Cell[0]存放着的正是department这张表的信息，从里面我预先（可以先讲格式，但这样就很无聊了）知道了rootpage = 2（cell[0]里面的data[3]==2）。
故而接着解析页2，这时候我们就可以看到我们之前插入的两条数据：
PS G:\code-2\sqlite3> ./showdb small.db 2bdCCC
Pagesize: 4096
Available pages: 1..2
Header on btree page 2:
000: 0d 13 table leaf
001: 00 00 0 Offset to first freeblock
003: 00 02 2 Number of cells on this page
005: 0f ea 4074 Offset to cell content area
007: 00 0 Fragmented byte count
Cell[0]:
ff5: 09 payload-size: 9
ff6: 01 rowid: 1
ff7: 04 record-header-size: 4
ff8: 09 typecode[0]: 9 - one
ff9: 15 typecode[1]: 21 - text(4)
ffa: 01 typecode[2]: 1 - int8
ffb: 74 65 73 74 data[1]: 'test'
fff: ff data[2]: -1
Cell[1]:
fea: 09 payload-size: 9
feb: 02 rowid: 2
fec: 04 record-header-size: 4
fed: 01 typecode[0]: 1 - int8
fee: 15 typecode[1]: 21 - text(4)
fef: 09 typecode[2]: 9 - one
ff0: 02 data[0]: 2
ff1: 74 65 73 74 data[1]: 'test'
之前插入的两条数据
sqlite> insert into department values(1, "test", -1);
sqlite> insert into department values(2, "test", 1);
结合上述数据再来分析页头以及别的数据格式的内容。
b-tree 页头内容
- 偏移0x0 存放着的是b-tree页的类型，总共有4种
- 0x02 是 内部索引 b-tree页，interior index b-tree page
- 0x05 是 内部表 b-tree页，interior table b-tree page
- 0x0a 是 叶节点索引 b-tree页，leaf index b-tree page
- 0x0d 是 叶节点表 b-tree页，leaf table b-tree page
- 偏移0x1和0x7，是与cell被删除的时候留下的磁盘碎片问题，大于等于4字节的磁盘碎片被称为freeblock，串成一条链表，由page header存储首个freeblock；小于4字节的被称为fragment，并且会被累加到Fragmented byte count里面。
- 偏移0x03和0x05与cell有关，前者存储cell的个数，后者存放cell内容的起始偏移
- 还有0x08处，如果是 interior table b-tree page的话，还会存放一个右子树的页号。
- 剩下的就是cell指针数组了。
那么问题来了，cell究竟是啥？cell我的理解就是上述四种节点的类型的具体存放内容。来自官网的介绍
| Datatype | Table Leaf (0x0d) | Table Interior (0x05) | Index Leaf (0x0a) | Index Interior (0x02) | Description |
|---|---|---|---|---|---|
| 4-byte integer | ✔ | ✔ | Page number of left child | ||
| varint | ✔ | ✔ | ✔ | Number of bytes of payload | |
| varint | ✔ | ✔ | Rowid | ||
| byte array | ✔ | ✔ | ✔ | Payload | |
| 4-byte integer | ✔ | ✔ | ✔ | Page number of first overflow page |
这里剩下的问题就是playload里面存放着什么了。不管是table还是index都是 "record format"，也就是记录列的个数，列的类型，以及每一列的内容。
对于Table Leaf来说，里面存放的就是一行数据，其格式如下：
| record-header-size |
|---|
| record-header |
| data array |
- record-header-size：表明该记录头部+列的类型的大小。用的是可变长整型
- record-header: 记录每一列的类型
serial type，也是一个可变长整型。与此同时它也承担着该列内容的长度。 - data：则是每一列的内容，整数由
serial type定义长度，而字符串和二进制数据长度由serial type给出，其余的值直接由serial type给出：
以下是serial type的定义：
| Serial Type | Content Size | Meaning |
|---|---|---|
| 0 | 0 | Value is a NULL. |
| 1 | 1 | Value is an 8-bit twos-complement integer. |
| 2 | 2 | Value is a big-endian 16-bit twos-complement integer. |
| 3 | 3 | Value is a big-endian 24-bit twos-complement integer. |
| 4 | 4 | Value is a big-endian 32-bit twos-complement integer. |
| 5 | 6 | Value is a big-endian 48-bit twos-complement integer. |
| 6 | 8 | Value is a big-endian 64-bit twos-complement integer. |
| 7 | 8 | Value is a big-endian IEEE 754-2008 64-bit floating point number. |
| 8 | 0 | Value is the integer 0. (Only available for schema format 4 and higher.) |
| 9 | 0 | Value is the integer 1. (Only available for schema format 4 and higher.) |
| 10,11 | variable | Reserved for internal use. These serial type codes will never appear in a well-formed database file, but they might be used in transient and temporary database files that SQLite sometimes generates for its own use. The meanings of these codes can shift from one release of SQLite to the next. |
| N≥12 and even | (N-12)/2 | Value is a BLOB that is (N-12)/2 bytes in length. |
| N≥13 and odd | (N-13)/2 | Value |
举个例子：
Cell[0]:
ff5: 09 payload-size: 9
ff6: 01 rowid: 1
ff7: 04 record-header-size: 4
ff8: 09 typecode[0]: 9 - one
ff9: 15 typecode[1]: 21 - text(4)
ffa: 01 typecode[2]: 1 - int8
ffb: 74 65 73 74 data[1]: 'test'
fff: ff data[2]: -1
该cell对应着：insert into department values(1, "test", -1);
数据依次是：整数1，字符串"test"，整数-1
整型，字符串，整型，这信息对应着0xff8，0xff9，0xffa，
其中字符串的长度 = （21 - 13）/2 = 4。那如果是奇数长度的字符串呢？
因为schema format是4，故1可以直接用 09来表示。
……
剩下的就不说了。
不过有一点值得注意的是，这插入其实是逆序执行的，回忆一下page的分布，cell content是从下往上伸展，而cell pointer array是从上往下伸展。故越新的数据，在越上面。这是为了减少页的磁盘碎片化而使用的机制。
至此最简单的一个数据库文件已经分析完。但是还留下以下问题：
- 1、overflow page 是怎么一回事？用在什么场景？
- 2、index 和 table 的
interior类型还没有讨论？ - 3、vacuum 是什么一回事？
- 4、wal-mode 和 hot-journal mode 具体的意义？
