Overview
Project1 主要与 Bustub 的 storage manager 相关，分为三个部分：
- Extendible Hash Table
- LRU-K Replacer
- Buffer Pool Manager Instance
Buffer Pool Manager 向系统提供获取 page 的接口，系统通过 page_id 向 Buffer Pool Manager 索要对应的 page，而不关心该 page 具体存放位置。也就是说，系统并不关心（也不可见）获取这个 page 的过程（从 disk 或 memory 上读取），也不关心 page 可能发生的在 disk 和 memory 间的移动。这些内部的操作都交由 Buffer Pool Manager 完成。
Extendible Hash Table 和 LRU-K Replacer 是 Buffer Pool Manager 内部的组件。Extendible Hash Table 用于实现 page table，将 page id 映射为 Buffer Pool 中 frame 的 frame id。 LRU-K Replacer 完成 Buffer Pool 空间不足时 frame 的移除工作。
Disk Manager 已经为我们提供，是实际在 disk 上读写数据的接口。
我们实现结构的类图如下：
Task #1 - Extendible Hash Table
实现 ExtendibleHashTable 类、Bucket 类，涉及文件：
- src/container/hash/extdible_hash_table.cpp
- src/include/Container/hash/extdible_hash_table.h
要求实现一个 extendible hash table，内部不能使用 build-in hash table，如 unordered_map。需要实现对扩容哈希表的支持，而不用实现对缩小/压缩哈希表的支持。该 hash table 在 buffer pool manager 中负责存储 buffer pool 中 page id 到 frame id 的映射关系。
Extendible Hash Table 由一个 directory + 多个 bucket 组成。
- directory: 存放指向 bucket 的指针，是一个数组。用于寻找 key 对应 value 所在的 bucket。
- bucket: 存放 value，是一个链表。一个 bucket 可以至多存放指定数量的 value。
Extendible Hash Table 维护两个值 ——
- global_depth：记录定位到 bucket 指针数组 directory (slot array) 的具体位置，需要取 key 的二进制的多少位
- 各 bucket 的 local_depth：记录定位到该 bucket 需要取 key 的二进制的多少位
Extendible Hash Table
标签：Buffer,frame,list,page,Project,lru,id,Pool,size From： https://www.cnblogs.com/angelia-wang/p/17262376.html