精选_毕业设计_基于C++的数据库可扩容哈希_完整源码

# 基于C++的数据库可扩容哈希 # 一、项目介绍 主要涉及可扩展哈希在数据库中的应用。 读入由 tpc-h 生成的 lineitem.tbl，以 L_ORDERKEY 属性作为键值将记录放入合适的哈希桶内。读入测试文件 testinput.in 内的数据，数据中包含多个需要查询的键值。将通过键值查询得到的所有记录都输出到 testoutput.out 文件中。算法实现分为两大部分，第一部分是建立索引，第二部分是查询。建立索引是将输入的每一条记录根据指定的键值放入合适的哈希桶内，当哈希桶已满时，需要进行分裂。查询是根据输入的键值返回具有相同键值的记录，返回的记录可能有不止一条。 # 二、项目环境 - 系统：Windows 8.1 专业版 64 位 - 处理器：Intel® Core(TM) i3 CPU M 350 @ 2.27GHz 2.27 GHz - 内存：2 GB 金士顿 DDR3 1333MHZ - 硬盘：希捷 ST9320 320GB 7200 转/分 - 语言：C++ - 编辑器：Visual Studio 2013 # 三、项目架构 本项目共有7 个文件： - main.cpp：主文件，程序的入口 - Manager.h (.cpp)：主控程序，实现功能的主体 - Buffer.h (.cpp)：缓存池，管理内存中各缓存页 - Index.h (.cpp)：目录页，存储哈希值和桶号的对应关系 - Page.h (.cpp)：页的基本类，实现一个页的基本功能 - Function.h (.cpp)：项目中要用到的通用函数，如取哈希值，取键值等 - option.h：程序的如最大使用页数，哈希方式等参数的定义文件 无论最大使用页数和哈希方式，项目运行时目录页占用 1 页，读写文件缓冲用占用一页，其他页都用来存储记录桶。 # 四、主要数据结构 ## 4.1 基本页  每个 Page 页在内存中的分布如下：  其中蓝色背景的为 contents 的内容。记录的具体内容从 contents 的头向尾扩展，对应的记录信息如长度，偏移值等从 contents 的尾向头扩展。需要写入或写出时将 Tong 强制转换为 char\*类型，按长度为 8192 进行存储或读取。 ## 4.2 缓冲池  每个缓冲池有一个Page\*的数组，用来存储各Page页的指针。pageId数组用来存储每个Page对应的pageId。ref\_bit, pin\_count数组分别存储各page的时钟标志和pin标记（用于时钟算法），dirty数组标志各page的修改状态，以确定换出时是否需要写回硬盘。 ## 4.3 目录页  size 表示目录页的总大小，包括在硬盘的部分。globalDepth 表示全局深度，start 表示目录当前在内存部分的头下标，pageId 表示以 start + (数组下标)为哈希值的桶的 pageId。 目录总的结构为：  # 五、主要算法 ## 5.1 低位哈希算法 ### 5.1.1 哈希方法 直接将 key 值截取低 globalDepth 位。比如 13 二进制为 1101，则当全局深度为 1 时返回 1， 全局深度为 2 时返回 1，全局深度为 3 时返回 5， 全局深度大于等于 4 时返回值都为 13。 程序中使用的方法是 key 值对 1 左移 globalDepth 位后的值取余：key % (1 << depth) ### 5.1.2 桶分裂算法 假设原来桶中的记录哈希值为 hashKey，则分裂后桶中的记录的哈希值可能为 hashKey 或者 1 << localDepth + hashKey，即原来的 hashKey 最高位前补 0 或 1。所以桶分裂后桶中的记录会根据记录的 key 值的哈希判断是留在旧桶还是移动到哈希值为 1<< localDepth + hashKey 的桶中。另外由于采取的是变长记录，删除掉一条记录后需要对之后的所有记录进行移动，所以旧桶对移出的记录不立即删除，而是将其长度置为-1，等桶分裂完成后再一次性将旧桶中所有长度为-1 的记录删除。 ```c++ void Buffer::spiltPage 当桶中存在下一条记录时循环： 计算该条记录的哈希值并与当前桶的哈希值进行比较 两者相同则进行下一次循环 两者不同则将该记录插入新桶中，并将该记录在当前桶的长度置为-1对旧桶进行更新操作 ``` ```c++ void Page::adjustPage 当桶中存在下一条记录时取该条记录进行循环得到该条记录的长度，判断其是否为-1 是，则继续循环 否，则取在其前面的距离最远一条长度为-1的记录，覆盖为该条记录更新桶的记录数和可用空间偏移 ``` #### 5.1.2.1 目录维护 桶分裂时需要对目录进行相应的维护，这里分两种情况： **localDepth < globalDepth** 这时需要将目录中新的哈希值所对应的桶号改为新桶桶号，同时如果需要的话，还要把另外一些关联的哈希值的对应桶号也改为新桶桶号。比如当前全局深度为 7，一个局部深度为 5，哈希值为 00110 的桶要进行分裂，这时不仅要将哈希值 01 00110 对应的桶更改为新桶桶号，还要将哈希值 11 00110 对应桶号做相同更改。 ```c++ void Manager::insert Value = 0 循环 Offset = value << (localDepth + 1) Hash = oldHash + (1 << localDepth) + offset 当得到的哈希值超出允许位数时退出循环 设置hash对应的桶号为新桶号 Value++ ``` **localDepth == globalDepth** 这时仅需要将目录翻倍后将哈希值为 oldHash + 1 << globalDepth 对应的桶号更改为新桶的桶号即可。 ## 5.2 高位哈希算法 ### 5.2.1 哈希方法 从第 23 位开始从高到低将 key 值截取 globalDepth 位。比如 2816 二进制为 0000 0000 0000 1011 0000 0000，则当全局深度小于等于 12 时都返回 0， 全局深度为 13 时返回 1，全局深度为 14 时返回 4， 全局深度为 15 时返回值为 5 等等。 程序中使用的方法是 key 值右移 23-globalDepth 位后与 007fffff(16)取与的结果： ```c++ (key ≫ (23 − globalDepth) ) & 007 ``` ### 5.2.2 桶分裂算法 假设原来桶中的记录哈希值为 hashKey，则分裂后桶中的记录的哈希值可能为 hashKey << 1 或者(hashKey << 1) + 1，即原来的 hashKey 的两倍或者两倍加一。这里不会将旧桶中的记录分到两个新桶，而是将旧桶对应的哈希值翻倍，之后再像低位扩展一样，根据旧桶中的记录的哈希值进行判断，哈希值恰好是原哈希值两倍的记录留在旧桶，其他移往新桶，并在全部记录都移动好后再对旧桶进行整理。 #### 5.2.2.1 目录维护 桶分裂时需要对目录进行相应的维护，这里也分两种情况： **localDepth < globalDepth** 这里跟低位扩展一样，不仅需要将新桶对应的哈希值更新，还需要对关联的哈希桶的哈希值进行更新。与低位扩展不同的是，高位扩展是在最低位后补 0 或 1。比如当前全局深度为 7，一个局部深度为 5，哈希值为 00110 的桶要进行分裂，这时不仅要将哈希值 00110 10 对应的桶更改为新桶桶号，还要将哈希值 00110 11 对应桶号做相同更改。 ```c++ void Manager::insert start = localHash << (globalDepth - localDepth) size = 1 << (globalDepth - localDepth - 1) for (int j = size; j < (size << 1);j++) 设置start + j 对应的桶号为新桶号 ``` **localDepth == globalDepth** 这时仅需要将目录翻倍后将哈希值为 (oldHash << 1) + 1 对应的桶号更改为新桶的桶号即可。 ## 5.3 时钟算法 每个桶都有一个 pin 标志位和 ref 标志位。Pin 表示该页不可被换出，ref 表示当前页的时钟标志。 ```c++ int Buffer::choseByClock 从 curr