SQLite源码分析5 文件格式相关

原文见 https://sqlite.org/fileformat2.html 描述了sqlite的各种数据结构、b树相关的存储等。 挑了重点做了翻译。需要先学会b树，最好了解分页、存储管理相关的概念。

---

数据库文件

• 通常sqlite的一个数据库存在一个文件中，称为”main database file”。

• 在一个事务过程中，会在另一个文件中存备份信息，称为”rollback journal”回滚日志。 如果在一个事务执行中发生灾害，回滚日志可以用来把数据恢复到事务开始前的状态。这样保证数据始终处在一个稳定的状态，不会被破坏。

Pages(分页)

• 数据库文件由一个或多个页组成。页大小范围是512-65536字节。 同个文件中的页的大小一致。

• 页编号从1开始。最大为4294967294(2^32 - 2)。 最小的数据库文件只包含一个512字节的页。 最大的文件可包含2147483646个页，每页65536字节，一共281474976579584字节(256T)。 一般情况下磁盘会先满。不太需要考虑这个文件大小限制。

• 实际应用中sqlite数据库一般大小为kb到几个G。虽然TB级别的应用也是存在的。

• 在某一时刻，一个页可作下列用途之一：

    lock-byte
    freelist
        freelist trunk
        freelist leaf
    b-tree
        表b树内部节点页
        表b树叶子节点页
        索引b树内部节点页
        索引b树叶子节点页
    payload overflow
    pointer map

• 所有对于主数据库文件的读写都以页为界，所有写的字节长度都是页的整数倍。 读也一样，除了一个特例。当数据库被打开时，读前100字节(数据库文件头)。

• 在存有有用信息的页被修改之前，页修改之前的数据会被写到回滚日志。 freelist的叶子页，由于不包含可用于回滚的信息，所以不需要写到回滚日志，以减少磁盘io。

---

数据库头信息

数据库文件前100字节包含各种元信息。

关注一部分：

offset	size	描述
0	16	写死的ascii字符串SQLite format 3
16	2	页的大小。我的文件是0x1000即4k字节。
20	1	每个页尾部的备用字节。可作一些扩展应用。比如存加密信息。
24	4	文件修改计数。文件每次被修改后释放锁时+1。如果有多个进程同时在读文件，可以用这个计数来检测文件是否更改。
32	4	第一个空闲页的编号
36	4	所有空闲页数量。
44	4	schema格式
48	4	默认页缓存大小。
56	4	字符串编码。1-utf8，2-utf16le，3-utf16be。
72	20	20字节备用空间。目前必须为0。

---

lock-byte页

• 数据库文件中的某一页，给操作系统做特殊用途。为了兼容老旧的操作系统。

freelist

• 数据库文件可能包含空闲的页。当删除某些信息时就可能出现空闲的页。 freelist存空闲的页的链表。

b树页

• b树提供基于页的有序key的kv存储。具体算法可见之前的blog。

• sqlite使用两种b树实体： 表-b树。使用64bit有符号整数作为key，所有数据存在叶子节点。 索引-b树。使用任意类型的key，不存任何数据。

• 一个b树页只可能是“内部”页和“叶子”页。 叶子页包含key，如果是表b树，每个key还包含数据。 内部页包含k个key和k+1个指针，指向下一层的子页。 k大于等于2，一般情况远大于2，可能多达上千。

• sqlite的表分为有rowid和无rowid。默认是有rowid表。我们只看有rowid的。

• 数据库每个表有一棵表b树。 每个索引都有一棵索引b树。 虚表没有b树。

• 表b树的每个数据包含一个64位有符号整数和最大2147483647(2048M)字节的任意数据。 内部节点只包含key，不包含数据。数据都存在叶子节点。

• 索引b树的每个数据包含最大2147483647字节的key，不包含数据。

• 每个key和它左边的指针一起称为一个cell。

• 一个b树页的数据布局：

  1. 100字节头数据(只对于第一页)

  2. 8或12字节页头。

  3. cell队列

  4. 未分配的空间

  5. cell内容

  6. 备用空间

• 页头格式：

offset	size	描述
0	1	b树页的类型。0x2 索引b树内部节点页。0x5 表b树内部节点页。0xa 索引b树叶子页。0xd 表b树叶子页
1	2	页中的第一个空闲block号。0表示没有空闲的block。
3	2	cell的数量
5	2	cell内容的起始位置
7	1	cell内容中的空闲字节数
8	4	节点最右端的指针。因为每个cell包含的是左边的指针，最右边的指针一定会落单。

• cell队列紧排在页头后面，按key升序排序。

• 页中会存在断续的可用空间，sqlite会时不时做类似“除碎片”的操作，把可用空间做成连续。来节省空间和提高效率。

---

变长整数(variable-length integer)(varint)

https://sqlite.org/src4/doc/trunk/www/varint.wiki

• 用1到9个字节来表示一个64bit有符号整数。 较小的值占用较少的字节数。 一个varint的长度存在第一个字节中。 字典顺序和数字顺序一致。如果按数字顺序排序了，那么在字符串层面也是有序的。

• b树中数据类型的总结:

数据类型	位置:表叶子节点	表内部节点	索引叶子节点	索引内部节点	描述
4字节int		✔		✔	左子节点的页号
varint	✔		✔	✔	payload的字节数
varint	✔	✔			rowid
字节array	✔		✔	✔	payload
4字节int	✔		✔	✔	第一个overflow页的页号

---

cell payload overflow

• 一个b树节点只分配1页空间，如果节点包含的数据超出限额，多出的数据就得存到overflow页。

• overflow页以链表的形式存，每页前4字节表示下一页的页号，其他是实际数据。

---

schema层

上述内容描述了b树底层的结构。下面讲sqlite如何用b树实现sql层面的操作，即增删查改等。

数据库记录的格式

• 表b树的叶子数据和索引b树的数据可以是任意格式数据。

• 所有数据都符合“记录格式”。记录格式描述列的数量，每个列的数据类型，列数据的格式。

• 一条记录包含头和体。头以一个varint开始，表示头的总字节数。 接着是一个或多个varint，称为serial type。每列对应一个，表示列的类型。

serial type	实际数据大小	描述
0	0	null
1	1	8位int
2	2	16位int
3	3	24位int
4	4	32位int
5	6	48位int
6	8	64位int
7	8	64位浮点数
8	0	整数0
9	0	整数1
10,11	不定长	内部备用
大于等于12的偶数N	(N-12)/2	blob类型
大于等于13的奇数N	(N-13)/2	string类型。结尾的null不存。

• 接着是每列的值。对于类型0，8，9，12，13，不需存值。

排序

• 排序优先级

  1. null值优先。serial type 0

  2. 数字(serial type 1-9)。在null之后，按数字排序。

  3. 字符串。按列的collating function排序。

  4. blob。按memcmp()排序。

• collating function定义如何比较两个字符。 sqlite定义3种内置的函数： BINARY 所有字节依次用memcmp()比较 NOCASE 与BINARY基本一致。如果有ascii字符，会把大写英文字母先转为小写，再用memcmp()比较。 RTRIM 右侧trim。与BINARY基本一致。字符串右边的空格不影响排序。两个字符串右侧空格数不一样，但是之前的字符都一样的话，算是相等。

  可以添加自定义的collating function。

sql表的表示

• 表一般用表b树来表示。

• 每个节点数据对应一行数据库记录。rowid作为64位的整数key存在每个节点数据里。

• 每条记录把所有列的数据按上述的记录格式拼接再存到b树节点。

sql索引的表示

• 每个索引都对应一棵索引b树。

• 里面的每个节点对应一条实际数据表里的记录。

• 索引b树的每个数据的组成是：索引包含的所有列加上对应的数据表记录的rowid。 对于一般表，key是rowid，对于无rowid的表，key是主键。

sql数据库schema的存储

sqlite_schema是sqlite内置的表。存各种结构定义信息。比如表、索引、trigger等等。

CREATE TABLE sqlite_schema(
  type text,
  name text,
  tbl_name text,
  rootpage integer,
  sql textxt
);

---

回滚日志

• 回滚日志和数据库文件存在同个目录。

• 一个数据库只能有一个回滚日志。所以一个数据库同时只能存在一个写事务。

• 当事务中途发生灾害时，数据库处于一个异常状态。 下次sqlite尝试打开时，回滚日志将会被检测到，并进行回滚操作，恢复到事务开始前的状态。

• 只有当一个回滚日志的header有效时才能进行回滚。 那么有三个情况可以使日志失效，也就是标志事务已经成功，即commit成功。

  1. 删除回滚日志

  2. truncate回滚日志到0。

  3. 把header写坏，比如写成全0。

• header的格式

offset	size	描述
0	8	写死0xd9, 0xd5, 0x05, 0xf9, 0x20, 0xa1, 0x63, 0xd7
8	4	下一块日志数据的页数。-1表示已经到了末尾。
12	4	校验和的随机数
16	4	数据库初始的页数
20	4	对应的磁盘sector扇区的字节数？
24	4	本日志的页数

• header需要按sector大小填充0。 header存在于一个扇区内，这样如果发生断电等，信息不会损坏。

• 接着是页数据。每个将要改变的数据页都会存下来。同个页最多存一次。 回滚的操作其实很简单，就是依次读日志里的页数据，写回数据库文件即可。

• 日志数据页的格式

offset	size	描述
0	4	页编号
4	N	事务开始前的数据
N+4	4	校验和