#  extmem-c-database-query-processing

**Repository Path**: Hmount/extmem-c-database-query-processing

## Basic Information

- **Project Name**:  extmem-c-database-query-processing
- **Description**: 一个基于C语言ExtMem程序库的 数据库查询处理算法模拟实现
- **Primary Language**: Unknown
- **License**: Not specified
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 0
- **Created**: 2022-12-26
- **Last Updated**: 2022-12-27

## Categories & Tags

**Categories**: Uncategorized

**Tags**: C语言

## README

## 仓库介绍

这是一个基于C语言ExtMem程序库的 数据库查询处理算法模拟实现

## extmem-c介绍

ExtMem 程序库是一个专门为本实验编写的模拟外存磁盘块存储和存取的程
序库，由 C 语言开发。ExtMem 程序库的功能包括内存缓冲区管理、磁盘块读/
写，它提供了 1 个数据结构和 7 个 API 函数。

ExtMem 程序库已预先建立了关系 R 和 S 的物理存储。关系的物理存储形式为磁盘块序列 B1, B2, …, Bn，其中 Bi的最后 4 个字节存放 Bi+1的地址。

.\data 下的每个文件模拟一个磁盘块。R 和 S 的每个元组的大小均为 8
个字节。每个磁盘块大小为 64 个字节，可存放 7 个元组和 1 个后继磁盘块地址。
初始化缓冲区块的大小为 64 个字节，缓冲区大小设置为 64*8+8=520 个字节。其中 8 个字节为标志位，表示每个块是否被占用。这样，每块可存放 7 个元组和 1 个后继磁盘块地址，缓冲区内可最多存放 8 个块

## 仓库架构

```shell
.
├── bin     
├── data        # 磁盘块模拟文件目录   
├── extmem.c    
├── extmem.h
├── obj
├── main        # 查询算法实现主函数
└── test.c      # extmem-c代码示例
```

## 运行方式

+ 建议直接使用命令行 编译运行

```shell
gcc extmem.c main.c -o main.out && ./main.out  
```

+ 或使用codeblock打开目录下的extmem.cbp文件运行


## 查询处理算法实现

+ 基于线性搜索的关系选择算法


基于ExtMem程序库，使用C语言实现线性搜索算法，选出S.C=128的元组，记录IO读写次数，并将选择结果存放在磁盘上。（模拟实现 select S.C, S.D from S where S.C = 128）


+ 两阶段多路归并排序算法（TPMMS）

利用内存缓冲区将关系R和S分别排序，并将排序后的结果存放在磁盘上。

+ 基于索引的关系选择算法

利用（2）中的排序结果为关系R或S分别建立索引文件，利用索引文件选出S.C=128的元组，并将选择结果存放在磁盘上。记录IO读写次数，与（1）中的结果对比。（模拟实现 select S.C, S.D from S where S.C = 128 ）

+ 基于排序的连接操作算法

对关系S和R计算S.C连接R.A ，并统计连接次数，将连接结果存放在磁盘上。 （模拟实现 select S.C, S.D, R.A, R.B from S inner join R on S.C = R.A）


+ 基于排序的集合交操作算法

实现集合操作算法交，将结果存放在磁盘上，并统计交操作后的元组个数。