搜索
实验四SPJ算法一、实验内容：1.选择操作算法（TableScan;IndexScan）；2.投影操作算法；3.连接操作算法（嵌套循环连接；基于排序的等值连接；基于散列的等值连接；基于索引的连接）；二、实验要求：1.选择操作：i.无条件选择；ii.等值条件；iii.非等值条件；iv.范围条件；2.连接操作：i.卡氏积(排序连接和散列连接例外)；ii.等值条件；iii.非等值条件(排序连接和散列连接例外)；三、实验步骤：本实验代码实现使用的是C语言。1.iterator迭代器的设计：我们对一个表不管是进行选择还是投影还是连接操作，都需要得到这个表的一条一条的元组，为此我们需要设计一个迭代器来方便的取出表中的元组。下面是我们对迭代器的设计，在文件scantable.h中：structiterator{intextent;/*currentwhichextent*/intblk;/*inwhichblockofthecurextent*/charb[PAGE_SIZE];/*curpagecontentpoint*/intt;/*?thtupofthecurpage*/intlen;/*tuplen*/};structiteratoropen_iter(constchar*tbname);intgetnext_iter(structiterator*iter,char*rec);/*fetchnexttuple,storeinrec*/intclose_iter(structiterator*iter);由于我们对记录的存储是聚簇的，所以我们的迭代器是一次取出一个块，然后一条一条的抛出记录，这个块中的记录用完之后再读下一个块，直到读出了这个表中的所有的块，得到了表中的所有记录。在iterator结构中，extent,blk,t分别表示当前的区间，块，记录位置；b[PAGE_SIZE]存储了当前取出的块，len是记录的长度。open_iter()是打开一个迭代器，并进行初使化；close_iter()是关闭这个迭代器；getnext_iter()是得到下一条元组。具体的实现在scantable.c里面。2.SPJ结果的输出：在进行完选择和连接操作之后，得到的结果我们想返回给用户。我们实现了Oracle里里面SQL*plus界面里的返回结果的样式，即把结果表用字符界面显示出来。也在头文件scantable.h里面，如下所示：intprint_tuple(char*rec,structtable_def*td);intprint_tbhdr(structtable_def*td);print_tbhdr()是显示结果表的表头，print_tuple()是显示结果表里的所有记录。在实现上，因为我们的每一条记录都是以char[]存储在数据文件里面，所以这个函数就是从记录头里面得到记录的模式信息，然后按记录模式逐个解析这条元组，然后按一定的形式显示。3.内存查找结构的实现：由于在下面的实验（基于块的嵌套循环连接以及一些其它的一元操作）中要用到内存的查找结构：能在接近常量的时间内增加一个新元组，查找一个元组是否存在。所以我们需要实现一个这样的数据结构。这样的结构很多，像hash和平衡搜索树等等。我们选择了使用AVL树，也即平衡搜索树。因为我们觉得虽然时间性能上面AVL不如hash，但是在这个结构的管理上面，AVL还是有优势的。具体实现的接口如下(头文件avl.h中)：structBNode//definetypeofthenode{intnum;//numberofnodesintbf;//balance-factor(1,0,-1:thetreeisbalance)KeyTypekey;//keywordInfoTypedata;//storedatastructnode*lchild,*rchild;//leftchild,rightchildstructnode*same;//具有相同的key，但是其他信息不同};/*若平衡二叉树b中不存在与e相同的节点，则插入，并返回1；否则返回0**@b：在b指向的平衡二叉树中插入数据**@e：待插入的关键字**@taller：表示这颗树是否增高*/structBNode*InsertBT(structBNode*b,structRecorde,int*taller);/*@b：平衡二叉树据**@k：待查找的关键字找到节点后返回该节点*/structResult*SearchBT(structBNode*b,KeyTypek);/*回收二叉树的内存空间*/voidClearBT(structBNode*b);BNode是AVL树的结点的定义，每个结点里面保存了相应的key值和相应的元组数据和其它的一些控制信息（像左右孩子节点的指针）；InsertBT()函数实现了向AVL树中插入一条元组的功能；SearchBT()函数是返回AVL树中具有相应key值的所有元组；ClearBT()函数负责清理申请的内存空间。4.select:无条件选择的实现：所谓无条件选择，就是取出表中的所有记录。实现上很简单，用表扫描算法，一条一条的得到记录就可以了。因为我们已经实现了迭代器，所以就是从迭代器中得到每一条记录，把记录放到结果集里面。因为我们的数据库存储，在每一个索引上面都不是聚簇的，所以我们在进行全表扫描的时候并没有用索引扫描（因为当索引不是聚簇时，进行索引扫描的代价是很高的）。代码见下，在源文件select.c里面：inttot_sel(constchar*tbname){......print_tbhdr(td);structiteratoriter=open_iter(tbname);while(getnext_iter(&iter,rec)==0){print_tuple(rec,td);}close_iter(&iter);return0;}5.select:等值条件选择的实现：当选择条件是等值的情况时，当选择条件上面建了索引的时候，可以用索引进行选择操作。即在索引里面查找条件里的键值，得到记录里面满足条件的所有记录的地址，然后从这些地址里面取出所对应的各条记录。我们不需要扫描整个表。代码见下，在源文件select.c里面：intequal_sel(intkey,constchar*tbname){if((res=btree_search(key,table,&nid,&idx))!=-1){print_tbhdr(tdef);//对每一条满足条件的记录for(;idxbnode-d;idx++){print_tuple(rec,tdef);}}return0;}对于不等值查询，我们没有别的办法，只能进行全表扫描，然后对每一条记录进行条件判定，若它满足相应的不等值条件，就把它放到结果集里面。6.select:范围条件选择的实现：对于范围查询，当我们在查找条件上面建立了B+树索引的时候，可以用索引来进行。首先从索引里面找到范围里面最左边的值的记录，若没有的话，找到比该值大的最小的key值的记录。然后在索引树上面向右逐个取出记录对应的地址，从数据里面得到相应的记录，直到索引树上的键值不在这个范围内时停止。对应这个查找过程，我们需要一个有效的索引扫描算法，为此我们修改了一下B+树索引(btree.h)的一点实现，修改了一下里面查找的实现，使它能像迭代器一样一个个地返回当前位置右边的记录地址。然后范围查询的实现如下，也在select.c里面：intrange_sel(intleft,intright,constchar*tbname){......print_tbhdr(tdef);btree_search(left,table,&nid,&idx);while(nid!=-1){//对每一个满足条件的值for(;idxbnode-d;idx++){if(bnode-key[idx]right)//不满足条件，跳出break;print_tuple(rec,tdef);}}return0;}7.product:笛卡尔积实现：对于product操作，我们没有其它的办法，只能对两个表的任何两条记录分别进行连接。所以实现上很简单：取出第一个表的每一条记录，分别与第二个表中记录做product。具体实现在join.c里面，如下：intproduct(constchar*tb1,constchar*tb2){print_tbhdr(td);itertb1=open_iter(tb1);//对tb1里的每一条记录while(getnext_iter(&itertb1,rec1)==0){itertb2=open_iter(tb2);//对tb2里的每一条记录while(getnext_iter(&itertb2,rec2)==0){/*outputrec1xrec2*/print_tuple(rec,td);}close_iter(&itertb2);}close_iter(&itertb1);return0;}两个表做product的时候，对CPU时间和I/O时间的花费非常大，而且不能够进行优化，所以实际对数据库表进行操作的时候应该避免这方面的操作。8.join:嵌套循环连接实现：对于最简单的嵌套循环连接，我们实现了两种算法：一种是基于元组的，一种是基于块的。下面分别介绍。(1)基于元组的嵌套循环连接：即取出第一个表的每一个元组，然后取出第二个表的每一个元组，判断第二个表的每一个元组是不是能和这第一个表的元组连接，若能连接，则把结果放入结果表中。实现上很简单（join.c），见下。intnest_tuple_join(constchar*tb1,constchar*tb2){print_tbhdr(td);itertb1=open_iter(tb1);while(getnext_iter(&itertb1,rec1)==0){itertb2=open_iter(tb2);while(getnext_iter(&itertb2,rec2)==0){/*outputrec1|x|rec2*/intkey1=*(int*)(rec1+TUPHDR_SIZE);intkey2=*(int*)(rec2+TUPHDR_SIZE);if(key1==key2){/*canjoin*/print_tuple(rec,td);}}close_iter(&itertb2);}close_iter(&itertb1);return0;}这种方法的好处是能对任何大小的表进行连接操作；但是缺陷也很明显，这种算法需要的I/O代价是非常非常大的。需要对它进行一下改进，就是下面的基于块的嵌套循环连接。(2)基于块的嵌套循环连接:我们对基于元组的嵌套循环连接进行一下改进：每次将尽可能多的第一个表中的元组放在内存，然后对它们建立一个内存查找结构，即我们之前建立的AVL树；然后依次取出第二个表中的元组，根据这个元组连接属性上的值查询我们建立的第一个表的内存查找结构，若能找出能和这个元组连接的第一个表中的元组，则把连接结果加入到结果表中。不断重复这样的步骤，直到我们取出了第一个表中的所有元组为止。很明显，当第一个表能一次都放进内存时，这个算法就成了等值连接的一遍算法。基于块的嵌套循环算法的具体的实现如下：也在源文件join.c中：intnest_blk_join(constchar*tb1,constchar*tb2){BNode*avl=NULL;print_tbhdr(td);itertb1=open_iter(tb1);//建立内存查找结构while(getnext_iter(&itertb1,rec1)==0){avl=InsertBT(avl,e,&taller);}itertb2=open_iter(tb2);while(getnext_iter(&itertb2,rec2)==0){//在内存查找结构中查找能进行连接的元