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 需要注意的地方

1. WritePageGuard和ReadPageGuard的移动赋值操作，需要先drop，再赋值新的guard。
2. 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. 全局深度大于局部深度
   只进行桶分裂

2. 全局深度等于局部深度
   目录扩展+桶分裂

这里只对第二种情况分析(其实也只比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,返回索引0for (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 删除

删除成功的时候需要检查 桶 是否空了，空的话，需要进行合并操作。

写这个函数的时候，我遇到了合并上的疑惑：

1. project 2中第三条提到了递归合并，也即如果合并后仍未空，需要继续合并。
2. 合并后directory索引的维护问题，一开始我以为只需要修改原来空桶的索引指向非空的桶。

所以我尝试看看网上的文章，看到两点注意：

1. 当前桶和对应的split image桶，有一个为空就需要合并。
2. 更新directory索引，需要将所有指向空桶的索引修改(这个借助完成的UpdateDirectoryMapping实现)

看了两眼感觉和自己的思路不一样，懒得看了，还是自己写吧。
所以删除的流程应该是：
获取当前桶对应的split 桶(如果存在的话)，

1. 当前桶或者split桶有一个为空，就需要删除空桶
2. 更新索引。

// 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);

3. CanShrink缩减目录
4. 重新获取页，为了递归删除，需要更新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中构造函数的实现。
另外非类型模板参数：
允许将具体的值（而不是类型）传递给模板。这种参数通常是整型、指针、枚举等，能够在编译期提供具体的值，而不是运行时。