sqlite初探(一)——文件格式

2018年11月29日 1 作者 筱枫

近期拜读了sqlite的源码,不禁对开发这款数据库的大神心生敬佩,更别提他还开发了lemon词法分析生成器,每一次阅读源码,都会有新的收获。

本文仅对最底层的文件格式进行探讨,因笔者才疏学浅,如有错误之处烦请指出。

最早自己写了个玩具般的数据库,当时对于如何将数据存入文件,采用的是很low的线性存储方法,一旦涉及到删改,便会非常麻烦,所以来研究sqlite,给了我不少的收获

阅读本文需要以下知识:
b树、位运算、基础c语言、内存管理、十六进制运算、varint

本文写于2018年11月底,所用的sqlite源码版本为3.25.3

一、文件头

探寻一个文件格式,最好的方法就是对照着一个存在的文件进行探寻
首先我们使用sqlite创建一个数据库,并且向其中写入一些数据

sqlite3 test.sqlite

随后依次输入以下sql语句

create table hello(num int);

insert into hello values(10);

最后使用.exit退出,可以看到,当前目录下成功创建了一个test.sqlite文件

接着,我们使用十六进制查看器打开这个文件,这里笔者使用的是vscode的hexdump插件

下面请参阅 sqlite文件格式 来研究

sqlite使用b树管理数据,但b树最后会序列化存储在文件中
sqlite以page(页)的形式来管理数据结构,通常每一页是4k,这么设定的原因主要是因为磁盘是以块读取,对于磁盘来说,读取一个1字节,跟4k(4096字节)的数据,实际上几乎花费一样的时间
读者可以查看一下test.sqlite文件的大小,正常情况下应该是8k,这说明它有两个页面,第一个页面是头页面,存放了一些内部表,第二个页面则是create table后所分配的页面

sqlite文件的头100个字节(也就是第一个页的100个字节),用于标识整个文件的数据,也就是俗称的文件头
这100个字节的含义如下

Database Header Format

OffsetSizeDescription
016The header string: “SQLite format 3\000”
162The database page size in bytes. Must be a power of two between 512 and 32768 inclusive, or the value 1 representing a page size of 65536.
181File format write version. 1 for legacy; 2 for WAL.
191File format read version. 1 for legacy; 2 for WAL.
201Bytes of unused “reserved” space at the end of each page. Usually 0.
211Maximum embedded payload fraction. Must be 64.
221Minimum embedded payload fraction. Must be 32.
231Leaf payload fraction. Must be 32.
244File change counter.
284Size of the database file in pages. The “in-header database size”.
324Page number of the first freelist trunk page.
364Total number of freelist pages.
404The schema cookie.
444The schema format number. Supported schema formats are 1, 2, 3, and 4.
484Default page cache size.
524The page number of the largest root b-tree page when in auto-vacuum or incremental-vacuum modes, or zero otherwise.
564The database text encoding. A value of 1 means UTF-8. A value of 2 means UTF-16le. A value of 3 means UTF-16be.
604The “user version” as read and set by the user_version pragma.
644True (non-zero) for incremental-vacuum mode. False (zero) otherwise.
684The “Application ID” set by PRAGMA application_id.
7220Reserved for expansion. Must be zero.
924The version-valid-for number.
964SQLITE_VERSION_NUMBER

接下来我们对着上面的数据库文件截图,开始分析(其实这一步很简单,如果有分析过其他文件格式,例如png,jpg等,几乎是一模一样)

开头16个字节的魔数,用于标志这是一个sqlite文件

注意,因为这里是十六进制展示,所以很多计算规则与十进制不同,上面截图的每一行都是十六,所以sqlite开头的文字刚好占用一整行

第16、17个字节表明一个数,每个page的大小,这里是十六进制的1000,也就是十进制的4096,正好是4K

注意,sqlite中一般都是采用big-endian存储数字,所以数字要从左向右直接阅读即可(如果是Little,则要反向,0x1000 就会表示为 0x00 0x10)

这里建议使用windows自带的计算器,切换到程序员,然后便可以十分方便的进行十六进制换算

第18、19个字节分别表明采用哪种方式读取文件,1为传统,2为WAL

其他几个字节无关重要,可以了解一下

请查看偏移量为24的4个字节,表明文件修改计数,最大值为2^32,这里目前是4,它会随着每次操作而递增

注意,一个字节为8位,所以4个字节为32位

接下来的4个字节表明页面总数量,这里是2,表明两个页面,每个页面4k,所以总文件大小为8k

之后的几个字节这里不做讨论,需要了解详细的读者可以点击上方的 sqlite文件格式 链接进行阅读官方说明

二、页头

读取完文件后,便开始读取页头

注意,sqlite的第一个页的前100个字节是用作文件头,所以第一个页的实际可用空间是4096-100=3996字节

B-tree Page Header Format

OffsetSizeDescription
01The one-byte flag at offset 0 indicating the b-tree page type.
  • A value of 2 (0x02) means the page is an interior index b-tree page.
  • A value of 5 (0x05) means the page is an interior table b-tree page.
  • A value of 10 (0x0a) means the page is a leaf index b-tree page.
  • A value of 13 (0x0d) means the page is a leaf table b-tree page.

Any other value for the b-tree page type is an error.

12The two-byte integer at offset 1 gives the start of the first freeblock on the page, or is zero if there are no freeblocks.
32The two-byte integer at offset 3 gives the number of cells on the page.
52The two-byte integer at offset 5 designates the start of the cell content area. A zero value for this integer is interpreted as 65536.
71The one-byte integer at offset 7 gives the number of fragmented free bytes within the cell content area.
84The four-byte page number at offset 8 is the right-most pointer. This value appears in the header of interior b-tree pages only and is omitted from all other pages.

这是页头的格式说明

页头所占空间有8个字节或者12个字节(内部页表)

首先看第一个字节用于确认页面类型

这里是0x0D,请将目光定位到这里,16进制的64是等于10进制的100,所以页头从这里开始

之后的一个双字节说明空闲块开始,如果没有空闲块则为零

(注意,这里的空闲块指的是由于更新或者删除所留出来的空闲空间,是以一个链表的形式存储,这里的双字节指向的是第一个空闲块的地址)

再然后的一个双字节 0x0001 表明一共有多少个单元格数量

(注:sqlite采用单元格的方式存储实际数据,包括实际记录值)

然后的一个字节用于标明单元内容区域内的分段空闲字节数(这个具体是什么暂时不懂)

之后的0x0FCD(因为截图错误的问题, 图中是0xFCB) 表明空闲单元格的起始位置

(注意:sqlite的数据采用倒序增长,从页底部,也就是4096处开始增长,大致格式类似于下图)

页头的结尾处会记录页尾当中每个单元格所占大小,而这个记录也是会随着数据增长,所以采用这种方式,可以说是充分利用了空间,降低复杂度

(为何是结束指针?因为数据是倒序排列的,所以对于单元格来说是结尾指针,但对于读取内存的时候来说,却是开始指针)

下面我们跳到地址0xFCD看看数据

可以很明显的看到,0xFCD正是单元格的结束位置,然后我们读取的时候,是0xFCD为起点,读取剩下的单元格数据

接下来请把目光转向第二页,地址0x1000处

可以明显看到,这是一个新的页面,开头0x0D表明类型,注意看最后,0xFFB,按照我们刚刚的分析,这个应该是第一个单元格的位置

请跳转过去,注意,现在新的页头地址是0x1000,所以这里实际上指向的是偏移量,具体地址是 0x1000+0xFFB=0x1FFB

(其实简单的拉到结尾即可)

可以看到0xFFB这里存在着我们的数据,但是我们存入的不是10么?怎么会有五个字节?

且听我慢慢道来

这里的格式是这样

(注意,这里开始,所有用到的数字全是varint编码后的,详情可了解SQLite文件格式初步分析之varint

varint跟utf8之类的编码格式思想基本一样,都是一种压缩算法,简单的转换可以采用如下代码

#include <stdio.h>
#include <malloc.h>

int main(void)
{
    char c[2];
    
    c[0] = 0x83;
    c[1] = 0x62;
    
    char *p = &c;
    
    int a,b,s;
    
    int v = 0;
 
    a = *p;
    /* a: p0 (unmasked) */
    //varint为一个字节时
    if (!(a&0x80)) //如果a<=127=0x7F=1111111b
    {
        //值在0到127之间
        v = a; //直接取值 之后返回
    }

    p++;
    b = *p;
    /* b: p1 (unmasked) */
    //varint为两个字节时
    if (!(b&0x80))//判断第二个字节是否为A。如果是,则此varint占用两个字节 格式为BA
    {
        a &= 0x7f; //a为第一个字节 取低7位
        a = a<<7; //a左移7位 为B的7位腾出空间
        a |= b; //A的低7位+B的低7位
        v = a;
    }
    
    
    printf("%d\n", v);
    
    return 0;
}

这里为了简单起见,最多只允许两个字节的varint编码

下面开始解析格式

payload-size:有效载荷,也就是实际数据所占的位置,这里是0x03,表明实际数据是三个字节,也就是header-size + typeN + valueN

ROWID:是sqlite对于一张表内数据的唯一标志,有点类似于唯一自增id,但这个是给sqlite自己用的,这里是0x01,表明是第一个

header-size:头尺寸,表明类型标志的大小(包含自身),这里是0x02,说明它和它下面的一个是头部

type1:第一个类型,具体类型可参阅下表,如果有多个类型,将会依次排列

value1:实际数据,根据type计算二来,这里是0x0A,对应的就是十进制的10,如果有多个值,将会依次排列

例如:

Serial Type Codes Of The Record Format

Serial TypeContent SizeMeaning
00Value is a NULL.
11Value is an 8-bit twos-complement integer.
22Value is a big-endian 16-bit twos-complement integer.
33Value is a big-endian 24-bit twos-complement integer.
44Value is a big-endian 32-bit twos-complement integer.
56Value is a big-endian 48-bit twos-complement integer.
68Value is a big-endian 64-bit twos-complement integer.
78Value is a big-endian IEEE 754-2008 64-bit floating point number.
80Value is the integer 0. (Only available for schema format 4 and higher.)
90Value is the integer 1. (Only available for schema format 4 and higher.)
10,11variableReserved 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)/2Value is a BLOB that is (N-12)/2 bytes in length.
N≥13 and odd(N-13)/2Value is a string in the text encoding and (N-13)/2 bytes in length. The nul terminator is not stored.

如此,基础格式便解析完成,虽然还会很多格式没有说,但本文只是初窥门径,所以便足够了,之后涉及到的更多内容,则会在接下来的文章继续