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