外部归并排序算法,使用B+树，分块整理等

先让我们看看原题的三个任务介绍： Task 1: Sorting the LINEITEM table by External Merge Sort Consider two cases: 1) using 5 buffer pages in memory for the external merge sort; 2) using 129 buffer pages in memory for the external merge sort. In the implementation, each buffer page occupies 8K bytes. The ORDERKEY attribute of the LINEITEM table is assumed to be the sort key in the external merge sort. Please report the number of passes and also the running time of the external merge sort in each case. Task 2: Organizing the sorted LINEITEM table into disk pages Please use the page format for storing variable-length records to organize the LINEITEM table sorted in Task 1. In the implementation, each disk page occupies 1K bytes. For each page we maintain a directory of slots, with a <record offset, record length> pair per slot. Both “record offset” and “record length” are 4 bytes wide. Task 3: Building a B-Tree over LINEITEM disk pages by Bulk Loading. Please use bulk loading to build a B-Tree over the disk pages of the LINEITEM table, which are generated in Task 2. The ORDERKEY attribute of the LINEITEM table is used as the (search) key for building the B-Tree. In the B-Tree, each internal node corresponds to a page of 1K bytes, both key and pointer are 4 bytes wide. Please report the running time of the bulk loading. A query interface is required for checking the B-Tree. For a reasonable ORDERKEY value, please print out all the pages visited along the path to find the corresponding record. Please also report the running time of the search.