数据库课程 CMU15-445 2023 Fall Project-2 Extendible Hash Index
0 实验结果
tips:完成项目的前提不需要一定看视频
1 数据结构：扩展哈希
解释下这张图：
图中header的最大深度2，directory最大深度2，桶的容量2。
最开始的时候只有一个header。
插入第一个数据，假设这个数据对应的哈希值是00…100
header的索引使用的是哈希值的MSB，即高位，因为header深度2，所以直接取高两位，即0.
此时header[0]并没有指向的directory，所以需要先new page创建目录页面，创建出的目录页面，默认gd，即全局深度应该为0.
目录页面实际指向页面的索引个数：1 << gd，即默认1个索引，此时索引到的bucket id为非法页面，索引需要new page创建桶页面。
将哈希值00…100对应的键值对存入桶中，并更新header，directory，bucket之间的索引关系。
不断插入数据，将导致桶溢出，此时就需要进行分类，也即图中下面部分的情况。
需要注意的是，当从directory索引bucket的时候使用的是哈希值的LSB，而由几个位索引则由directory的gd决定。
2 任务要求
2.1 Read/Write Page Guards
需要实现 BasicPageGuard, ReadPageGuard, WritePageGuard 的移动构造函数，移动赋值操作，析构函数。
移动构造，移动赋值就是转移guard的所有权，但是移动赋值操作，需要释放本来的资源，接管传入的that指向。
2.1.1 需要注意的地方
- WritePageGuard和ReadPageGuard的移动赋值操作，需要先drop，再赋值新的guard。
- FetchPageRead和FetchPageWrite返回guard之前，一定要加读/写锁。
2.2 Extendible Hash Table Pages
在这个任务中需要实现header，directory，bucket页面的结构。
header索引directory使用的是MSB
directory索引bucket使用的是LSB
2.2.1 重点说一下directory page
// 注意：全局深度设置为0，本地深度设置为0
ExtendibleHTableDirectoryPage::Init
// 1. 插入时，桶满分裂,传入原桶索引,返回新桶索引
// 2. 删除时，获取当前桶索引分裂时产生的对称索引，用于检查一方是否为空桶
ExtendibleHTableDirectoryPage::GetSplitImageIndex
// 增加深度，需要拷贝一半，directory目录扩大一倍
ExtendibleHTableDirectoryPage::IncrGlobalDepth
// 什么时间可以缩减目录? directory目录大小内,全部满足ld < gd
ExtendibleHTableDirectoryPage::CanShrink()
2.3 Extendible Hashing Implementation
在这个任务中就需要使用 2.2 中准备好的API来实现DiskExtendibleHashTable的构造函数，读值，插入和删除。
2.3.1 插入
由第一部分：扩展哈希的介绍，相信对Insert的流程有一个了解。
插入时，如果directory页面不存在，需要先创建directory页面。
如果directory页面存在，需要根据全局深度gd个LSB位索引桶页面，如果桶满，需要进行分裂。
这里有两种情况：
- 全局深度大于局部深度
只进行桶分裂
- 全局深度等于局部深度
目录扩展+桶分裂
这里只对第二种情况分析(其实也只比1多一个操作)：
如果全局深度==局部深度，需要增加全局深度，如果全局深度已经最大，则表示扩展哈希已满。增加局部深度ld，分裂过程中对原桶存在的所有key重新分配桶。
存在一种情况： 全部的key又被分到同一个桶中了，此时仍然无法插入新key，所以，插入操作是一个while操作，如果扩展哈希未满，应该继续分裂，尝试插入。
产生的新桶，需要使用UpdateDirectoryMapping更新directory的下标指向新的page_id。
这里提供下实现：
template <typename K, typename V, typename KC>
void DiskExtendibleHashTable<K, V, KC>::UpdateDirectoryMapping(ExtendibleHTableDirectoryPage *directory,
uint32_t new_bucket_idx, page_id_t new_bucket_page_id,
uint32_t new_local_depth, uint32_t local_depth_mask) {
// throw NotImplementedException("DiskExtendibleHashTable is not implemented");
uint32_t val = 0; // 当gd为0,返回索引0
for (uint32_t i = 0; i < new_local_depth; i++) {
val <<= 1;
val |= 1;
}
uint32_t start_idx = new_bucket_idx & val;
for (uint32_t idx = start_idx; idx < directory->Size(); idx += (1 << new_local_depth)) {
directory->SetBucketPageId(idx, new_bucket_page_id);
directory->SetLocalDepth(idx, new_local_depth);
}
}
另外需要注意的是：不支持重复键插入，所以一定要先Lookup检查，不存在时再进入insert操作。
2.3.2 查询
查询是最简单的了，如果后面遇到bug，可以在这个函数中添加以下代码，进行调试。
使用./test/extendible_htable_test >> mylog.txt将log重定向，看下哪里不对劲。
directory_page->PrintDirectory();
bucket_page->PrintBucket();
2.3.3 删除
删除成功的时候需要检查 桶 是否空了，空的话，需要进行合并操作。
写这个函数的时候，我遇到了合并上的疑惑：
- project 2中第三条提到了递归合并，也即如果合并后仍未空，需要继续合并。
- 合并后directory索引的维护问题，一开始我以为只需要修改原来空桶的索引指向非空的桶。
所以我尝试看看网上的文章，看到两点注意：
- 当前桶和对应的split image桶，有一个为空就需要合并。
- 更新directory索引，需要将所有指向空桶的索引修改(这个借助完成的
UpdateDirectoryMapping实现)
看了两眼感觉和自己的思路不一样，懒得看了，还是自己写吧。
所以删除的流程应该是：
获取当前桶对应的split 桶(如果存在的话)，
- 当前桶或者split桶有一个为空，就需要删除空桶
- 更新索引。
// 1. 释放空桶
bucket_guard.Drop();
bpm_->DeletePage(bucket_page_id);
// 2. 更新directory_page
// 可能多个下标指向删除的桶 2^(gd-ld)
directory_page->DecrLocalDepth(split_idx);
UpdateDirectoryMapping(directory_page, bucket_idx, split_bucket_page_id,
directory_page->GetLocalDepth(split_idx), 0);
CanShrink缩减目录- 重新获取页，为了递归删除，需要更新
bucket_guard和split_bucket_guard
2.3.3.1 注意
注意后面为了并发控制使用FetchPageWrite时候，第4步，重新获取页，需要先drop页面进行解锁，否则重新获取页时候可能会发生死锁。
split_bucket_guard.Drop();
bucket_guard.Drop();
2.4 Concurrency Control
将前面获取页面的操作FetchPageBasic修改为FetchPageWrite或者FetchPageRead，并选择合适的时机drop解锁。
3 知识总结
在这一节中并没有用到新的知识。
这一节中比较有意思的是page_guard中构造函数的实现。