sqlite初探(二)——删改对文件格式的影响

2019年1月16日 0 作者 筱枫

近期事情比较多,所以更新得比较迟

本文涉及到数据库记录的删改对文件格式的影响,以及索引如何存储在文件中,需要有着b树的相关概念(包括b树结构,增删改查等方面)

紧接前文sqlite初探(一)——文件格式

删除和修改对于文件格式的影响是差不多,删除只是简单的找到这条记录的id,然后将其标记为已删除即可

首先执行如下语句,我们来重新开一个sqlite文件

create table hello(id int);
insert into hello values(10);
insert into hello values(20);
insert into hello values(30);

现在用hexdump打开文件,可以看到三条记录

如上文所说,这里的三条记录是这个样子的:

下面我来删除其中一条记录,这里就以删除第二条为例(ps:03 02 02 01 14 这条)

可以很明显的看到,这条记录变成了这个样子,而且上面的单元格指针(即0x0ffb 0x0ff1)也顺序前移。注意开头0x0d后面的0x0ff6,这里按照官方文档的解释,是第一个空闲单元格的地址,而空闲单元格则是链表的形式存在,每个空闲的单元格前两个字节是下一个空闲单元格的指针(若当前单元格是最后一个则是0),第二第三个字节表明了当前空闲单元格的大小,图中是0x05,也就是我圈出来的这五个字节)

这里附上原文:

A freeblock is a structure used to identify unallocated space within a b-tree page. Freeblocks are organized as a chain. The first 2 bytes of a freeblock are a big-endian integer which is the offset in the b-tree page of the next freeblock in the chain, or zero if the freeblock is the last on the chain. The third and fourth bytes of each freeblock form a big-endian integer which is the size of the freeblock in bytes, including the 4-byte header. Freeblocks are always connected in order of increasing offset. The second field of the b-tree page header is the offset of the first freeblock, or zero if there are no freeblocks on the page. In a well-formed b-tree page, there will always be at least one cell before the first freeblock.


接下来我们再删除一条记录,看看记录如何改变,这里删除第一条记录,也就是id为10的这条

有意思的地方出现了:

若是按照刚刚文档上所说,圈出来的前两个字节应该是偏移量才对,但依旧是0,不慌,看这个0x0a,在看看后面几个空闲的0,瞬间恍然大悟

sqlite将这两个空闲的单元格给合并在一块,形成了一个大的单元格(实际上很多文件系统也会如此处理,为了避免更多的磁盘碎片)


至于更改,则与删除差不多,更改的情况分为三种:

一:更改前后的所占单元格空间不变

二:更改后的单元格比原本要大(这种情况sqlite会首先去空闲单元格中找,看是否有地方可以容纳这个地方,若是没有,则追加至最后面的单元格,然后将原本的单元格标记为删除)

三:更改后的单元格比原来要小(这种情况要看究竟小多少,通过上面的空闲单元格描述我们可以得知,一个空闲单元格最少需要4个字节:2下一个单元格指针+2单元格大小标志)

(这里作者并未对这种情况有深入的了解,仅限于猜测:若是小于4个单元格,则不理会,若是大于等于4个单元格,则将其标记为空闲单元格)


接下来则是重头戏——索引

之前我一直有着这样一个好奇,b树究竟在sqlite中是怎么存储的呢?是如何序列化存储的呢?通过这段时间的研读,发现我把问题想得过于复杂了,其实最关键的就是b树的算法,只要理解的b树的算法,再看sqlite的文件格式,就会简单很多

关于b树,建议可以看一看这篇文章从B树、B+树、B*树谈到R 树

这里简单的说下我对于b树的理解

b树分为两种结构:节点、叶子

叶子是存储实际数据的,而节点,则是存储指向叶子节点的指针

在sqlite中,开启了索引后叶子节点中存储的则是经过排序后的数据,所以查找起来相当快,而要找到这片叶子,可以很简单的通过节点上面的指针来找到

例如下图:

类似于二叉树,通过一个关键值将数据分为左右两部分,这样查找的时候就相当于使用著名的二分搜索法

例如我们要找5,可以看到,节点里面刚好就是5,直接按照这个5指向的真正数据去取即可

要找3也不难,我们可以看到,3是小于5的,所以去找左边的叶子(在sqlite中,这里会进行一次磁盘读取),随后我们用顺序查找可以很快找到关键字3,再去取3指向的真正数据即可

上面所说的比较抽象,如果没有看懂也没关系,下面实际来看看sqlite是如何处理的

将刚刚创建的数据库不要,我们换个新的,依旧执行上面4条语句,生成一张表后三条记录,接着,我们对id这个键创建索引

create index id_index on hello(id);

接着我们再用hexdump来看看

创建索引后会单独为索引增加一个页,所以最大长度为0x3000(我这里截图是只截了0x1000-0x3000)

0x1000那里没有什么好说的,0x0d表明是一个数据页

但0x2000这里的0x0a表明它是一个索引页,按照官方手册来说,索引页也是采用单元格的形式来存储数据,而且结构跟数据页的一模一样,在这里我们可以很清楚的看到,索引的占用大小比数据还要大…….

索引页的空闲单元格起始是0xffef,而数据页的则是0xfff1,差了2个字节

但是没关系,我们继续看最后标出来的04 03 01 09 0a

注意,这里面是没有了rowid行,也就是数据页中紧跟数据单元格大小的那个字节(详情见上文)

开头的04表明数据内容有4个字节,由于没有了rowid行,所以第二个03就表明头长度,3表明

03 01 09 这三个是头字节,最后的0a则是实际内容(ps:09在这里解释为1,详情见上文)

这个数据结构如果打印出来会是这个样子

sqlite首先会根据这里面来查找id,然后根据id去找到对应的数据,后面的09(解释为1)就派上了用场,这里的1表明它处在第一个单元格里面,所以直接根据单元格指针去找即可(当然这里我还没有探究若是跨页会如何查找,但跨页等也不再这里的讨论范围内)

当然你可能会问,按照我前面所画的图,不应该还会有一个节点页吗?

当然会有,只不过现在数据量比较小而已,接下来我们用代码批量插入数据,注意,数据数量要刚刚好,不能太多也不能太少,太多的话会导致有很多无用的数据在里面——主要是看起来比较恼火

我的代码如下,当然你也可以改成你自己的

<?php

$sqlite = new sqlite3("hello.test");

$i=500;
while ($i--)
{
	$sqlite->query('INSERT INTO hello VALUES('.mt_rand(100, 200).')');
}

接着我们来看sqlite文件

可以很明显的看到,0x3000、0x4000的位置是两个索引页,0x5000、0x6000是两个数据页

至于0x1000,开头的0x05表明它是数据页的节点指针(这里对应的就是上面所说的b树的节点)

0x2000开头的0x02标明是索引页的节点指针

根据官方手册(详见前文),图中我标注出来的两个四字节的数是最右侧的指针,这里0x1000表明的数据页指针指向的是0x6000(第七页),而0x2000的指针指向的则是0x4000(第五页)

同时我们可以看到,其中分别存储了一个单元格数据,接下来我们就看看其中的内容

首先请看0x1000的数据,位于0x0ffa处,加上基地址就是0x1fffa

这里的单元格格式跟之前不一样,官方文档如下:

开头的四个字节是叶子指针,这里是 0x00 00 00 06,所以是指向第6页

接着是个varint的数,这表明关键字,用于区分数据,此处为0x83 0x62,用上文我们写的varint程序转换一下,就是482,表明第482个单元以前的内容,全部都在第六页,也就是0x5000所对应的数据页里面

接着我们看看0x5000中的内容

下面我们看看索引页的情况

如法炮制,我们通过0x2000节点页的单元格找到0x3000

开头的0x04表明指向的第4页,后面的这一串跟数据单元格中的数据很相像(注意不是数据节点,即开头是0x0d的数据页)

0x07表明有七个字节的负载

0x03表明头部一共占了三个字节(包括其本身),这里是0x03 0x02 0x02

之后就是详细的数据,注意这里面的数据不是采用的varint,而是实打实根据0x02的含义来

0x02表明是16位的大端字节,这里一个是0x0094 另外一个是0x00d4,表明小于或者等于它的情况都会出现第4页(这里为何会有两个数据笔者暂时不了解,需要详细阅读源码)

这样查找的顺序就清晰明了了

假设有索引的情况下,且格式如上

首先前往0x2000的位置读取索引节点页(磁盘操作一次),然后根据数的大小判断是否是在左叶还是右叶(右叶就是0x2008开始,4个字节的页码,这里是0x05,说明有两个页,一个是第4页,一个是第五页)

再接着读取索引页(磁盘操作一次),通过索引页当中的内容进行顺序查找,确定数据的实际位置

再读取一次0x3000数据节点页(磁盘操作一次),确定单元格实际的页

最后读取实际数据页(磁盘操作一次),再通过单元格索引找到对应的数据

虽然看上去数据量很少,而且也读取了4次磁盘,但b树的一个关键特性就是相对于数据量的增长,读取磁盘的次数增长极慢

其中数据节点页和索引节点页是必读的,所以在每次操作中可以暂且忽略,假设索引页有100张(节点指针可以存入索引节点页中),数据页也有一百100张(节点指针可以存入数据节点页),通过b树的特性,也仅仅只需要读取4次!

倘若没有索引的话,就只能顺序查找数据了,要将这100个数据页依次读取一遍!

所以,b树确实对磁盘挺好呢(笑)

但是添加索引会带来额外负担,增删改效率的下降(因为要额外维护一份索引),以及更多的空间占用(索引占用空间),但相对而言,数据库主要就是用来查询的,所以这份代价是值得的。

这次的文件解析就到这里了,下一章会谈谈sqlite当中的事务如何处理,其实也可以直接阅读官方文档,当中都有详细说明,相对于数据格式,事务反而显得比较简单了2333