B 樹與 B + 樹解析與實現

一、磁盤存儲優化的核心邏輯

在大規模數據處理場景中，磁盤 I/O 效率是性能瓶頸的核心。磁盤訪問具有以下特性：

隨機訪問成本高：磁頭尋道時間（Seek Time）可達毫秒級，相比內存訪問（納秒級）慢百萬倍。
順序訪問效率高：連續扇區的讀取速度比隨機讀取快 10 倍以上。
頁存儲機制：磁盤以頁（Page，通常 4KB/8KB/16KB）為單位讀寫數據，單次 I/O 操作讀取完整一頁。

B 樹與 B + 樹通過以下設計優化磁盤訪問：

矮胖樹結構：每個節點存儲多個鍵值，減少樹的高度（通常 3-4 層即可支撐百萬級數據）。
順序訪問支持：B + 樹的葉子節點通過鏈表連接，實現高效范圍查詢。
節點對齊頁大小：節點大小等于磁盤頁，單次 I/O 讀取完整節點，減少碎片。

二、B 樹：平衡多路搜索樹的基石

2.1 核心結構與規則

B 樹是一種自平衡的多路搜索樹，其核心規則如下：

節點容量：每個節點最多有m個子節點（m為階數），最少有?m/2?個子節點。
鍵值分布：節點內鍵值有序排列，左子樹鍵值 < 當前鍵值 < 右子樹鍵值。
平衡條件：所有葉子節點位于同一層，根節點至少有 2 個子節點（除非樹高為 1）。
節點分裂與合并：插入 / 刪除操作導致節點溢出或不足時，通過分裂 / 合并保持平衡。

示例結構（m=3）

2.2 關鍵操作詳解

插入操作（以 m=3 為例）

查找插入位置：從根節點開始，逐層向下找到目標葉子節點。
處理節點溢出：
- 若葉子節點已滿（鍵值數 = m-1），分裂為左右兩部分，中間鍵值提升至父節點。
- 若父節點溢出，遞歸向上分裂，可能導致樹高增加。

刪除操作（以 m=3 為例）

查找刪除位置：定位到包含目標鍵值的節點。
處理節點不足：
- 若刪除后節點鍵值數 <?m/2?-1，從兄弟節點借鍵或與兄弟節點合并。
- 若父節點鍵值數不足，遞歸向上處理。

2.3 代碼實現

#include <vector>
#include <algorithm>
#include <stdexcept>// B樹節點類模板
template <typename T, int M>  // M為B樹的階數
class BTreeNode {
public:std::vector<T> keys;                  // 存儲鍵值std::vector<BTreeNode<T, M>*> children;  // 存儲子節點指針bool is_leaf;                         // 是否為葉子節點// 構造函數BTreeNode(bool leaf = true) : is_leaf(leaf) {}
};// B樹類模板
template <typename T, int M>
class BTree {
private:BTreeNode<T, M>* root;  // 根節點指針// 分裂子節點：將full_child分裂為兩個節點void splitChild(BTreeNode<T, M>* parent, int child_idx) {BTreeNode<T, M>* full_child = parent->children[child_idx];BTreeNode<T, M>* new_node = new BTreeNode<T, M>(full_child->is_leaf);int mid = M / 2;// 復制中間鍵右側的鍵到新節點for (int i = mid + 1; i < M; ++i) {new_node->keys.push_back(full_child->keys[i]);}full_child->keys.resize(mid);  // 保留中間鍵左側的鍵// 如果不是葉子節點，復制子節點指針if (!full_child->is_leaf) {for (int i = mid + 1; i <= M; ++i) {new_node->children.push_back(full_child->children[i]);}full_child->children.resize(mid + 1);}// 將新節點插入到父節點的子節點列表parent->children.insert(parent->children.begin() + child_idx + 1, new_node);// 將中間鍵提升到父節點parent->keys.insert(parent->keys.begin() + child_idx, full_child->keys[mid]);}// 插入非滿節點void insertNonFull(BTreeNode<T, M>* node, const T& key) {int i = node->keys.size() - 1;// 如果是葉子節點，直接插入鍵if (node->is_leaf) {node->keys.push_back(key);// 保持鍵的有序性while (i >= 0 && key < node->keys[i]) {node->keys[i + 1] = node->keys[i];--i;}node->keys[i + 1] = key;} else {// 找到插入的子節點位置while (i >= 0 && key < node->keys[i]) {--i;}int child_idx = i + 1;// 檢查子節點是否已滿if (node->children[child_idx]->keys.size() == M - 1) {splitChild(node, child_idx);  // 分裂子節點// 確定插入到分裂后的哪個子節點if (key > node->keys[child_idx]) {child_idx++;}}insertNonFull(node->children[child_idx], key);  // 遞歸插入}}public:// 構造函數BTree() {root = new BTreeNode<T, M>();}// 插入鍵值void insert(const T& key) {BTreeNode<T, M>* r = root;// 如果根節點已滿，分裂根節點if (r->keys.size() == M - 1) {BTreeNode<T, M>* new_root = new BTreeNode<T, M>(false);root = new_root;new_root->children.push_back(r);  // 舊根成為新根的子節點splitChild(new_root, 0);          // 分裂舊根insertNonFull(new_root, key);     // 插入鍵到新根} else {insertNonFull(r, key);  // 直接插入到非滿的根節點}}// 查找鍵值（返回是否存在）bool search(const T& key) {return searchHelper(root, key);}private:// 查找輔助函數bool searchHelper(BTreeNode<T, M>* node, const T& key) {int i = 0;// 找到第一個大于等于key的位置while (i < node->keys.size() && key > node->keys[i]) {++i;}// 如果找到匹配的鍵，返回trueif (i < node->keys.size() && key == node->keys[i]) {return true;}// 如果是葉子節點且未找到，返回falseif (node->is_leaf) {return false;}// 遞歸查找子節點return searchHelper(node->children[i], key);}
};

三、B + 樹：數據庫索引的黃金標準

3.1 結構增強與優化

B + 樹在 B 樹基礎上進行了以下改進：

數據全在葉子節點：內部節點僅存儲鍵值和子節點指針，不存儲實際數據。
葉子節點鏈表：所有葉子節點通過雙向鏈表連接，支持高效范圍查詢。
更高的扇出：內部節點鍵值數更多，樹高更低（通常比 B 樹矮 1-2 層）。

3.2 核心操作優化

插入操作（以 m=3 為例）

分裂策略：僅分裂葉子節點，中間鍵值提升至父節點，內部節點鍵值數可能超過m-1。
鏈表維護：分裂后更新相鄰葉子節點的前后指針。

刪除操作（以 m=3 為例）

合并策略：若葉子節點鍵值數不足，優先從兄弟節點借鍵；若兄弟節點也不足，則合并并更新父節點指針。
鏈表調整：合并后重新連接鏈表指針。

3.3 代碼實現

#include <vector>
#include <algorithm>
#include <stdexcept>// B+樹節點類模板
template <typename T, int M>  // M為B+樹的階數
class BPlusTreeNode {
public:std::vector<T> keys;                       // 存儲鍵值std::vector<BPlusTreeNode<T, M>*> children; // 存儲子節點指針BPlusTreeNode<T, M>* next;                 // 葉子節點的鏈表指針（用于范圍查詢）bool is_leaf;                              // 是否為葉子節點// 構造函數BPlusTreeNode(bool leaf = true) : is_leaf(leaf), next(nullptr) {}
};// B+樹類模板
template <typename T, int M>
class BPlusTree {
private:BPlusTreeNode<T, M>* root;    // 根節點指針BPlusTreeNode<T, M>* leaf_head;  // 葉子節點鏈表頭（便于范圍查詢）// 分裂子節點void splitChild(BPlusTreeNode<T, M>* parent, int child_idx) {BPlusTreeNode<T, M>* full_child = parent->children[child_idx];BPlusTreeNode<T, M>* new_node = new BPlusTreeNode<T, M>(full_child->is_leaf);int mid = (M - 1) / 2;  // B+樹分裂點（保留中間鍵在原節點）// 復制中間鍵右側的鍵到新節點for (int i = mid + 1; i < M; ++i) {new_node->keys.push_back(full_child->keys[i]);}full_child->keys.resize(mid + 1);  // 保留中間鍵// 如果是葉子節點，處理鏈表指針if (full_child->is_leaf) {new_node->next = full_child->next;full_child->next = new_node;} else {// 非葉子節點復制子節點指針for (int i = mid + 1; i <= M; ++i) {new_node->children.push_back(full_child->children[i]);}full_child->children.resize(mid + 1);}// 插入新節點到父節點parent->children.insert(parent->children.begin() + child_idx + 1, new_node);// 父節點插入分裂點的鍵（B+樹父節點存儲子節點的最小鍵）parent->keys.insert(parent->keys.begin() + child_idx, full_child->keys[mid]);}// 插入非滿節點void insertNonFull(BPlusTreeNode<T, M>* node, const T& key) {int i = node->keys.size() - 1;// 葉子節點直接插入if (node->is_leaf) {node->keys.push_back(key);// 保持有序while (i >= 0 && key < node->keys[i]) {node->keys[i + 1] = node->keys[i];--i;}node->keys[i + 1] = key;} else {// 找到子節點位置while (i >= 0 && key < node->keys[i]) {--i;}int child_idx = i + 1;// 檢查子節點是否已滿if (node->children[child_idx]->keys.size() == M) {splitChild(node, child_idx);if (key > node->keys[child_idx]) {child_idx++;}}insertNonFull(node->children[child_idx], key);}}public:// 構造函數BPlusTree() {root = new BPlusTreeNode<T, M>();leaf_head = root;  // 初始葉子頭為根節點}// 插入鍵值void insert(const T& key) {BPlusTreeNode<T, M>* r = root;// 根節點已滿，分裂根節點if (r->keys.size() == M) {BPlusTreeNode<T, M>* new_root = new BPlusTreeNode<T, M>(false);root = new_root;new_root->children.push_back(r);splitChild(new_root, 0);insertNonFull(new_root, key);} else {insertNonFull(r, key);}// 更新葉子頭（如果根節點分裂后葉子頭變化）if (!root->is_leaf) {BPlusTreeNode<T, M>* temp = root;while (!temp->is_leaf) {temp = temp->children[0];}leaf_head = temp;}}// 范圍查詢：返回[start, end]之間的所有鍵std::vector<T> rangeQuery(const T& start, const T& end) {std::vector<T> result;BPlusTreeNode<T, M>* current = leaf_head;// 找到起始葉子節點while (current != nullptr) {auto it = std::lower_bound(current->keys.begin(), current->keys.end(), start);if (it != current->keys.end()) {break;}current = current->next;}// 遍歷葉子節點鏈表收集結果while (current != nullptr) {for (const T& key : current->keys) {if (key > end) {return result;}if (key >= start) {result.push_back(key);}}current = current->next;}return result;}// 點查詢：返回是否存在bool search(const T& key) {BPlusTreeNode<T, M>* current = root;while (current != nullptr) {int i = 0;while (i < current->keys.size() && key > current->keys[i]) {++i;}// 葉子節點檢查是否存在if (current->is_leaf) {return (i < current->keys.size() && current->keys[i] == key);}// 非葉子節點繼續向下查找current = current->children[i];}return false;}
};

四、B 樹與 B + 樹深度對比

特性	B 樹	B + 樹
數據存儲	所有節點均可存儲數據	僅葉子節點存儲數據
樹高	較高（相同數據量下比 B + 樹高 1-2 層）	較低（內部節點鍵值更多）
查詢效率	點查詢可能更快（非葉子節點命中）	點查詢穩定（必須到葉子節點）
范圍查詢	需中序遍歷，隨機 I/O 多	順序遍歷鏈表，順序 I/O 高效
磁盤利用率	內部節點存儲數據，空間利用率低	內部節點緊湊，空間利用率高
應用場景	內存數據庫、小規模索引	關系型數據庫、文件系統