数据库课程设计 1： 可扩展哈希

《数据库课程设计 1： 可扩展哈希》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、数据库课程设计1:可扩展哈希1.实验平台Linux或者Windows2.编程语言仅能使用C/C++，不允许使用STL。3.实现算法可扩展哈希，具体算法请见课件中的第5至12张。算法实现分为两大部分，第一部分是建立索引，第二部分是查询。建立索引是将输入的每一条记录根据指定的键值放入合适的哈希桶内，当哈希桶已满时，需要进行分裂。查询是根据输入的键值返回具有相同键值的记录，返回的记录可能有不止一条。4.实现过程(1)读入由tpc-h生成的lineitem.tbl，以L_ORDERKEY属性作为键值将记录放入合适的哈希桶内。(2)读入测试文件te

2、stinput.in内的数据，数据中包含多个需要查询的键值，具体格式请见[6.数据输入输出说明]。(3)将通过键值查询得到的所有记录都输出到testoutput.out文件中，具体格式请见[6.数据输入输出说明]。5.实现细节(1)只能使用P个页，每个页的大小为8Kbytes，一个哈希桶的大小和一个页的大小相同。考虑以下两种情况：a)P=8（也就是整个内存中仅能使用8个页，这8个页用于存放索引和哈希桶的数据）b)P=128（也就是整个内存中仅能使用128个页，这128个页用于存放索引和哈希桶的数据）由于页的数量有所限制，lineitem.tbl的数据和对其建立的索引不可能都放在内存里

3、，所以频繁的文件读写(I/O)是不可避免的。请比较P=8和P=128两种情况下，I/O的次数、目录的大小、哈希桶的数量、查询的速度（每秒执行查询的数量）、I/O用时占查询总用时的比例等。(2)对于哈希桶内的数据，采用<键，数据记录>的方式进行存储。详细内容请参考课件中的第16、17张。(3)对于存储哈希桶数据的页面，使用变长记录的方式进行存储。关于变长记录，请参考课件中的第31张。(4)使用时钟页面算法进行页面置换，请参考中的第19张。(5)分别实现从低位和从高位进行扩展的哈

4、希。详细内容请参考课件中的第10张。比较这两种哈希方法，包括桶的分裂方式、桶分裂时桶内数据的分配方式、I/O的次数、目录的大小、桶的数量、查询的速度（每秒执行查询的数量）、I/O用时占查询总用时的比例等。(6)将建立的哈希索引输出到新的文件中，命名为hashindex.out，格式自定。(7)对于每个查询结果，请按照L_PARTKEY属性的值进行排序。16.数据输入输出说明将文件路径作为启动参数传入程序，例如执行ExtendibleHash.exe程序，执行命令为“ExtendibleHash.exeD:database”。该路径表示l

5、ineitem.tbl和testinput.in所在的文件路径，同时也表示testoutput.out和hashindex.out输出的文件路径。以下是对文件的格式进行说明，请严格按照文件格式进行输入输出。hashindex.out格式自定，因此不作说明。(1)lineitem.tbl通过tpc-h的dbgen程序生成，ScaleFactor设置为1，所以记录的数量一定是6001215。选择L_ORDERKEY属性作为键值建立哈希索引。(2)testinput.in数据第一行是n，表示查询数量。接下来的n行，每行分别是一个整数，表示要查询的键值。(3)testoutput.out对于

6、每一个查询，输出所有满足要求的记录，并且按照L_PARTKEY属性的值进行排序。每行一条记录。对于每个查询的结果，都以-1作为结束。以下是样例。lineitem.tbltestinput.intestoutput.out27.提交说明请将所有要提交的内容放入一个压缩文件内，命名格式为“组号_组长姓名_实现平台”，例如“01_张三_linux”。组号信息请向学委咨询。要提交的内容如下：(1)README写明所提交的内容和小组信息。小组信息包括组员学号、姓名、班级。(2)源代码放入”src”文件夹内。(3)可执行程序放入”bin”文件夹内。这里需要提交四个可执行程序。由于程序有两个参数，

7、一个是页的数量，一个是哈希的扩展方式，根据排列组合，有4种方案。根据方案中参数的不同分别命名为least_128,most_128,least_8,most_8。并附上README说明每个程序完成的功能和如何运行程序。(4)实验报告可用中文或英文写。实验报告必须为pdf格式，请以“组号_report”的方式命名，例如”01_report”。实验报告必须包含以下内容：a)实验环境、工具说明b)实验思路c)数据结构设计d)实验过程设计e)代码结构f)实验结果、