### 可拓展哈希方法详解及其实现
#### 一、引言
在数据库系统中，索引技术是提高查询效率的关键。其中一种高效的索引技术是可拓展哈希（Extendible Hashing），它能够在数据量不断增长的情况下，通过动态调整索引来保持较高的查询性能。本文将基于给定的描述和部分内容，详细介绍可拓展哈希的基本概念、实现细节以及具体的实现步骤。
#### 二、可拓展哈希简介
可拓展哈希是一种动态的索引结构，适用于大型数据集的管理。它通过分层哈希表来组织数据，可以随着数据量的增长自动进行调整。主要特点包括：
- **动态调整**：能够随着数据的增加或减少而自动调整索引结构。
- **高效查询**：通过分层哈希表，能够快速定位到目标数据所在的位置。
- **局部性**：查询操作通常只需要访问索引的一部分，从而减少了I/O操作。
#### 三、实现细节
##### 3.1 实验环境与要求
- **实验平台**：支持Linux或Windows操作系统。
- **编程语言**：使用C/C++编写程序，不允许使用STL库。
- **实现算法**：依据课程材料中的说明实现可拓展哈希算法。
##### 3.2 数据集与键值
- **数据集**：使用tpc-h工具生成的`lineitem.tbl`文件，共有6001215条记录。
- **键值选择**：以`L_ORDERKEY`属性作为键值，用于构建哈希索引。
##### 3.3 索引构建与查询
- **索引构建**：对于每条记录，根据其键值将其放入合适的哈希桶内。当哈希桶已满时，需要进行分裂处理。
- **查询处理**：根据给定的键值返回所有匹配的记录。查询结果需按`L_PARTKEY`属性排序。
##### 3.4 内存限制与I/O操作
- **内存限制**：
- 当内存容量为8页（每页8KB）时，需要考虑内存限制对索引和数据的影响。
- 当内存容量为128页时，同样关注I/O操作次数、目录大小等方面的变化。
- **I/O操作**：由于内存容量有限，数据和索引无法完全加载到内存中，因此频繁的磁盘读写操作不可避免。
##### 3.5 具体实现
- **哈希桶存储**：采用`<键，数据记录>`的方式存储哈希桶内的数据。
- **页面存储**：使用变长记录的方式存储哈希桶数据。
- **页面置换**：采用时钟页面置换算法。
- **哈希扩展方式**：实现从低位和从高位进行扩展的哈希，比较两者在桶分裂、数据分配、I/O次数等方面的差异。
- **索引输出**：将建立好的哈希索引输出到`hashindex.out`文件中。
##### 3.6 输入输出说明
- **输入文件**：
- `lineitem.tbl`：通过tpc-h的dbgen程序生成，共6001215条记录。
- `testinput.in`：第一行为查询数量，之后每行为一个整数键值。
- **输出文件**：
- `testoutput.out`：每行一条记录，按`L_PARTKEY`属性排序。
- `hashindex.out`：格式自定义。
##### 3.7 提交内容
- **文件压缩**：将所有提交内容打包成压缩文件，命名格式为“组号_组长姓名_实现平台”。
- **提交内容**：
- `README`：说明提交内容和小组信息。
- 源代码：放入“src”文件夹内。
- 可执行程序：放入“bin”文件夹内，包含四个不同参数配置的可执行文件。
- 实验报告：中文或英文，以PDF格式提交。
#### 四、结论
通过对可拓展哈希的理解与实践，我们不仅掌握了这种索引结构的核心原理，还深入了解了其实现过程中面临的挑战与解决策略。尤其是在内存有限的情况下，如何优化I/O操作，提高查询效率等问题显得尤为重要。此外，对比不同哈希扩展方式下的性能差异，也有助于我们在实际场景中做出更合理的选择。
