B+樹高效實現與優化技巧

B樹的定義

一顆M階B樹T，滿足以下條件

  1. 每個結點至多擁有M課子樹
  2. 根結點至少擁有兩顆子樹
  3. 除了根結點以外，其余每個分支結點至少擁有M/2課子樹
  4. 所有的葉結點都在同一層上
  5. 有k棵子樹的分支結點則存在k-1個關鍵字，關鍵字按照遞增順序進行排序
  6. 關鍵字數量滿足 ceil( M/2 ) - 1 <= n <= M-1

B樹與B+樹的區別

在實際磁盤存儲中往往選用的都是b+樹

b+樹相較于b樹的優點

  1. 關鍵字不保存數據，只用來索引，所有數據都保存在葉子結點（b樹是每個關鍵字都保存數據）
  2. b+樹的葉子結點是帶有指針的，且葉結點本身按關鍵字從小到大順序連接（適用于范圍查詢）
  3. b+樹的中間結點不保存數據，所以磁盤頁能容納更多結點元素，更“矮胖”

C++ B+樹算法

構建B+樹的基本結構

B+樹是一種多路平衡搜索樹，常用于數據庫和文件系統索引。以下是一個簡單的B+樹節點結構定義：

template <typename Key, typename Value>
class BPlusNode {
public:bool is_leaf;std::vector<Key> keys;std::vector<Value> values;  // Only for leaf nodesstd::vector<BPlusNode*> children;  // Only for non-leaf nodesBPlusNode* next;  // Pointer to next leaf node (for range queries)
};

插入操作的實現

插入操作需要處理節點分裂和鍵的重新分配。以下是插入邏輯的核心代碼片段：

template <typename Key, typename Value>
void BPlusTree<Key, Value>::insert(const Key& key, const Value& value) {if (root == nullptr) {root = new BPlusNode<Key, Value>(true);root->keys.push_back(key);root->values.push_back(value);return;}BPlusNode<Key, Value>* leaf = find_leaf(root, key);leaf->keys.push_back(key);leaf->values.push_back(value);std::sort(leaf->keys.begin(), leaf->keys.end());if (leaf->keys.size() > order) {split_leaf(leaf);}
}

刪除操作的實現

刪除操作需要處理節點合并和鍵的重新分配。以下是刪除邏輯的核心代碼片段：

template <typename Key, typename Value>
void BPlusTree<Key, Value>::remove(const Key& key) {BPlusNode<Key, Value>* leaf = find_leaf(root, key);auto it = std::find(leaf->keys.begin(), leaf->keys.end(), key);if (it == leaf->keys.end()) return;size_t index = it - leaf->keys.begin();leaf->keys.erase(leaf->keys.begin() + index);leaf->values.erase(leaf->values.begin() + index);if (leaf != root && leaf->keys.size() < (order + 1) / 2) {handle_underflow(leaf);}
}

范圍查詢的實現

B+樹支持高效的范圍查詢，以下是實現代碼片段：

template <typename Key, typename Value>
std::vector<Value> BPlusTree<Key, Value>::range_query(const Key& start, const Key& end) {std::vector<Value> result;BPlusNode<Key, Value>* leaf = find_leaf(root, start);while (leaf != nullptr) {for (size_t i = 0; i < leaf->keys.size(); ++i) {if (leaf->keys[i] >= start && leaf->keys[i] <= end) {result.push_back(leaf->values[i]);}if (leaf->keys[i] > end) return result;}leaf = leaf->next;}return result;
}

完整B+樹類的定義

以下是一個完整的B+樹類定義，包含構造函數和析構函數：

template <typename Key, typename Value>
class BPlusTree {
private:int order;BPlusNode<Key, Value>* root;
public:BPlusTree(int order) : order(order), root(nullptr) {}~BPlusTree() { clear(root); }void insert(const Key& key, const Value& value);void remove(const Key& key);Value search(const Key& key);std::vector<Value> range_query(const Key& start, const Key& end);
private:BPlusNode<Key, Value>* find_leaf(BPlusNode<Key, Value>* node, const Key& key);void split_leaf(BPlusNode<Key, Value>* leaf);void handle_underflow(BPlusNode<Key, Value>* node);void clear(BPlusNode<Key, Value>* node);
};

測試B+樹的插入和查詢

以下是一個簡單的測試用例，驗證B+樹的插入和查詢功能：

void test_b_plus_tree() {BPlusTree<int, std::string> tree(3);tree.insert(1, "Alice");tree.insert(2, "Bob");tree.insert(3, "Charlie");assert(tree.search(2) == "Bob");auto results = tree.range_query(1, 3);assert(results.size() == 3);
}

處理節點分裂的邏輯

當葉子節點的鍵數量超過階數時，需要進行分裂：

template <typename Key, typename Value>
void BPlusTree<Key, Value>::split_leaf(BPlusNode<Key, Value>* leaf) {BPlusNode<Key, Value>* new_leaf = new BPlusNode<Key, Value>(true);size_t split_pos = leaf->keys.size() / 2;new_leaf->keys.assign(leaf->keys.begin() + split_pos, leaf->keys.end());new_leaf->values.assign(leaf->values.begin() + split_pos, leaf->values.end());leaf->keys.erase(leaf->keys.begin() + split_pos, leaf->keys.end());leaf->values.erase(leaf->values.begin() + split_pos, leaf->values.end());new_leaf->next = leaf->next;leaf->next = new_leaf;insert_into_parent(leaf, new_leaf->keys[0], new_leaf);
}

處理節點下溢的邏輯

當節點的鍵數量低于最小值時，需要進行合并或借用：

template <typename Key, typename Value>
void BPlusTree<Key, Value>::handle_underflow(BPlusNode<Key, Value>* node) {if (node == root) {if (node->keys.empty() && !node->children.empty()) {root = node->children[0];delete node;}return;}// Borrow or merge with siblingsBPlusNode<Key, Value>* parent = find_parent(root, node);// Implementation depends on sibling availability and size
}

查找父節點的輔助函數

以下是一個輔助函數，用于查找給定節點的父節點：

template <typename Key, typename Value>
BPlusNode<Key, Value>* BPlusTree<Key, Value>::find_parent(BPlusNode<Key, Value>* current, BPlusNode<Key, Value>* child) {if (current == nullptr || current->is_leaf) return nullptr;for (size_t i = 0; i < current->children.size(); ++i) {if (current->children[i] == child) {return current;}auto parent = find_parent(current->children[i], child);if (parent != nullptr) return parent;}return nullptr;
}

插入到父節點的邏輯

分裂后需要將新節點的鍵插入到父節點中：

template <typename Key, typename Value>
void BPlusTree<Key, Value>::insert_into_parent(BPlusNode<Key, Value>* left, const Key& key, BPlusNode<Key, Value>* right) {BPlusNode<Key, Value>* parent = find_parent(root, left);if (parent == nullptr) {parent = new BPlusNode<Key, Value>(false);parent->keys.push_back(key);parent->children.push_back(left);parent->children.push_back(right);root = parent;return;}auto it = std::lower_bound(parent->keys.begin(), parent->keys.end(), key);size_t index = it - parent->keys.begin();parent->keys.insert(it, key);parent->children.insert(parent->children.begin() + index + 1, right);if (parent->keys.size() > order) {split_internal(parent);}
}

內部節點分裂的邏輯

內部節點的分裂與葉子節點類似，但需要處理子節點指針：

template <typename Key, typename Value>
void BPlusTree<Key, Value>::split_internal(BPlusNode<Key, Value>* node) {BPlusNode<Key, Value>* new_node = new BPlusNode<Key, Value>(false);size_t split_pos = node->keys.size() / 2;Key middle_key = node->keys[split_pos];new_node->keys.assign(node->keys.begin() + split_pos + 1, node->keys.end());new_node->children.assign(node->children.begin() + split_pos + 1, node->children.end());node->keys.erase(node->keys.begin() + split_pos, node->keys.end());node->children.erase(node->children.begin() + split_pos + 1, node->children.end());insert_into_parent(node, middle_key, new_node);
}

清除B+樹的邏輯

析構時需要遞歸釋放所有節點的內存：

template <typename Key, typename Value>
void BPlusTree<Key, Value>::clear(BPlusNode<Key, Value>* node) {if (node == nullptr) return;if (!node->is_leaf) {for (auto child : node->children) {clear(child);}}delete node;
}

搜索操作的實現

根據鍵查找對應的值：

template <typename Key, typename Value>
Value BPlusTree<Key, Value>::search(const Key& key) {BPlusNode<Key, Value>* leaf = find_leaf(root, key);auto it = std::find(leaf->keys.begin(), leaf->keys.end(), key);if (it == leaf->keys.end()) throw std::runtime_error("Key not found");return leaf->values[it - leaf->keys.begin()];
}

查找葉子節點的輔助函數

以下是一個輔助函數，用于查找包含給定鍵的葉子節點：

template <typename Key, typename Value>
BPlusNode<Key, Value>* BPlusTree<Key, Value>::find_leaf(BPlusNode<Key, Value>* node, const Key& key) {if (node == nullptr) return nullptr;if (node->is_leaf) return node;auto it = std::upper_bound(node->keys.begin(), node->keys.end(), key);size_t index = it - node->keys.begin();return find_leaf(node->children[index], key);
}

測試B+樹的刪除功能

以下是一個測試用例，驗證B+樹的刪除功能：

void test_b_plus_tree_deletion() {BPlusTree<int, std::string> tree(3);tree.insert(1, "Alice");tree.insert(2, "Bob");tree.insert(3, "Charlie");tree.remove(2);try {tree.search(2);assert(false);  // Should throw} catch (const std::runtime_error& e) {assert(std::string(e.what()) == "Key not found");}
}

處理葉子節點合并的邏輯

當葉子節點的鍵數量不足時，需要與兄弟節點合并：

template <typename Key, typename Value>
void BPlusTree<Key, Value>::merge_leaves(BPlusNode<Key, Value>* left, BPlusNode<Key, Value>* right) {left->keys.insert(left->keys.end(), right->keys.begin(), right->keys.end());left->values.insert(left->values.end(), right->values.begin(), right->values.end());left->next = right->next;remove_from_parent(right);delete right;
}

從父節點中刪除鍵的邏輯

合并后需要從父節點中刪除對應的鍵：

template <typename Key, typename Value>
void BPlusTree<Key, Value>::remove_from_parent(BPlusNode<Key, Value>* child) {BPlusNode<Key, Value>* parent = find_parent(root, child);if (parent == nullptr) return;auto it = std::find(parent->children.begin(), parent->children.end(), child);if (it == parent->children.end()) return;size_t index = it - parent->children.begin();if (index > 0) {parent->keys.erase(parent->keys.begin() + index - 1);}parent->children.erase(it);if (parent != root && parent->keys.size() < (order + 1) / 2 - 1) {handle_underflow(parent);}
}

測試B+樹的合并功能

以下是一個測試用例，驗證B+樹的合并功能：

void test_b_plus_tree_merge() {BPlusTree<int, std::string> tree(3);for (int i = 1; i <= 4; ++i) {tree.insert(i, "Value" + std::to_string(i));}tree.remove(1);tree.remove(2);assert(tree.search(3) == "Value3");assert(tree.search(4) == "Value4");
}

B+樹的持久化存儲

將B+樹保存到文件中以便后續加載：

template <typename Key, typename Value>
void BPlusTree<Key, Value>::serialize(const std::string& filename) {std::ofstream out(filename, std::ios::binary);serialize_node(out, root);out.close();
}

序列化節點的邏輯

遞歸序列化節點及其子節點：

template <typename Key, typename Value>
void BPlusTree<Key, Value>::serialize_node(std::ofstream& out, BPlusNode<Key, Value>* node) {if (node == nullptr) return;out.write(reinterpret_cast<char*>(&node->is_leaf), sizeof(bool));size_t size = node->keys.size();out.write(reinterpret_cast<char*>(&size), sizeof(size_t));for (const auto& key : node->keys) {out.write(reinterpret_cast<const char*>(&key), sizeof(Key));}if (node->is_leaf) {for (const auto& value : node->values) {size_t val_size = value.size();out.write(reinterpret_cast<char*>(&val_size), sizeof(size_t));out.write(value.c_str(), val_size);}} else {for (auto child : node->children) {serialize_node(out, child);}}
}

從文件加載B+樹

從文件中加載B+樹：

template <typename Key, typename Value>
void BPlusTree<Key, Value>::deserialize(const std::string& filename) {std::ifstream in(filename, std::ios::binary);if (!in) return;clear(root);root = deserialize_node(in);in.close();
}

反序列化節點的邏輯

遞歸加載節點及其子節點：

template <typename Key, typename Value>
BPlusNode<Key, Value>* BPlusTree<Key, Value>::deserialize_node(std::ifstream& in) {if (in.eof()) return nullptr;bool is_leaf;in.read(reinterpret_cast<char*>(&is_leaf), sizeof(bool));BPlusNode<Key, Value>* node = new BPlusNode<Key, Value>(is_leaf);size_t size;in.read(reinterpret_cast<char*>(&size), sizeof(size_t));node->keys.resize(size);for (size_t i = 0; i < size; ++i) {in.read(reinterpret_cast<char*>(&node->keys[i]), sizeof(Key));}if (is_leaf) {node->values.resize(size);for (size_t i = 0; i < size; ++i) {size_t val_size;in.read(reinterpret_cast<char*>(&val_size), sizeof(size_t));char* buffer = new char[val_size + 1];in.read(buffer, val_size);buffer[val_size] = '\0';node->values[i] = std::string(buffer);delete[] buffe

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/diannao/93884.shtml
繁體地址，請注明出處：http://hk.pswp.cn/diannao/93884.shtml
英文地址，請注明出處：http://en.pswp.cn/diannao/93884.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！

相關文章

Android 基礎入門學習目錄（持續更新）

Android 基礎入門學習目錄（持續更新）

四大組件 Activity&#xff1a; Service&#xff1a; BroadcastReceiver&#xff1a; ContentProvider&#xff1a; UI 與交互開發 常見的UI布局和UI控件 樣式與主題 Fragment Intent 數據存儲 自定義View和自定義Group 自定義View 自定義ViewGroup 事件分發 Key…
閱讀更多...
Linux移動大量文件命令

Linux移動大量文件命令

背景 使用 mv 命令報“/bin/mv: 參數列表過長”&#xff0c;也是第一遇到&#xff0c;查了一下&#xff0c;最后用rsync命令解決了。還好每臺服務器&#xff0c;都必裝rsync了&#xff0c;記錄如下。 命令 nohup rsync -av --remove-source-files --progress /public/tmp/video…
閱讀更多...
SQL中的HAVING用法

SQL中的HAVING用法

HAVING 是 SQL 中專門對 “分組之后的聚合結果” 再做篩選的子句。 它一般跟在 GROUP BY 后面&#xff0c;不能單獨使用&#xff0c;作用類似于分組版的 WHERE。? 1. 語法位置 SELECT 列1, 聚合函數(列2) AS 別名 FROM 表 GROUP BY 列1 HAVING 聚合條件; -- 這里寫對聚合…
閱讀更多...
【Halcon 】Halcon 實戰：如何為 XLD 模板添加極性信息以提升匹配精度？

【Halcon 】Halcon 實戰：如何為 XLD 模板添加極性信息以提升匹配精度？

Halcon 實戰&#xff1a;如何為 XLD 模板添加極性信息以提升匹配精度&#xff1f; 在使用 Halcon 進行模板匹配時&#xff0c;我們通常有兩種方式創建模板&#xff1a; 基于圖像灰度&#xff08;CreateScaledShapeModel&#xff09;基于輪廓 XLD&#xff08;CreateScaledShapeM…
閱讀更多...
grafana/lock-stack 日志 Pipeline 配置

grafana/lock-stack 日志 Pipeline 配置

前言 本文使用的是 grafana/loki-stack chart 抓取的 k8s 日志。其他 chart 配置都差不多。 日志問題 docker 容器運行時 pod 內原始日志 [cpu-4] Hello, 第 9788 次報時&#xff0c;時間&#xff1a;2025-08-01T06:35:420000 {"HOSTNAME":"cpu-4",&qu…
閱讀更多...
appium2.0+之PointerActions詳解

appium2.0+之PointerActions詳解

以下內容在 夜神模擬器 上進行。 一、應用場景 一些針對手勢的操作&#xff0c;比如滑動、長按、拖動等。可以將這些基本手勢組合成一個相對復雜的手勢。 二、使用步驟創建觸摸輸入設備&#xff08;模擬手指操作&#xff09; touch_input PointerInput(interaction.POINTER_TO…
閱讀更多...
Java HTTPS 請求失敗排查與證書導入全過程

Java HTTPS 請求失敗排查與證書導入全過程

文章目錄Java HTTPS 請求失敗排查與證書導入全過程問題背景問題初步分析排查過程查看目標地址證書導入證書驗證證書是否導入成功重啟應用進一步驗證&#xff1a;是否真的是證書問題&#xff1f;1. 瀏覽器訪問2. 抓包工具驗證&#xff08;如 Charles、Wireshark&#xff09;補充…
閱讀更多...
android APT技術

android APT技術

1&#xff0c;背景 對于注解的使用&#xff0c;想必大家都不陌生&#xff0c;它出現在我們的源碼中&#xff0c;以及大部分框架中&#xff0c;比如ButterKnife、Arouter、Retrofit&#xff0c;但它們是有區別的&#xff0c;其中前2個是編譯時注解&#xff0c;最后一個是運行時注…
閱讀更多...
MySQL 和 PostgreSQL綜合比對分析匯總

MySQL 和 PostgreSQL綜合比對分析匯總

面對大數據項目或其它類型項目中&#xff0c;面對關系型數據庫選擇一直是很總要的一點&#xff0c;本文針對MySQL 和 PostgreSQL進行綜合比對分析匯總&#xff0c;內容僅供參考。MySQL 和 PostgreSQL 是兩款主流的開源關系型數據庫&#xff08;RDBMS&#xff09;&#xff0c;但…
閱讀更多...
Linux---make和makefile

Linux---make和makefile

一、基本概念1.是什么make是一條命令&#xff0c;makefile是一個文件2.對應在vs中按一下f5就能運行代碼&#xff0c;在Linux中make就相當于f5&#xff0c;使用makefile來封裝從而實現我&#xff0c; 想要的功能3.使用①創建makefile文件②編輯makefile解釋&#xff1a;test.exe…
閱讀更多...
【DAB收音機】DAB收音機協議及其他資料匯總

【DAB收音機】DAB收音機協議及其他資料匯總

目錄[ETSI DAB標準協議文檔](https://www.etsi.org/standards)Other DAB資料DAB收音機相關的專利DAB收音機相關的期刊及學位論文DAB開源項目代碼倉庫qt-dab工具welle.io工具dablin工具【eti廣播工具】?? 項目對比與選型建議Other 收音機資料Other資料ETSI DAB標準協議文檔 官…
閱讀更多...
RabbitMQ的特點和消息可靠性保障

RabbitMQ的特點和消息可靠性保障

掌握RabbitMQ的核心知識&#xff0c;需從其特點和消息可靠性保障&#xff08;尤其是消息丟失解決方案&#xff09;兩方面入手&#xff0c;以下是詳細說明&#xff1a; 一、RabbitMQ的核心特點 RabbitMQ是基于AMQP&#xff08;Advanced Message Queuing Protocol&#xff09;協議…
閱讀更多...
項目升級啦

項目升級啦

公司要新做一個醫療行業的業務&#xff0c;經過業務端和產品端的評估該業務與公司已有的產品線關聯不大&#xff0c;用戶后續也不想在老系統那臺老爺車上繼續使用&#xff0c;話說老系統到現在差不多10年了&#xff0c;中間經歷過的前后端開發者形形色色&#xff0c;維護者換了…
閱讀更多...
Android中頁面生命周期變化

Android中頁面生命周期變化

一、Activity切換的生命周期變化&#xff08;A啟動B&#xff09;1. 標準流程&#xff08;B完全覆蓋A&#xff09;完整生命周期路徑&#xff1a;Activity A&#xff1a;onPause()&#xff1a;失去焦點&#xff0c;仍部分可見onStop()&#xff1a;完全不可見&#xff08;當B完全覆…
閱讀更多...
自動駕駛控制算法——PID算法

自動駕駛控制算法——PID算法

自動駕駛控制算法——PID算法 文章目錄自動駕駛控制算法——PID算法一、PID 是什么&#xff1f;二、PID 原理2.1 **比例環節&#xff08;P&#xff09;**2.2 **積分環節&#xff08;I&#xff09;**2.3 **微分環節&#xff08;D&#xff09;**2.4 特點總結2.5 案例分析 —— 小…
閱讀更多...
Spring Boot 異步執行方式全解析：@Async、CompletableFuture 與 TaskExecutor 對比

Spring Boot 異步執行方式全解析：@Async、CompletableFuture 與 TaskExecutor 對比

在 Spring Boot 開發中&#xff0c;異步執行是提升系統性能的重要手段&#xff0c;尤其適用于處理耗時操作&#xff08;如日志記錄、郵件發送、數據同步等&#xff09;。本文將深入對比 Spring Boot 中三種主流的異步實現方式 ——Async注解、手動CompletableFuture和直接使用T…
閱讀更多...
高效微調2：Prompt-Tuning原理與實戰

高效微調2：Prompt-Tuning原理與實戰

高效微調2：Prompt-Tuning原理與實戰 Prompt-Tuning原理介紹 代碼 Prompt-Tuning原理介紹 Prompt-Tuning Prompt-Tuning的思想：凍結主模型全部參數，在訓練數據前加入一小段Prompt,只訓練Prompt的表示層，即一個Embedding模塊。其中，Prompt.又存在兩種形式，一種是hard promp…
閱讀更多...
使用BART模型和T5模型實現文本改寫

使用BART模型和T5模型實現文本改寫

BART模型BART&#xff08;Bidirectional and Auto-Regressive Transformers&#xff09;是由 Facebook AI Research&#xff08;FAIR&#xff09;在 2019 年提出的序列到序列&#xff08;seq2seq&#xff09;預訓練模型&#xff0c;論文發表于《BART: Denoising Sequence-to-Se…
閱讀更多...
電商前端Nginx訪問日志收集分析實戰

電商前端Nginx訪問日志收集分析實戰

使用FileBeatLogstashES實現分布式日志收集 在大型項目中 &#xff0c;往往服務都是分布在非常多不同的機器上 &#xff0c;每個機器都會打印自己的log日志 但是 &#xff0c;這樣分散的日志 &#xff0c;本來就無法進行整體分析。再加上微服務的負載均衡體系 &#xff0c;甚至…
閱讀更多...
TwinCAT3示例項目1

TwinCAT3示例項目1

目錄一、需求分析二、程序編寫1.實現1盞燈的自控&#xff08;IF、TOF&#xff09;2. 添加模式控制&#xff08;Case、枚舉&#xff09;3. 添加多盞燈&#xff08;FOR、數組&#xff09;4. 添加多組燈&#xff08;二維數組&#xff09;END項目結合了&#xff0c;FB&#xff0c;I…
閱讀更多...
最新文章

Copyright @ 2022~2023