????????在緩沖池管理器中，FetchPage 和 NewPage 函數返回已經鎖定的頁面指針。這個鎖定機制確保頁面在沒有任何讀取和寫入時不會被驅逐。為了表示頁面在內存中不再需要，程序員必須手動調用 UnpinPage。

????????然而，如果程序員忘記調用 UnpinPage，頁面將永遠不會被驅逐出緩沖池。由于緩沖池實際上只有較少的幀，這將導致更多的頁面在磁盤和內存之間交換。這樣不僅會影響性能，而且這個 bug 很難被發現。

????????您將實現 BasicPageGuard 類，它存儲指向 BufferPoolManager 和 Page 對象的指針。一個頁面保護器確保一旦超出作用域，就會調用 UnpinPage 來解除鎖定頁面。請注意，它仍然應該提供一個供程序員手動解除鎖定頁面的方法。

????????由于 BasicPageGuard 隱藏了底層的頁面指針，它還可以提供只讀/寫數據的 API，這些 API 在編譯時進行檢查，確保正確設置 is_dirty 標志。

????????在這個和后續項目中，多個線程將會讀取和寫入相同的頁面，因此需要使用讀寫鎖來確保數據的正確性。請注意，在 Page 類中，已經為此目的提供了相關的鎖方法。類似于解除鎖定頁面，程序員可能會忘記在使用后解除鎖定。為了解決這個問題，您將實現 ReadPageGuard 和 WritePageGuard，它們會在作用域結束時自動解除頁面的鎖定。

????????由于在2024-fall的project1分析過了類似的，故實現這塊不在贅述。說實話我個人還是更喜歡2023f版的，這個版本的對PageGuard進行拆分得恰到好處。先是給出BasicPageGuard讓我們對PageGuard的作用有個具體的理解，再Basic的基礎上可以進一步升級為ReadPageGuard(下面簡寫為RPG)和WritePageGuard(簡寫為WPG)。這一套流程看下來2024f版對PageGuard的拆分程度太高了，上來就要求實現RPG和WPG，理解起來的難度要大不少。

????????接下來具體分析關于如何使用PageGuard。我相信很多人可能會對As和AsMut的用法有所疑惑。但無論是RPG還是WPG，其As與AsMut都是調用BasicPG的函數。我們只要理解透徹下面四個函數那對于PageGuard的使用也就是手到擒來了。

????????可以發現，GetData()與As()是配套的，而GetDataMut()和AsMut()也是配套的。而且GetDataMut這個函數中，修改了is_dirty_位，這說明一旦我們選擇調用AsMut，那最好是真的對page的內容進行了修改，自然也只有WPG才能調用AsMut的。

????????那什么時候調用RPG與WPG的情況也就呼之欲出了。只要需要修改page時，才需要調用WPG。如果只是讀取page，那調用RPG就可以了。但是！如果你懶得思考要不要修改page那直接調用WPG也不是不行，就是會多造成disk IO降低吞吐率。如果不清楚是否需要修改page，保險起見可以直接調用WPG。

 1.   auto GetData() -> const char * { return page_->GetData(); }2.  3.   template <class T>4.   auto As() -> const T * {5.     return reinterpret_cast<const T *>(GetData());6.   }7.  8.   auto GetDataMut() -> char * {9.     is_dirty_ = true;
10.     return page_->GetData();
11.   }
12.  
13.   template <class T>
14.   auto AsMut() -> T * {
15.     return reinterpret_cast<T *>(GetDataMut());
16.   }
17.  

Task #2 - Extendible Hash Table Pages

實驗說明分析

哈希表頭頁面（Hash Table Header Page）

頭頁面位于基于磁盤的可擴展哈希表的第一層，并且每個哈希表只有一個頭頁面。它存儲指向目錄頁面的邏輯子指針（作為頁面ID）。可以將其視為一個靜態的第一層目錄頁面。頭頁面具有以下字段：

請注意，盡管頁面的大小是物理限制，您應該使用 max_depth_ 來確定 directory_page_ids_ 數組的上限大小。

您必須通過僅修改其頭文件（src/include/storage/page/extendible_htable_header_page.h）和相應的源文件（src/storage/page/extendible_htable_header_page.cpp）來實現可擴展哈希表的頭頁面。

哈希表目錄頁面（Hash Table Directory Page）

目錄頁面位于基于磁盤的可擴展哈希表的第二層。每個目錄頁面存儲指向桶頁面的邏輯子指針（作為頁面ID），并包含用于處理桶映射以及動態擴展和收縮目錄的元數據。目錄頁面具有以下字段：

請注意，盡管頁面的大小是物理限制，您應該使用 max_depth_ 來確定 bucket_page_ids_ 數組的上限大小。

您必須通過僅修改其頭文件（src/include/storage/page/extendible_htable_directory_page.h）和相應的源文件（src/storage/page/extendible_htable_directory_page.cpp）來實現可擴展哈希表的目

錄頁面。

哈希表桶頁面（Hash Table Bucket Page）

桶頁面位于基于磁盤的可擴展哈希表的第三層。它們實際上存儲鍵值對。桶頁面具有以下字段：

請注意，盡管頁面的大小是物理限制，您應該使用 max_size_ 來確定 array_ 數組的鍵值對的上限大小。

您必須通過僅修改其頭文件（src/include/storage/page/extendible_htable_bucket_page.h）和相應的源文件（src/storage/page/extendible_htable_bucket_page.cpp）來實現可擴展哈希表的桶頁面。

重要說明：

每個可擴展哈希表的頭/目錄/桶頁面對應于通過緩沖池獲取的內存頁面的內容（即 data_ 部分）。每當您讀取或寫入頁面時，必須先從緩沖池中獲取頁面（使用其唯一的 page_id），然后將其重新解釋為相應的類型，在讀取或寫入后解鎖該頁面。我們強烈建議您利用在任務1中實現的 PageGuard API 來實現這一目標。

舉例說明可擴展哈希的插入流程

接下來直接舉個例子來解釋可擴展哈希表的具體實現過程：

初始Global_Depth=0，每個Bucket的Local_Depth=0，Bucket的max_size_=2。假設我們需要插入0 1 2 3 4 5 6 7 8 。

咳咳，又到了展示我精湛畫圖功力的時候了。Show time！

①插入0，1。由于初始的Bucket空間大小足夠，可以直接插入到Bucket0中。紫色筆記表示depth，左側表示Directory，右側表示Buckets。

③接下來插入2，發現B0已經滿了，無法直接插入。

1. 所以B0先嘗試local_depth++來進行桶分裂，但是由于此時local_depth已經等于global_detph了，所以loc_d自增失敗，需要glo_d先自增。此時glo_d=1
2. Loc_d++，即loc_d=1，自增成功可以進行桶分裂。原桶與新桶(brother)的loc_d都是1
3. 將原Bucket的元素進行重映射，即遍歷B0的所有元素，進行key&loc_depth_mask將元素分配到原桶和新桶中。

如下圖。0&1=0，1&1=1。所以0依然放在原桶中，1重新放在下標為1的新桶中。

• 重新嘗試插入2。通過2&global_depth_mask即10&1=0來把2放入B0中。

③插入3。通過3&global_depth_mask即11&1=1來把3放入B1中。

④插入4。4&global_depth_mask即100&1=0，發現B0已經滿了，故準備進行桶分裂。

1. 所以B0先嘗試local_depth++來進行桶分裂，但是由于此時local_depth已經等于global_detph了，所以loc_d自增失敗，需要glo_d先自增。此時glo_d=2
2. Loc_d++，即loc_d=2，自增成功可以進行桶分裂。原桶與新桶(brother)的loc_d都是2
3. 將原Bucket的元素進行重映射，即遍歷B0的所有元素，進行key&loc_depth_mask將元素分配到原桶和新桶中。

如下圖。0&11=00，10&11=10。所以0依然放在原桶B0中，2重新放在下標為2的新桶B10中。

• 重新插入4。4&global_depth_mask即100&11=00，所以把4插入到B0中

⑤插入5，5& global_depth_mask即101&11=01，發現B1這個桶已經滿了，準備桶分裂

1. Glo_d > loc_d，loc_d++成功，故桶B1可以直接分裂，得到新桶B11
2. 將原桶B1的元素進行重映射(key&local_depth_mask)分配到B01和B11中
3. 重新嘗試插入5，5& global_depth_mask即101&11=01，插入B01成功。如果插入失敗繼續嘗試桶分裂。

⑥插入6，6& global_depth_mask即110&11=10，成功插入到B10中

⑦插入7，7& global_depth_mask即111&11=11，成功插入到B11中

⑧插入8,8& global_depth_mask即1000&11=00，發現桶B00已經滿了，嘗試進行桶分裂

1. 所以B00先嘗試local_depth++來進行桶分裂，但是由于此時local_depth已經等于global_detph了，所以loc_d自增失敗，需要glo_d先自增。此時glo_d=3
2. Loc_d++，即loc_d=2，自增成功可以進行桶分裂。原桶與新桶(brother)的loc_d都是3
3. 將原Bucket的元素進行重映射，即遍歷B0的所有元素，進行key&loc_depth_mask將元素分配到原桶和新桶中。
4. 重新嘗試插入8，8& global_depth_mask即1000&111=000插入成功。如果插入失敗繼續嘗試桶分裂。

最后可擴展哈希表如下:

其實這個例子中，應該用page_id來標記唯一的桶，為了方便理解我就直接用下標來標識每個Bucket。

通過上述例子，我們可以總結可擴展哈希表的插入流程

1. 嘗試插入key。進行key&global_depth_mask從而找到對應的Bucket下標。當前Bucket不滿，直接插入成功，return。如果失敗進行步驟2
2. Bucket滿了。
   1. 當前global_depth > local_depth，此Bucket進行local_depth++成功，可以直接進行桶分裂。進行步驟3
   2. 當前global_depth =local_depth，此Bucket進行local_depth++失敗，不可以可以直接進行桶分裂。進行Global_depth++，所以此Bucket可以進行local_depth++，桶分裂成功。進行步驟3
3. 重映射。桶分裂成功后，遍歷原Bucket，對其中的每個元素elem進行elem&local_depth_mask，從而將原Bucket的元素分配到原桶和新桶中。重新進行步驟1