@H_404_4@
@H_404_4@1．磁盘文件管理@H_404_4@sqlite使用了@H_404_4@OS提供的文件管理功能来实现磁盘文件的管理，在@H_404_4@sqlite中每一个打开的数据库文件都是下列结构的实例。
@H_404_4@struct OsFile{
@H_404_4@ HANDLE h;/*在@H_404_4@Windows下访问文件的句柄；@H_404_4@*/
@H_404_4@ int locked;/*0代表没有锁，大于@H_404_4@0:表示写锁，小于@H_404_4@0:读锁@H_404_4@*/
@H_404_4@};
@H_404_4@HANDLE是@H_404_4@Windows下的文件标识符，通过它我们可以直接操纵磁盘文件，可以实现文件的读写，文件的随机随机访问，并且还能对文件的随机访问进行优化，这对于小型数据库已经足够了，没有必要自己开发像@H_404_4@ISAM的文件管理工具。在@H_404_4@OsFile结构中可以看到一个锁标识@H_404_4@locked，这是@H_404_4@sqlite中非常重要的结构，利用该标志允许@H_404_4@sqlite移植到多线程环境下。在@H_404_4@Windwos下磁盘文件中的偏移地址是按照字节来计算的，这样我们完全可以操纵文件中的单个字节，在文件管理层中，@H_404_4@sqlite改变了@H_404_4@Windows中的@H_404_4@API函数的调用接口，并提供了丰富的文件操作接口，并且实现了文件锁，在多线程环境下，文件锁是@H_404_4@DBMS磁盘文件管理器必须的功能。我们可以调用@H_404_4@Windows API函数，来实现文件锁，由于@H_404_4@Windows 98/Me中不支持@H_404_4@LockFileEx，也就是说不存在读写锁的概念，这就给我们造成了很大问题，首先是在@H_404_4@Windows 98/Me中的@H_404_4@LockFile不仅能够封锁写者，也能够封锁读者，也就是说如果我们对文件的指定区间进行@H_404_4@LockFile而获得一个锁，那么这个区间不仅写者不能使用它，而且读者也不能使用它，这和我们平时的想法是不一样的，读者只能封锁写者，而不应该封锁读者。@H_404_4@sqlite的解决方案是这样的：读锁可以封锁指定区间上的某一个字节。写锁可以封锁指定区间上的所有字节。而这里的指定区间就是锁区间，这样就可以保证只有一个写者。另外在文件获得写锁或者读锁之前，必须先获得一个文件上的锁区间上第一个字节的锁。这将阻止了两个进程同时在一个文件上获得一个锁。当文件处于读锁状态，而现在想在该文件上加上写锁，那么该文件的读锁状态会自动的转化为写锁状态，同理写锁也会自动的转化为读锁，这样就打破了文件死锁的必要条件“循环等待”，防止了两个进程进入死锁状态。另外@H_404_4@sqlite中还实现了临界区，利用它可以防止两个不同的线程同时访问一个资源。
在@H_404_4@sqlite中缓冲区管理器@H_404_4@(Pager)才用了页式缓冲区管理策略，每一个页的大小都是@H_404_4@1024B，@H_404_4@Pager不仅实现数据库文件的并发控制，而且实现了事务日志和检查点日志的相关操作。在@H_404_4@sqlite中一个页的大小可以随意更改，但是是@H_404_4@1024B的时候效果更好。另外还有在每一个页面的末尾的保留位@H_404_4@sqlITE_PAGE_RESERVE，通常为@H_404_4@0。
在@H_404_4@sqlite中每一个页都有一个页头部@H_404_4@PgHdr，它是实现事务处理的关键。该结构对于应用软件程序员来说是透明的，它仅仅是一个内部结构。@H_404_4@PgHdr仅仅在@H_404_4@Pager.c文件中才能使用，该结构中包含一个@H_404_4@hash冲突链表，它主要使用来解决由于@H_404_4@PgHdr.pgno有相同的@H_404_4@hash值而造成的冲突。还有一个引用计数，它是用来表示该页当前有几个在使用它。@H_404_4@PgHdr维护的以下几个链表：空闲页链表、页的链表（所有内存中的页），处于检查点日志上页的链表，脏页链表，@H_404_4@hash冲突页链表。那么相应的@H_404_4@Pager结构中也保存了相应的链表头部，有的还有链表的尾部。比如说空闲页链表它采用了先进先出的页面管理的策略，每一个磁盘页的在内存中都是以@H_404_4@PgHdr开始，这个结构后面就是磁盘页的内容，上层软件主要使用@H_404_4@PgHdr后面的磁盘文件数据。在@H_404_4@PgHdr结构中有两个对事务操作有很重要的属性，@H_404_4@PgHdr.inJournal和@H_404_4@PgHdr.needSync这两个标志，就是他们来保证事务操作的原子性的，当我们想要对一个页做修改的时候，首先必须做的就是将它写到日志文件中去，那么上述两个标志将设置，但是我们想要把修改过的页，放到磁盘上，那么首先要将日志页先写入到磁盘上，当这个过程完成之后，@H_404_4@PgHdr.needSync将被清除，那么此时我们就可以安全的修改磁盘上的数据库文件。
一个事务的开始通常会把数据库文件标志为@H_404_4@sqlITE_WRITELOCK状态，在事务开始之前数据库文件处于@H_404_4@sqlIITE_READLOCK状态，通过调用@H_404_4@sqlitepager_begin函数来转换到写状态，对于临时数据库文件来说，日志文件的打开推迟到真正需要写日志文件，对于一般的数据库文件，通常都需要打开日志文件，对于只读的数据库文件，没有必要打开一个日志文件。在一个数据库页需要被更改之前，通常会调用@H_404_4@sqlitepager_write来让该页的内容写到日志文件中，然后将日志文件中内容写到磁盘上，只有当该函数调用成功了之后，才能真正的修改该数据库页。修改后的页会放到脏页链表中等待一起被写到磁盘数据库文件，当对数据库文件修改完成的时候，然后将调用@H_404_4@sqlitepager_commit将本事务所有脏页链表上的页全部写到磁盘上，如果在这个过程中出现任何错误，@H_404_4@rollback日志文件中的页。@H_404_4@sqlitepager_commit能将数据库文件状态转化为@H_404_4@sqlITE_READLOCK。检查点日志在@H_404_4@sqlite中用于一个较长事务中，检查点日志文件是一个临时的文件，当事务被提交后他们将自动的被关闭，然后该检查点日志文件也将自动的被删除。
@H_404_4@3．@H_404_4@sqlite中的@H_404_4@B-Tree结构@H_404_4@
@H_404_4@B-Tree主要是用来管理数据库文件和索引的，它把数据库文件分成了@H_404_4@n个大小为@H_404_4@1024B的页，每一个页都有一个页号，页号是从@H_404_4@1开始的，页号是页的唯一标示，第一个页通常存放了数据库文件的元数据信息。@H_404_4@B-Tree的基本思想是：数据库文件的每一个页包含@H_404_4@N个数据库条目（记录）和@H_404_4@N+1个指向子页的指针。查找一个指定键值需要读@H_404_4@O(log(M))个页，@H_404_4@ M是@H_404_4@B-Tree中记录的个数。一个数据库文件可以拥有一个或者多个独立的@H_404_4@B-tree。每一个@H_404_4@B-tree可以通过它的根页的索引@H_404_4@(页码@H_404_4@)来区分。
数据库的第一个页通常是主数据库页@H_404_4@(master pager)，它一定是一个结构为@H_404_4@PageOne的对象，它并不是用来存放记录的，它的功能主要是：
@H_404_4@1．利用@H_404_4@magic string检查数据库文件的完整性，它是一个表示字符串。
@H_404_4@2．利用@H_404_4@magic int来确定是不是需要改变磁盘数据的字节顺序。
@H_404_4@3．保存未使用页的页码的链表信息，同时记录了空闲链表中的页的个数。
@H_404_4@4．用来存放用户自定义的元数据信息，元数据信息通常描述了记录的结构和意义。
由于在不同的机器中数据的表示形式是不一样的，例如在@H_404_4@X86机器上，数据是按照@H_404_4@little-endian，也就是低字节放在高字节的前面，为了兼容不同的处理器上的字节的顺序，@H_404_4@ sqlite使用@H_404_4@big-endian而不是本地直接顺序。这就是@H_404_4@magic int存在的原因。
关于字节对齐的问题。字节对齐可以提高我们访问内存的速度。对于@H_404_4@32位的地址，我们选择按照@H_404_4@4个字节对齐，因为@H_404_4@4个字节恰好是@H_404_4@32位的，那么地址线也作为数据总线，所以每次读一个数据都是@H_404_4@32位，一次恰好可以读取@H_404_4@32位，这是很重要的。假如说不字节对齐的话，假如说一个大小为@H_404_4@7个字节的对象，如果按照内存对齐，那么它可以占据两个字节，那么只需要两次就可以读出，但是如果不对齐有可能占据@H_404_4@3个字节那么就需要读@H_404_4@3次了。这是在内存中当然不算什么，但是如果访问的是磁盘呢？显然字节对齐有利于减少读取磁盘的次数。
任何记录的@H_404_4@Key和@H_404_4@Data组合成了一个“@H_404_4@Payload”，小于@H_404_4@MX_LOCAL_PAYLOAD的@H_404_4@Payload字节放到数据库页中。如果@H_404_4@Payload大于@H_404_4@MX_LOCAL_PALOAD，多出来的字节放到@H_404_4@overflow页中。这样一个@H_404_4@Cell可以存放任意大小的对象。图@H_404_4@3.1所示就是@H_404_4@Cell的结构：
@H_404_4@
图@H_404_4@3.1
其中@H_404_4@CellHdr里面存放了记录和键值的大小，以及该@H_404_4@Cell的左孩子页码。@H_404_4@aPayload存放着该@H_404_4@Cell的有效负载，而@H_404_4@Ovfl是一个页码，它是指向一个溢出页页码，图@H_404_4@3.2所示就是一个溢出页的结构：
@H_404_4@
图@H_404_4@3.2
其中@H_404_4@iNext是指向下一个溢出页的页码，@H_404_4@aPayload里面存放的有该页的有效负载。该页主要用来存放溢出的@H_404_4@Cell和空闲页页号信息等。当它用来存放空闲页页号信息的时候，通常放的是一个@H_404_4@FreelistInfo的结构，而该空闲页的页号也将赋值给@H_404_4@PageOne.Freelist变量。
对于@H_404_4@Btree中的每一个页都有一个头部结构体@H_404_4@PageHdr。该结构体存放了最右边的那个孩子页的页码，还有第一个@H_404_4@Cell的偏移地址，我们通过第一个@H_404_4@Cell可以查找所有的@H_404_4@Cells，它是一个链表结构，不过该链表结构中的指针是并不是@H_404_4@C语言中的指针，而是@H_404_4@Cell在@H_404_4@aPayload中的偏移字节数，所以它即使存放到磁盘中，当它在一次的读出的时候仍旧能够使用。还有一个变量@H_404_4@firstFreeBlk是用来记录第一个@H_404_4@FreeBlk结构的偏移地址，通过它我们可以找到在该页中的空闲块的链表，进而来管理该页上的所有空闲块。在一个页中空闲块是一个@H_404_4@FreeBlk结构，所有的空闲块按照地址的先后顺序而组成一个@H_404_4@FreeBlk List。注意@H_404_4@FreeBlk链表总是按照地址有序的，每一个@H_404_4@FreeBlk都有两个变量，一个是表示该空闲块大小的@H_404_4@iSize，另外还有一个指向下一个@H_404_4@FreeBlk块的@H_404_4@iNext。该结构是与溢出页的数据结构不一样的，溢出页主要使用来管理溢出页链表的，而@H_404_4@FreeBlk是用来管理页中的空闲块的。图@H_404_4@3.3所示就是一个页中的@H_404_4@Cell和@H_404_4@FreeBlk的组织形式，实际的运行过程中并不是这个样子的，有可能@H_404_4@Cell和@H_404_4@FreeBlk交替出现，这只是@H_404_4@DBMS运行中的一个特殊状态，：
@H_404_4@MemPage和@H_404_4@Pager中的一个页对应，它和@H_404_4@OverfullPage的性质是一样的，都是一个内存页，他们的大小都是@H_404_4@1024B，但是@H_404_4@MemPage是一个正在使用的页，是用来存放@H_404_4@Cell即有效记录。另外在@H_404_4@MemPage中有一个非常重要的结构就是存取访问点@H_404_4@apCell[]，它存放着每一个@H_404_4@Cell的在页中的偏移地址，这样可以在常数时间内读取一个@H_404_4@Cell，而不用依靠@H_404_4@Cell的链表结构，但是它也提高了程序的复杂性，例如我们什么时间更新@H_404_4@apCell[]呢，而且它什么时间是有效的，因为在数据库中有很多的插入和删除操作，每一次插入和删除我们都要更改@H_404_4@apCell[]，因为插入和删除有可能让@H_404_4@apCell[]中的指针失效。@H_404_4@MemPage使用了共用体来存放@H_404_4@Cell。
@H_404_4@union u_page_data {
@H_404_4@char aDisk[sqlITE_PAGE_SIZE];
@H_404_4@PageHdr hdr;
@H_404_4@ } u;
在这个@H_404_4@union结构中，@H_404_4@aDisk的前面的@H_404_4@sizeof(PageHdr)个字节应该是一个@H_404_4@PageHdr实例，而后面才是真正的@H_404_4@Cell，这就很大的提高了方便性，我们只需要操纵@H_404_4@aDisk就可以知道@H_404_4@aDisk所有的信息了。该结构体通常放到@H_404_4@MemPage开始的地方，该结构体以后的才是一些标志信息。@H_404_4@u的结构如图@H_404_4@3.3，该图中显示了两个@H_404_4@MemPage，里面存放了该结构。
@H_404_4@
图@H_404_4@3.4
图@H_404_4@3.4显示了整个@H_404_4@B-Tree的结构，从这个结构中可以看到，在每一个页中的@H_404_4@Cell都是有序的，假设是从小到大排列，@H_404_4@PageHdr指向的那个页的所有记录将大于该页中的所有记录，每一个@H_404_4@Cell中包含有一个记录，每一个@H_404_4@Cell都指向一个左孩子页，该页中的所有记录将小于@H_404_4@Cell中的记录。这些@H_404_4@Cell将直接存放到磁盘的数据库文件上。@H_404_4@Cell的头部、@H_404_4@PageHdr、其他辅助信息都不会被存放到磁盘上，他们是用来帮助@H_404_4@DBMS管理文件的。
