SQLite的底层实现的研究_sql

概述1．磁盘文件管理 SQLite使用了OS提供的文件管理功能来实现磁盘文件的管理，在SQLite中每一个打开的数据库文件都是下列结构的实例。 struct OsFile{ HANDLE h;/*在Windows下访问文件的句柄；*/ int locked;/*0代表没有锁，大于0:表示写锁，小于0:读锁*/ }; HANDLE是Windows下的文件标识符，通过它我们可以

1．磁盘文件管理

sqlite使用了OS提供的文件管理功能来实现磁盘文件的管理，在sqlite中每一个打开的数据库文件都是下列结构的实例。

struct Osfile{

HANDLE h;/*在windows下访问文件的句柄；*/

int locked;/*0代表没有锁，大于0:表示写锁，小于0:读锁*/

};

HANDLE是windows下的文件标识符，通过它我们可以直接 *** 纵磁盘文件，可以实现文件的读写，文件的随机随机访问，并且还能对文件的随机访问进行优化，这对于小型数据库已经足够了，没有必要自己开发像ISAM的文件管理工具。在Osfile结构中可以看到一个锁标识locked，这是sqlite中非常重要的结构，利用该标志允许sqlite移植到多线程环境下。在WinDWos下磁盘文件中的偏移地址是按照字节来计算的，这样我们完全可以 *** 纵文件中的单个字节，在文件管理层中，sqlite改变了windows中的API函数的调用接口，并提供了丰富的文件 *** 作接口，并且实现了文件锁，在多线程环境下，文件锁是DBMS磁盘文件管理器必须的功能。我们可以调用windows API函数，来实现文件锁，由于windows 98/Me中不支持LockfileEx，也就是说不存在读写锁的概念，这就给我们造成了很大问题，首先是在windows 98/Me中的Lockfile不仅能够封锁写者，也能够封锁读者，也就是说如果我们对文件的指定区间进行Lockfile而获得一个锁，那么这个区间不仅写者不能使用它，而且读者也不能使用它，这和我们平时的想法是不一样的，读者只能封锁写者，而不应该封锁读者。sqlite的解决方案是这样的：读锁可以封锁指定区间上的某一个字节。写锁可以封锁指定区间上的所有字节。而这里的指定区间就是锁区间，这样就可以保证只有一个写者。另外在文件获得写锁或者读锁之前，必须先获得一个文件上的锁区间上第一个字节的锁。这将阻止了两个进程同时在一个文件上获得一个锁。当文件处于读锁状态，而现在想在该文件上加上写锁，那么该文件的读锁状态会自动的转化为写锁状态，同理写锁也会自动的转化为读锁，这样就打破了文件死锁的必要条件“循环等待”，防止了两个进程进入死锁状态。另外sqlite中还实现了临界区，利用它可以防止两个不同的线程同时访问一个资源。

2．缓冲区管理器

在sqlite中缓冲区管理器(Pager)才用了页式缓冲区管理策略，每一个页的大小都是1024B，Pager不仅实现数据库文件的并发控制，而且实现了事务日志和检查点日志的相关 *** 作。在sqlite中一个页的大小可以随意更改，但是是1024B的时候效果更好。另外还有在每一个页面的末尾的保留位sqlITE_PAGE_RESERVE，通常为0。

在sqlite中每一个页都有一个页头部PgHdr，它是实现事务处理的关键。该结构对于应用软件程序员来说是透明的，它仅仅是一个内部结构。PgHdr仅仅在Pager.c文件中才能使用，该结构中包含一个hash冲突链表，它主要使用来解决由于PgHdr.pgno有相同的hash值而造成的冲突。还有一个引用计数，它是用来表示该页当前有几个在使用它。PgHdr维护的以下几个链表：空闲页链表、页的链表（所有内存中的页），处于检查点日志上页的链表，脏页链表，hash冲突页链表。那么相应的Pager结构中也保存了相应的链表头部，有的还有链表的尾部。比如说空闲页链表它采用了先进先出的页面管理的策略，每一个磁盘页的在内存中都是以PgHdr开始，这个结构后面就是磁盘页的内容，上层软件主要使用PgHdr后面的磁盘文件数据。在PgHdr结构中有两个对事务 *** 作有很重要的属性，PgHdr.inJournal和PgHdr.needSync这两个标志，就是他们来保证事务 *** 作的原子性的，当我们想要对一个页做修改的时候，首先必须做的就是将它写到日志文件中去，那么上述两个标志将设置，但是我们想要把修改过的页，放到磁盘上，那么首先要将日志页先写入到磁盘上，当这个过程完成之后，PgHdr.needSync将被清除，那么此时我们就可以安全的修改磁盘上的数据库文件。

一个事务的开始通常会把数据库文件标志为sqlITE_WRITELOCK状态，在事务开始之前数据库文件处于sqlIITE_READLOCK状态，通过调用sqlitepager_begin函数来转换到写状态，对于临时数据库文件来说，日志文件的打开推迟到真正需要写日志文件，对于一般的数据库文件，通常都需要打开日志文件，对于只读的数据库文件，没有必要打开一个日志文件。在一个数据库页需要被更改之前，通常会调用sqlitepager_write来让该页的内容写到日志文件中，然后将日志文件中内容写到磁盘上，只有当该函数调用成功了之后，才能真正的修改该数据库页。修改后的页会放到脏页链表中等待一起被写到磁盘数据库文件，当对数据库文件修改完成的时候，然后将调用sqlitepager_commit将本事务所有脏页链表上的页全部写到磁盘上，如果在这个过程中出现任何错误，rollback日志文件中的页。sqlitepager_commit能将数据库文件状态转化为sqlITE_READLOCK。检查点日志在sqlite中用于一个较长事务中，检查点日志文件是一个临时的文件，当事务被提交后他们将自动的被关闭，然后该检查点日志文件也将自动的被删除。

3．sqlite中的B-Tree结构

B-Tree主要是用来管理数据库文件和索引的，它把数据库文件分成了n个大小为1024B的页，每一个页都有一个页号，页号是从1开始的，页号是页的唯一标示，第一个页通常存放了数据库文件的元数据信息。B-Tree的基本思想是：数据库文件的每一个页包含N个数据库条目（记录）和N+1个指向子页的指针。查找一个指定键值需要读O(log(M))个页， M是B-Tree中记录的个数。一个数据库文件可以拥有一个或者多个独立的B-tree。每一个B-tree可以通过它的根页的索引(页码)来区分。

数据库的第一个页通常是主数据库页(master pager)，它一定是一个结构为PageOne的对象，它并不是用来存放记录的，它的功能主要是：

1．利用magic string检查数据库文件的完整性，它是一个表示字符串。

2．利用magic int来确定是不是需要改变磁盘数据的字节顺序。

3．保存未使用页的页码的链表信息，同时记录了空闲链表中的页的个数。

4．用来存放用户自定义的元数据信息，元数据信息通常描述了记录的结构和意义。

由于在不同的机器中数据的表示形式是不一样的，例如在X86机器上，数据是按照little-endian，也就是低字节放在高字节的前面，为了兼容不同的处理器上的字节的顺序， sqlite使用big-endian而不是本地直接顺序。这就是magic int存在的原因。

关于字节对齐的问题。字节对齐可以提高我们访问内存的速度。对于32位的地址，我们选择按照4个字节对齐，因为4个字节恰好是32位的，那么地址线也作为数据总线，所以每次读一个数据都是32位，一次恰好可以读取32位，这是很重要的。假如说不字节对齐的话，假如说一个大小为7个字节的对象，如果按照内存对齐，那么它可以占据两个字节，那么只需要两次就可以读出，但是如果不对齐有可能占据3个字节那么就需要读3次了。这是在内存中当然不算什么，但是如果访问的是磁盘呢？显然字节对齐有利于减少读取磁盘的次数。

任何记录的Key和Data组合成了一个“Payload”，小于MX_LOCAL_PAYLOAD的Payload字节放到数据库页中。如果Payload大于MX_LOCAL_PALOAD，多出来的字节放到overflow页中。这样一个Cell可以存放任意大小的对象。图3.1所示就是Cell的结构：

图3.1

其中CellHdr里面存放了记录和键值的大小，以及该Cell的左孩子页码。aPayload存放着该Cell的有效负载，而Ovfl是一个页码，它是指向一个溢出页页码，图3.2所示就是一个溢出页的结构：

图3.2

其中iNext是指向下一个溢出页的页码，aPayload里面存放的有该页的有效负载。该页主要用来存放溢出的Cell和空闲页页号信息等。当它用来存放空闲页页号信息的时候，通常放的是一个FreeListInfo的结构，而该空闲页的页号也将赋值给PageOne.FreeList变量。

对于Btree中的每一个页都有一个头部结构体PageHdr。该结构体存放了最右边的那个孩子页的页码，还有第一个Cell的偏移地址，我们通过第一个Cell可以查找所有的Cells，它是一个链表结构，不过该链表结构中的指针是并不是C语言中的指针，而是Cell在aPayload中的偏移字节数，所以它即使存放到磁盘中，当它在一次的读出的时候仍旧能够使用。还有一个变量firstFreeBlk是用来记录第一个FreeBlk结构的偏移地址，通过它我们可以找到在该页中的空闲块的链表，进而来管理该页上的所有空闲块。在一个页中空闲块是一个FreeBlk结构，所有的空闲块按照地址的先后顺序而组成一个FreeBlk List。注意FreeBlk链表总是按照地址有序的，每一个FreeBlk都有两个变量，一个是表示该空闲块大小的iSize，另外还有一个指向下一个FreeBlk块的iNext。该结构是与溢出页的数据结构不一样的，溢出页主要使用来管理溢出页链表的，而FreeBlk是用来管理页中的空闲块的。图3.3所示就是一个页中的Cell和FreeBlk的组织形式，实际的运行过程中并不是这个样子的，有可能Cell和FreeBlk交替出现，这只是DBMS运行中的一个特殊状态，：

图3.3

MemPage和Pager中的一个页对应，它和OverfullPage的性质是一样的，都是一个内存页，他们的大小都是1024B，但是MemPage是一个正在使用的页，是用来存放Cell即有效记录。另外在MemPage中有一个非常重要的结构就是存取访问点apCell[]，它存放着每一个Cell的在页中的偏移地址，这样可以在常数时间内读取一个Cell，而不用依靠Cell的链表结构，但是它也提高了程序的复杂性，例如我们什么时间更新apCell[]呢，而且它什么时间是有效的，因为在数据库中有很多的插入和删除 *** 作，每一次插入和删除我们都要更改apCell[]，因为插入和删除有可能让apCell[]中的指针失效。MemPage使用了共用体来存放Cell。

union u_page_data {

char adisk[sqlITE_PAGE_SIZE];

PageHdr hdr;

} u;

在这个union结构中，adisk的前面的sizeof(PageHdr)个字节应该是一个PageHdr实例，而后面才是真正的Cell，这就很大的提高了方便性，我们只需要 *** 纵adisk就可以知道adisk所有的信息了。该结构体通常放到MemPage开始的地方，该结构体以后的才是一些标志信息。u的结构如图3.3，该图中显示了两个MemPage，里面存放了该结构。

图3.4

图3.4显示了整个B-Tree的结构，从这个结构中可以看到，在每一个页中的Cell都是有序的，假设是从小到大排列，PageHdr指向的那个页的所有记录将大于该页中的所有记录，每一个Cell中包含有一个记录，每一个Cell都指向一个左孩子页，该页中的所有记录将小于Cell中的记录。这些Cell将直接存放到磁盘的数据库文件上。Cell的头部、PageHdr、其他辅助信息都不会被存放到磁盘上，他们是用来帮助DBMS管理文件的。