[HIT-DB-Lab3] 数据库的多路归并算法及其实现

HIT战德臣老师的数据库lab3, 目的是用代码实现一个两阶段多路归并算法, 处理数据, 具体要求如下

先看看ppt上有关内容:

两趟多路归并算法其实不难理解,

如果你的内存足够大, 你可以把所有的元素装进内存再排序, 这样就是一趟排序算法

但是当内存不够的时候,就需要有两趟排序算法

• 第一趟: 你就要先把所有元组分成若干个子集(每个子集可以完全装进内存), 再把各个子集排好序后写回去

• 第二趟: 把排好序的若干子集, 分别取出他们的最前面若干元素放入内存(输入缓冲区), 然后对么每个子集最前面的元素进行比较(一个子集最前面的元素一定是这个子集最小的元素), 这些正在比较的元素称为排序缓冲区, 最小的元素放入输出缓冲区中, 然后一次比较后面的元素, 容易得知每次进入输出缓冲区的元素是整个数组中最小的元素

我先用的Java实现, 然后发现速度实在太慢了, 100w条数据, 跑了十几分钟, 然后改用C, 颇费周折, 几个破指针差点把我弄死......不过还是按时完成了

具体代码详见我的github: HIT-Database-Labs/实验3 at main · 1191000814/HIT-Database-Labs · GitHub2022年春哈工大数据库系统实验(战德臣老师). Contribute to 1191000814/HIT-Database-Labs development by creating an account on GitHub.https://github.com/1191000814/HIT-Database-Labs/tree/main/%E5%AE%9E%E9%AA%8C3