Ctrl+K

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

校验和
On this page