实验报告-存储管理

实验三存储管理实验内容：数据文件的组织；缓冲区管理；空闲空间管理；实验要求：数据文件的组织：段页式组织方式；支持基本数据类型，可不支持大对象数据；缓冲区管理：缓冲区页面组织；缓冲区查找；缓冲区淘汰；空闲空间管理：空闲空间组织；空闲空间分配；空闲空间回收；实验步骤：本实验代码实现使用的是C语言。数据文件的组织：我们借助Oracle里面关于数据存储的概念，划分一个表空间，表空间里面又分为数据段，索引段和数据字典段。每个段里面又分为等长大小的区，每个区由若干个页（PAGE_PER_EXTENT我们设为200）来组成。具体的定义在文件tablespace.h里面。而在页中存储记录时，页头保存这个页中有多少条元组；然后剩余的空间来存储具体的记录：每个记录有记录头，记录头记录这个元组的模式的指针，元组的长度和时间戳；记录体存储具体的属性数据。而在记录体中存储数据时，我们现在支持三种数据类型：int,char(n),vchar(n)。考虑到对齐的因素，我们每个属性的数据都从4的整数倍的地址开始存储，所以数据字典里记录的各个属性的偏移量都是4的倍数。具体到单个元组插入的时候过程是这样的：先读数据字典，找到这个表所在的空间（第一个区间），然后读这个区间头，找到一个有空闲空间的页，然后读出那一页，按照数据字典的解析把该元组插入到这个页中的空闲位置，然后将该页写回到文件中。具体的文件组织可以用下面的图来表示：数据文件：｜文件头｜数据段｜索引段｜数据字典段｜数据段：｜区间一｜区间二｜区间三｜……｜区间：｜区间头｜页一｜页二｜页三｜……｜页：｜页头｜元组一｜元组二｜元组三｜……｜元组：｜记录模式指针｜长度｜时间戳｜属性一｜属性二｜属性三｜……｜我们所定义的一些头部定义如下所示：structfile_header{ intmagic_num;/*filemagicnumber*/ unsignedcharbitmap[MAX_EXTENT];/*recordwhichextenthavefreespace*/};structextent_header{ intrec_per_page; intnext;/*nullis-1*/ intbitmap[MAX_DAT_PAGE];};structindex_header{ charbitmap[MAX_IDX_PAGE/CHAR_BIT];};structdict_header{ struct{ intflag; chartname[20]; }table[MAX_TABLE_NUM];};各个头部的主要功能就是记录空闲空间，回收空闲空间。到下面空闲空间管理时我们会具体介绍。缓冲区管理：缓冲区页面组织：以下是我们缓冲区的定义：缓冲区一共有BUFFER_SIZE个缓冲区页面，一个页面存储一个文件的块号pgid，以及是否该页被修改dirty，以及这一页的pinnumber，还有就是文件物理块的内容page。structbuff_node{ intpgid;/*blockid*/ intdirty;/*ifbemodified*/ intpin;/*pinnumber*/ charpage[PAGE_SIZE];/*pagedata*/};#defineBUFFER_SIZE2000structbuff_nodebuff[BUFFER_SIZE];intinit_buffer(void);/*setallbuffernodeempty*/intclose_buffer(void);/*writebackdityblock*/intgetpg_LRU(intpgid);/*getpgidtobuffer,andreturnitspointerinbuffer*/intsetbf_dirty(intbuffid);intdelbf_page(intbuffid);缓冲区查找：为了能在缓冲区里面直接定位到想要的页，我们建了一个简单的hash表，就是一个数组inthtab[TOTAL_PAGE]。当我们需要几个的某一页的时候，直接到这个表中能查这个页现在是在缓冲区的哪个地方。如果能查到，则直接返回这个页，如果找不到，则需要淘汰缓冲区里的某个页面，然后从文件中把这一页加载进来。具体代码实现在getpg_LRU(intpgid)里面，伪代码如下所示：intgetpg_LRU(intpgid){ if(htab[pgid]!=-1){//需要的页在缓冲区中 update_lru(htab[pgid]);//更新lru链表 returnhtab[pgid]; } if(有空的缓冲区页){ 得到该空页empty 把该页加载到缓冲区 returnempty; } 从lru链上得到要淘汰的页empty=lru_list.head; if(buff[empty].dirty==1)//写回被修改的页 write_page(buff[empty].page,buff[empty].pgid); htab[buff[empty].pgid]=-1; } 把新的页加载到缓冲区 returnempty;}缓冲区淘汰：缓冲区的淘汰算法我们采用是LRU。为了能快速找到要淘汰的页，我们定义了两个链表，空缓冲区链表，和lru淘汰链表。如下所示：struct{ inthead; inttail; struct{ intnext; intprev; }pg[BUFFER_SIZE];}lru_list;struct{ intcnt; inthead; inttail; intque[BUFFER_SIZE];}empty_list;这样当我们所需要的页不在缓冲区中时，我们首先查找empty_list，如果有空闲的缓冲区区间，我们就把新进来的页放在那个空缓冲区页面中，然后更新一下empty_list和lru_list。如果缓冲区中没有空闲空间，我们这时候需要淘汰一个页，我们仅仅是淘汰lru_list头上的那个页，因为那个页就是最早没有被访问到的页，我们每访问一个页都要更新lru_list，就把那个页放到lru_list的链表尾，这就保证了链表头上的页是需要被淘汰的。这样我们的淘汰算法就是O(1)的，能保证效率。空闲空间管理：1)空闲空间的组织：对空闲空间的管理我们统一使用的是位图的管理方式，在文件头，区间头，索引段头，页头，都有相应的位图，文件头的位图管理空闲区间的分配，区间头里面管理空闲页的分配，在每个页里面，页头管理这个页中的空闲空间，以便插入相就应的记录。如下所示：structfile_header{ intmagic_num;/*filemagicnumber*/ unsignedcharbitmap[MAX_EXTENT];/*recordwhichextenthavefreespace*/};structextent_header{ intrec_per_page; intnext;/*nullis-1*/ intbitmap[MAX_DAT_PAGE];};structindex_header{ charbitmap[MAX_IDX_PAGE/CHAR_BIT];};structdict_header{ struct{ intflag; chartname[20]; }table[MAX_TABLE_NUM];};2)空闲空间的分配：具体到空闲空间的分配，就是先读出位图，然后从头扫描到一个空(值为0)的位，然后将这一页或区间给分配出去，并把这一位置为1。在tablespace.h里面，next_data_extent()是得到下一个可用的数据区间，next_empty_page(int*extid)是得到exitd这个区间里可用的一个空页，next_idx_page()是得到一个可用的索引页。3)空闲空间的回收：当一个页中没有数据存储在里面的时候，这个页就要被回收；当一个索引节点被删除的时候，这个页也要被回收。空闲空间的回收我们是把相应的位图上该页的位置值置为空（0），代表这一页现在已经是空闲的了，这就完成了空闲空间的回收。数据字典的建立：向数据库文件中插入记录之前，需要首先建立数据字典，描述要插入的表的各种信息以及各种属性。我们的数据字典的结构如下所示：enumtype_t{INT,CHAR};/*atable'srelationdefination*/structreldef{ charrelname[20]; charothername[20]; charauthor[20]; intattrcnt; intreclen; intreccnt; intattrptr; intviewptr;};/*aattribution'sdefine*/structattrdef{ charname[20]; enumtype_ttype; intlen; intoffset; intingretyptr; intattrexpptr;};#defineMAX_ATTR_NUM100/*atable'sdefine*/structtable_def{ intfirst_ext; intbtree_root; intbtree_level; structreldefrel; structattrdefattr[MAX_ATTR_NUM];};一个表的定义table_def里面记录这个表第一个区间的区间号，这个关系的信息（关系名，创建者，属性个数，记录长度，属性定义指针等等），以及各个属性的定义（属性名，属性类型，属性长度，属性在记录内的偏移等等）。所对应的createtable操作，就是填写上述定义的信息，然后将这些定义写到数据字典段，以后查找某个表的时候就可以找到这个表的信息，从而解析各个记录。记录的插入和删除：有关记录的插入删除操作在page.h里面。向一个表中插入一条元组的时候，首先从数据字典中得到这个表的信息，然后找到一个有足够空间可以插入该元组的块，然后将这个元组插入到这个空闲空间，然后更新一下块头的信息，把这个块写回文件。这完成了记录的插入操作。同样，进行记录的删除时，先找到要删除的记录所在的块，然后将这个块中最后一条记录覆盖掉这个记录，更新一个下块头信息，当这个块中没有记录存在时，要将这个块回收。这样就完成了记录的删除操作。同样，我们还实现了表的扫描操作。把一个表中的每条元组都显示出来。具体就是从头一条一条的取出元组，按照数据字典的解析，得到每个属性的具体值，显示在屏幕上。测试及分析：我们的main.c文件和anothermain.c是做具体的测试的程序，用了两个测试过程。主要一个是测试缓冲区的性能，另一个是测试记录的插入查找，表的扫描，即数据文件的组织和空闲空间管理。其中所用的机器参数为：CPU：IntelCore2DuoCPUE44002.00GHZ；RAM：1G；硬盘：SATA7200转；OS:Gentoo-kernel-2.6.25-r9首先实现一个计算时间的函数：voidcompute_time(void(*process)(void))；该函数要求传入一个函数指针，然后运行计算出该函数执行所需要的时间。就是在process()执行之前记录一个时间，执行之后记录一个时间，就能得到process()执行的粗略时间。1)main.c里面我们主要测试缓冲区的性能，我们的测试过程如下：首先在数据字典中建立一个表，然后用文件”all200000.txt”中将200,000条记录插入到数据中，同时根据key建立B+索引，然后显示该B+树索引结构，然后根据索引等值查询20,000条记录，插入5000条记录，删除5000条记录。我们的一次测试各过程所用的时间如下图１所示：图1：有缓冲区测试运行情况而没有缓冲区时所用的时间如下图2所示：图2：无缓冲区测试运行情况由图1和图2的比较我们可以看出，用了缓冲区，200,000条记录只需要870ms左右，而不用缓冲时要用2400ms左右，说明加上缓冲区后程序的性能还是提高了一大截的。2)anothermain.c里面我们主要是测试记录的插入和表的扫描，用Scan.txt文件里面1,000,000条记录进行插入，然后从数据库文件中扫描这整个表。下图3是插入百万条记录的运行时间，大约为53s左右，可以看出时间性能上还是可以接受的。图3:插入百万条记录的运行时间进行表扫描产生的结果如下图4所示。图4:表扫描测试结果心得与体会：1)这次实验，我们改进了B+树中的一些算法，主要是在一个树节点中查找某个键值的时候，我们这次采用了二分查找的方法，经过测试表明，时间性能上还是有很大的提升的。2)在进行缓冲区的设计时，开始我们设计的简单，缓冲区查找时，是把所有的缓冲区都搜索一遍，看看所需要的页是不是在缓冲区里面。而缓冲区淘汰的时候，也是搜索整个缓冲区，比较修改时间看哪个页是需要换出去的。当我们测试的时候发现，加上缓冲区后，时间性能反而下降了，这让我们开始思考我们的设计，经过查阅资料，发现缓冲区是不能这么简单的实现的。于是我们加了很多