CMU-15445(6)——PROJECT#2-BPlusTree-Task#1

PROJECT#2-B+Tree

在 PROJECT#2 中，我們需要實現一個B plus Tree，用過 MySQL 的同學肯定對它不陌生，B+Tree是實現高效數據檢索的核心組件，其內部節點的作用是引導搜索過程，而實際的數據項則存于葉子節點中。該索引結構能夠實現快速的數據檢索，無需對數據庫表中的每一行數據進行掃描，可實現快速隨機查找以及對有序記錄的高效掃描。

舉個例子，如果我們要用某個給定的 id 來檢索某個貨物的記錄，沒有索引結構的情況下，我們只能從第一條記錄開始遍歷每個貨物的記錄，直到找到某個ID和我們給定的ID一致的記錄，時間復雜度是O(N)。常見的索引結構有二叉樹、紅黑樹、哈希表和B+Tree，而如果我們維護了一個以ID為KEY的索引結構，我們可以通過這個索引結構查詢這個ID對應的貨物所在的位置，然后直接從這個位置讀取數據，B+Tree能保證 O (log n) 時間復雜度的檢索操作。

在著手項目開發前，建議先系統學習 B + 樹數據結構的核心原理，預先夯實知識基礎。

B+Tree

DB 的數據一般保存在磁盤上，這樣的好處是持久化，但也有很大的缺點：讀寫特別慢。

磁盤讀寫的最小單位是扇區，扇區的大小只有 512B 大小，操作系統一次會讀寫多個扇區，所以操作系統的最小讀寫單位是塊(Block)。Linux 中的塊（頁）大小為 4KB ，也就是一次磁盤 I/0 操作會直接讀寫8個扇區。

由于數據庫的索引是保存到磁盤上的，因此當我們通過索引查找某行數據的時候，就需要先從磁盤讀取索引到內存，再通過索引從磁盤中找到某行數據，然后讀入到內存，也就是說查詢過程中會發生多次磁盤//O，而磁盤 I/0 次數越多，所消耗的時間也就越大（如果沒有索引結構，那么就需要從頭開始將每一行數據的索引從磁盤讀到內存和目標索引進行對比，I/O次數會特別多）。

所以，我們希望索引的數據結構能在盡可能少的磁盤的 1/0 操作中完成查詢工作，因為磁盤 I/0 操作越少，所消耗的時間也就越小。

因此，一個合格的數據結構需要滿足以下要求：

能在盡可能少的磁盤的 /O 操作中完成查詢工作；
要能高效地查詢某一個記錄，也要能高效地執行范圍查找;

如果可以將索引按順序（增序或降序），那么可以通過二分查找來降低查詢時間復雜度到O(logN)，進一步優化到二分查找樹、自平衡二叉樹、B樹…，這一部分內容可參考文章：

>>>為什么 MySQL 采用 B+ 樹作為索引？ | 小林coding<<<

索引結構的迭代優化總結起來其實就是以下內容：

在數據結構的索引場景中，若將索引存儲于數組結構，線性查找的時間復雜度為 O (N)，而采用二分查找可將復雜度降至 O (logN)。盡管數組的線性存儲方式實現簡單，但插入操作需移動后續所有元素，導致 O (N) 級的時間開銷。由此引出二叉樹結構，其通過指針鏈接節點實現非連續存儲，兼具二分查找特性，但當二叉搜索樹退化為單支樹（如全右子樹或全左子樹）時，時間復雜度會退化為 O (N)。

為解決此類平衡性問題，AVL 樹與紅黑樹等平衡二叉搜索樹應運而生。然而，無論何種平衡樹結構，其樹高仍隨數據量呈 O (logN) 增長，這直接導致磁盤 I/O 次數隨樹高增加而顯著上升。B 樹的出現通過提升節點扇出能力（單個節點可包含多個子節點）有效降低樹高，但傳統 B 樹節點存儲索引與數據記錄的復合信息，當用戶數據記錄尺寸遠大于索引鍵時，會引發兩大問題：

非目標節點的數據記錄加載會消耗額外 I/O 資源；
無效數據占用內存空間，降低緩存命中率。

B+樹其實就是B樹的升級，MySQL 中索引的數據結構就是采用了 B+ 樹，B+ 樹結構如下圖：

在這里插入圖片描述

圖片來源：https://xiaolincoding.com/mysql/index/why_index_chose_bpuls_tree.html#%E4%BB%80%E4%B9%88%E6%98%AF-b-%E6%A0%91-2

B+ 樹與 B 樹差異的點，主要是以下這幾點：

葉子節點（最底部的節點）才會存放實際數據（索引+記錄），非葉子節點只會存放索引；
所有索引都會在葉子節點出現，葉子節點之間構成一個有序鏈表；
非葉子節點的索引也會同時存在在子節點中，并且是在子節點中所有索引的最大（或最小）。
非葉子節點中有多少個子節點，就有多少個索引；

如下圖所示（課程ppt示例圖）：
在這里插入圖片描述

所有數據均保存至葉子結點 Leaf Nodes；內部節點 Inner Node 僅僅充當控制查找記錄的媒介，并不代表數據本身，所有的內部結點元素都同時存在于子結點中，是子節點元素中是最大（或最小）元素。

如上圖，5 是其子結點的最大值， 9 是其子結點的最小值，所有的數據 [1,3,6,7,9,13...] 均保存至葉子結點中，而根結點 [5,9]均不是數據本身，只是充當控制查找記錄的媒介。

總而言之，一個完整的 B+ 樹由根節點、內部節點、葉子節點三部分組成。每個節點均有鍵（key）和值（value）組成，區別在于內部節點的值指向子節點的指針（通常是頁 ID，用于導航到下一層節點），而葉節點的值指向實際數據記錄的引用（通常是 RID，用于定位存儲在磁盤上的完整元組）。每個節點通常對應數據庫緩沖池中的一個物理頁面，通過唯一的頁 ID標識。

內部節點的結構如下圖所示：

每個內部節 Inner Nodes 點都由 [P,K] 組成，P指向子樹根結點的指針；K 表示關鍵字值，也就是索引。
內部節點的關鍵字值有如下規律：
$K?<K?<…<K_{c-1}$

在這里插入圖片描述

葉子節點的結構如下圖所示：

葉子節點的值指向磁盤中的某塊數據地址；
存在指針 P_next 指向下一個葉子節點，方便遍歷查詢。

在這里插入圖片描述

關于 B+ 樹的插入、刪除可參考文章：B+樹看這一篇就夠了（B+樹查找、插入、刪除全上） - 知乎

參考：為什么 MySQL 采用 B+ 樹作為索引？ | 小林coding

TASK#1-B+Tree Pages

了解完 B+ 樹的基礎知識后，便可以著手實現 TASK#1。

我們現在很清楚一個完整的 B+ 樹由根節點、內部節點和葉子節點三部分組成，其實三者都是同一類型，只不過根據位置不同，不同節點存儲的數據對象不同。

在 Project 中，B+ 樹所有節點都以 B+Tree Page 的形式存在，根據節點類型不同，又分為 B+Tree Internal Page 和 B+Tree Leaf Page，二者均繼承自 B+Tree Page，區別只在于二者存儲的數據類型不同：

B+Tree Internal Page 的 Value 為子樹根節點的索引；
B+Tree Leaf Page 的 Value 為元組 RID。

本節的目的就是實現以下三個頁：

B+Tree Page
B+Tree Internal Page
B+Tree Leaf Page

Base-Tree

需要修改的文件：

src/include/storage/page/b_plus_tree_page.h
src/storage/page/b_plus_tree_page.cpp

文件中的抽象類 BPlusTreePage 是B+樹所有節點類型的公共抽象，包含了內部節點和葉節點共享的核心屬性和方法，我們實現的函數多數是 Get/Set，因此比較簡單。

因為內部節點和葉子節點都是 BPlusTreePage 的派生，因此每個 B + 樹頁面的起始位置都包含了三元素：PageType (4) | CurrentSize (4) | MaxSize (4)，分別代表：

PageType：4 字節，標識頁面類型
CurrentSize：4 字節，當前頁面中的鍵值對數量
MaxSize：4 字節，頁面可容納的最大鍵值對數量

一共 12B 的不包含鍵值對的信息被稱為 HEADER，分別對應 BPlusTreePage 的成員變量：

private:// Member variables, attributes that both internal and leaf page shareIndexPageType page_type_ __attribute__((__unused__));// Number of key & value pairs in a pageint size_ __attribute__((__unused__));// Max number of key & value pairs in a pageint max_size_ __attribute__((__unused__));

其中，IndexPageType 是定義的枚舉類：

enum class IndexPageType { INVALID_INDEX_PAGE = 0, LEAF_PAGE, INTERNAL_PAGE };

INVALID_INDEX_PAGE = 0：無效頁面（初始狀態或已釋放的頁面）
LEAF_PAGE：葉子節點頁面（存儲實際數據記錄的引用）
INTERNAL_PAGE：內部節點頁面（存儲索引鍵和子節點指針）

此外，盡管這里 B+ 樹的所有節點均以 B+Tree Page 的形式存在，但和 lab1 的 Page 是有本質上的區別，BPlusTreePage 實際對應BPM 中 Page 對象的 data_ 存儲區域。因此在讀取或寫入節點時，首先需要通過 BPM.CheckedReadPage(page_id) 獲取受保護可讀的 std::optional<ReadPageGuard> 對象（獲取可寫對象也如此），再將其 data_ 部分 reinterpret_cast 為 BPlusTreePage，最后根據對應的 page_type_ 強轉為 Internal/Leaf page，然后在讀取或寫入后取消固定該頁面。具體數據排布如下圖所示：

在這里插入圖片描述

實現整體比較簡單，需要注意的只有GetMinSize() ，對于內部節點和葉子節點，最小大小有不同的計算方式。

最大鍵值對數量為 N 時，節點的最少鍵值對數量存在三種情況：

根節點：
根節點是葉節點時，內部至少需要 1 個鍵值對，這個很好理解，空樹插入首個元素時，根節點必須至少有 1 個鍵值對（如初始插入場景）
根節點是內部節點時，內部至少需要 2 個鍵值對，因為內部節點需指向至少 2 個子節點（左子樹和右子樹），因此至少需要 1 個有效鍵（實際用于索引查詢的鍵值對） + 1 個哨兵鍵（內部節點最左側的無效鍵）

內部節點：節點插入數據之后可能溢出，這時需要進行分裂操作，為了簡化分裂代碼的編寫，內部節點和根節點會留出一個鍵值對的位置作為哨兵，實際最大鍵值對數量為 N?1，加上最左側的無效鍵，最小鍵值對數量為 ?(N?2)/2?+1；
(N?2)：減去哨兵鍵和 1 個分裂鍵
加 1 是因為哨兵鍵必須保留在左子樹

葉節點：最小鍵值對數量為 ?(N?1)/2?，因為葉節點無需哨兵鍵，最大有效鍵值對為 N?1（留出 1 個空位用于分裂）

Internal Page

需要修改的文件：

src/include/storage/page/b_plus_tree_internal_page.h
src/storage/page/b_plus_tree_internal_page.cpp

B+ 樹和 B 樹最大的區別就是 B+ 樹的內部節點存儲的是索引信息而不是數據，且 m 個 key 對應 m+1 個 child，這種設計使得每個鍵成為兩個相鄰子樹的分隔符，如下圖所示：

在這里插入圖片描述

由于 child 的數量不等于 key 的數量，因此將第一個鍵設置為無效（key_array_[0] = KeyType()），并且查找方法應始終從第二個鍵開始，簡單來說就是犧牲空間獲取效率，舉個例子說明：

在這里插入圖片描述

假如存在 key_array_ = [5，10，20，30]，且 key_array_[0] 有效，則 child 的含義變為：

P0指向<5的鍵（但B+樹根節點的最小鍵是整個 B + 樹中所有鍵的最小值，在左子樹中不存在比5小的鍵，因此這個區間為空）
P1指向[5,10)的鍵
P2指向[10,20)的鍵
P3指向[20,30)的鍵
還需額外的子指針指向≥30的鍵（但數組已無空間）

因為子指針page_id_array_[i]指向的子樹包含鍵值范圍：[key_array_[i], key_array_[i+1])，若key_array_[0]存儲有效鍵，查找最左側子樹時需特殊處理，因為不存在小于 key_array_[0] 的區間，所以左子樹只能通過判斷是否小于 key_array_[1] ：

// 假設key_array_[0]有效，查找最左側子樹的代碼
if (key < key_array_[1]) {return page_id_array_[0]; 
}

正常我們希望的判斷邏輯為：

// 實際查找邏輯（從key_array_[1]開始）
int index = 1;
while (index < GetSize() && key >= key_array_[index]) {index++;
}
return page_id_array_[index-1];  // 無需特殊處理最左側子樹

P0指向的區間永遠為空，浪費一個子指針位置，且4 個鍵需要 5 個子指針，但數組只有 4 個位置。因此有必要將 key_array_[0] 無效。

在這里插入圖片描述

key_array_[0] 無效時， child 的含義變為：

子指針P0指向<10的所有鍵
子指針P1指向[10,20)的所有鍵
子指針P2指向[20,30)的所有鍵
子指針P3指向≥30的所有鍵

特別注意，宏 INTERNAL_PAGE_SLOT_CNT 表示 B + 樹內部頁面最多能存儲的鍵值對數量

\#define INTERNAL_PAGE_SLOT_CNT \
((BUSTUB_PAGE_SIZE - INTERNAL_PAGE_HEADER_SIZE) / ((int)(sizeof(KeyType) + sizeof(ValueType))))  // NOLINT

一個頁通常為 4KB，HEADER占據 12B，最大鍵對值數量取決于鍵值對占用空間，假如 sizeof(int) + sizeof(int) = 4 + 4 = 8 字節，那么一個頁能存儲的鍵值對數量為 (4096 - 12) / (4 + 4) = 510.5 → 向下取整為 510。

因此，每個內部頁面實際最多存儲 510 個鍵和 511 個子指針（因首個鍵無效），理論上可容納 510 個有效鍵，實際最大有效鍵數量為 509（因需預留一個位置用于分裂）；最小有效鍵數量 = ?510/2? - 1 = 255 - 1 = 254，當頁面鍵數量降至 254 以下時，可能觸發與兄弟節點的合并，當頁面鍵數量達到 510 時，插入操作將觸發分裂。

內部節點頁的結構如下圖所示，它比父類多了一個 array 數組成員，用于存放 key | page_id 鍵值對，其中 page_id 是子節點的頁 id：

在這里插入圖片描述