EXTMEM-URSQL

• HITSZ，数据库实验4-查询处理算法的模拟实现
• 项目的IO和堆内存(但是实际上那部分内存开在栈里...总之就是不能MALLOC)请求要通过本部邹兆年老师的EXTMEM模块实现

环境

Visual Studio 2019

64位编译

程序是GBK编码的，windows传统艺能，懒得改了

原理

索引

给定key是会重复的。故采用一级索引，索引键-值第一次出现的块的地址

TPMMS排序后，300+段内的块都是连续的、可以用枚举器读的。

显然，一级索引占用的空间不会超过数据本身。

模块说明

extmem

邹兆年老师的extmem库。功能是对64B大小的数据块操作。

我对其进行了一点修改，替换了不安全的fopen和sscanf等函数，并改为使用64位地址(裆燃，后来发现这没卵用，但也没改回来。实际上程序因为数据格式原因最多只支持0-9999).

如果数据格式更改，地址空间可以进行扩增。

infrastructure

一些和项目基本上无关的通用常量定义。优化写C的体验。

ursql-consts

项目相关的常量、通用函数和数据结构定义

block

因为下发的原始数据二进制文件拿字符串存数组(宁可真是个小机灵鬼流汗😅)，例如45存成'4''5''\0''\0'，因此给数据的比较和处理带来极大不便。故block模块中提供了一套类型安全的中间件适配层来替代extmem中的操作。除了此模块，其他模块基本没有引用extmem中的内容。

除了读、写、创建和释放操作，还提供了基于选择排序的块内/块间内排序。 之所以不写快排是因为懒(反正数据量并不大)。

enumerator

枚举器。又叫迭代器，封装了一个数据结构和一些常见操作。可以基于64B数据块完成一系列链式数据储存的完整遍历。支持挂起。占用一个block。

polymeric_enumerator

聚合枚举器。可以把若干个的枚举器结果聚合，安装一定规则按序操作。对于程序中使用的min_of_enumerators聚合器，配合已经有序的迭代器可以实现归并排序(TPMMS的第二阶段)。

data_writer

数据写入器。可以流式写入连续地若干个数据单元(item_t)到链式数据储存。占用一个block。

ursql_io

复制通用的字符串输出。

relation

实现关系操作，被外部模块(main.c)调用的大部分函数来自这里

ii_stage_operation

基于排序的两端扫描算法。他们的第一阶段都一样，调用block中的API，完成强排序，使用ii_stage_operation的前半段完成；第二阶段则分别使用XXXX_stage_ii实现，这些第二阶段都实现alg_stage_ii这一函数指针封装的接口。

强排序是指集合内的元素具有全序关系，任意两个不相等的元素都有大小之分(如， (20,20)<(21,20),(20,20)>(20,21))。

其中，交并差的第二阶段结构很相似，程序是基于两个输入(聚合枚举器)的情况来决定运行情况的，很有意思。

具体地，两个输入共有6个情况：

1. 两输入均截止
2. 左输入截止
3. 右输入截止
4. 左输入较大
5. 两输入相等

具体情况读者可自行观察代码。

ursql

URSQL所有功能模块的最外层封装。