# DatabaseLab4

**Repository Path**: LoanCold/database-lab4

## Basic Information

- **Project Name**: DatabaseLab4
- **Description**: No description available
- **Primary Language**: Unknown
- **License**: Not specified
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 0
- **Created**: 2021-04-22
- **Last Updated**: 2021-05-05

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

#### 运行

项目根目录下运行下命令即可运行main.c对应的内容
> make run

运行test.c则使用该命令
> make test

#### 题目解析

每个磁盘块大小为64个字节，可存放7个元组和1个后继磁盘块地址。
每个元组占8个字节，每个字节都是char，需要atoi转成数字。因为值域限定，属性A与C占前两个字节，B和D占后四个字节。
R中包含16块 * 7 = 112个元组，S中包含32块 * 7 = 224个元组。

![image-20210422144522098](Readme.assets/image-20210422144522098.png)

#### 操作

硬盘中的数据只能被导入到buffer中。buffer只有八块。

![image-20210422224308602](Readme.assets/image-20210422224308602.png)

一定要小心，写入磁盘的块就被释放了，读取磁盘的块设置为占用

#### 问题一

将数据读一块进来，然后扫是否为1

关系s的数据是块17至块48.

结果放在49之后



#### 问题二

两阶段多路归并

总共有8个buf：

- 初始化时，分成子集合可以一次排序八个块，意味着S排序成两组，R成为4组
- 考虑一个输出块，最多进行七路归并，完全可以满足六组一次归并的要求。



初始化：用插入排序，但是要小心一个块中的最后一个元组不是有效数据，是指向下一块的指针。对于插入结果我们也这么做，不使用最后一个元组，这里我们直接指向下一个块。



归并：

- 找到最大值：找到后，movenext，如果next跨块则取下一块，若最后一块把当前块指针置零，之后不再参与比较。
- 存数据：满了就在末尾指向下一块，取另一块，然后存进去。
- 最大值路后移动：末尾了就指向下一块，最后一块了就将这一路的指针置零，不再参与归并排序。





#### 问题三

为S建立主索引：一个索引的元组为（C属性，该块的地址）。查找时：若值满足“小于前者大于等于后者”则从前者开始搜索，输出等于的，直到末尾或者是小于目的的值就结束。

考虑必须同时能够比较前者和后者两个元素，因此我们要用一个指针来存储前者，每次访问后者都进行比较。



#### 问题四

与问题二非常类似，将二路R和四路S放在一起归并排序。对每路R.A，都在S.C的四路中扫描一遍，找到满足连接条件的，就不找了，写入result。表面上看起来简单，但是实际上操作复杂，最关键的就是在遇到几路值相同的时候，不能简单的将对应路向前移动就能遍历成功。

还好这道题不要求两趟算法，而是sort merge join，那么直接使用第二问的结论，两路（一路S一路R，进行连接）。实际在这个基础之上还可以进一步的拓展成上述的多路，但是有难度，这里不考虑。

对于两路（一路R，一路S）的，就先这样，类似于快排双指针。以R为中心，对S先找到第一个小于等于R的值，不等于的话就移动S指针，S移动到小于等于R，等等以此移动。

如果中间匹配到了，那就进入特殊环节。



#### 问题五

交：和问题四非常相近，两路，以R为中心，找到第一个小于等于S的，然后判定元组是不是完全相等，是就写入结果。不管是不是想等S都要后移一个位置。

并：不等的时候直接合并，等于的时候才看是不是真的相等。

差：大体上一样，S不等就写，SR相等对R遍历，没有就加进去。

#### 重构

在块的读写过程中，产生了大量重复的大块代码块。