探索B-树系列

embedded/2025/2/13 11:02:22/

🌈前言🌈

        本文将讲解B树系列,包含 B-树,B+树,B*树,其中主要讲解B树底层原理,为什么用B树作为外查询的数据结构,以及B-树插入操作并用代码实现;介绍B+树、B*树。

📁常见的搜索结构

种类数据格式时间复杂度
顺序查找无要求O(N)
二分查找有序O(logN)
二叉搜索树无要求O(N)
二叉平衡树无要求O(logN)
哈希无要求O(1)

        以上数据结构适用于数据量不大的情况下,能够一次性存放在内存中,进行数据查找的场景。

        对内存进行访问是很快的,纳秒级别(10^-9)。但是同样时间内,访问磁盘的时间是很慢的,毫秒级别(10^-3)。

        从表格可以看出,高效的查找结构是二叉平衡树和哈希表,但是他们都有一定的缺点。

        对于二叉平衡树,时间复杂度还是很高,例如10亿的数据可能需要30次磁盘访问,这是难以接受的结果。        

        哈希表时间复杂度很低,但是哈希存在哈希冲突的问题,在某些极端场景下,某个位置冲突很多,导致访问次数剧增,也难以接受。

        因此,就有了B-树系列,通过压缩树的高度,来减少磁盘访问次数,提高对数据的访问速度。

📁 B树

 📂概念

        1970年,R.Bayer和E.mccreight提出了一种适合外查找的树,它是一种平衡的多叉树,称为B树。

一棵m阶(m>2)的B树,是一棵平衡的M路平衡搜索树,可以是空树或者满足一下性质:

 1. 根节点至少有两个孩子

 2. 每个分支节点都包含k-1个关键字和k个孩子,其中 ceil(m/2) ≤ k ≤ m ceil是向上取整函数

 3. 每个叶子节点都包含k-1个关键字,其中 ceil(m/2) ≤ k ≤ m

 4.  所有的叶子节点都在同一层

 5.  每个节点中的关键字从小到大排列,节点当中k-1个元素正好是k个孩子包含的元素的值域划分 

 6. 每个结点的结构为:(n,A0,K1,A1,K2,A2,… ,Kn,An)其中,Ki(1≤i≤n)为关键字,且Ki<Ki+1(1≤i≤n-1)。Ai(0≤i≤n)为指向子树根结点的指针。且Ai所指子树所有结点中的关键字均小于Ki+1。n为结点中关键字的个数,满足ceil(m/2)-1≤n≤m-1。

 📂 插入

插入流程:

        1. 如果树为空,直接插入新节点,作为根节点。

        2. 树非空,找到待插入元素在树的插入位置(维护B树的性质,一定要在叶子节点中插入)

        3.  找到元素要插入的节点cur后,插入元素,注意元素一定是从小到大排序的。

        4. 检测该节点cur是否满足B树性质:即节点中元素个数是否等于M,如果小于则满足

        5. 如果不满足,就进行分裂:

                a. 申请新节点brother。

                b. 找到cur节点中间位置mid,mid之后的元素和孩子节点移到brother中。

                c. mid元素及brother节点插入到上层节点parent,重复上述操作,指导节点满足B树性质。

        一下代码是为了更好理解 B-树插入流程,并不是为了造更好的轮子,但是整体结构上大致是一样的。

template<class K, int M>
struct BTreeNode
{typedef BTreeNode<K, M> Node;K _keys[M];Node* _subs[M + 1];size_t _n = 0;Node* _parent = nullptr;BTreeNode(){for (int i = 0; i < M; ++i){_keys[i] = K();_subs[i] = nullptr;}_subs[M] = nullptr;}
};template<class K,int M = 3>
class BTree
{typedef BTreeNode<K, M> Node;
public:pair<Node*, int> Find(const K& key){Node* parent = nullptr;Node* cur = _root;while (cur){size_t i = 0;while(i < cur->_n){if (key < cur->_keys[i]){break;}else if (key > cur->_keys[i]){++i;}else{return make_pair(cur, i);}}parent = cur;cur = cur->_subs[i];}return make_pair(parent, -1);}void insertKey(Node* node , const K& key , Node* child){int end = node->_n - 1;while (end >= 0){if (node->_keys[end] >= key){node->_keys[end + 1] = node->_keys[end];node->_subs[end + 2] = node->_subs[end + 1];--end;}else{break;}}node->_keys[end + 1] = key;node->_subs[end + 2] = child;if (child)child->_parent = node;++node->_n;}bool insert(const K& key){if (_root == nullptr){_root = new Node();_root->_keys[0] = key;_root->_n = 1;return true;}//去重pair<Node*, int> it = Find(key);if (it.second != -1){return false;}Node* cur = it.first;insertKey(cur, key, nullptr);//节点未满,可以继续存放关键码 , 不需要分裂直接返回if (cur->_n != M){return true;}//节点满了,向左 向上分裂//1. 找到节点数据域中间位置//2. 给一个新节点,将中间位置以后数据移动到brother //3. 中间位置数据移动到父节点//4. 节点连接while (cur->_n == M){Node* brother = new Node;size_t mid = cur->_n >> 1;int i = mid + 1, j = 0;while (i < M){//cur 把关键字及其左孩子给brotherbrother->_keys[j] = cur->_keys[i];brother->_subs[j++] = cur->_subs[i];cur->_keys[i] = K();cur->_subs[i] = nullptr;++i;}//最后处理一下最右位置的孩子brother->_subs[j] = cur->_subs[i];cur->_subs[i] = nullptr;K midKey = cur->_keys[mid];cur->_keys[mid] = K();brother->_n = j;cur->_n = cur->_n - j - 1;Node* parent = cur->_parent;if (parent == nullptr){//分裂的是根节点_root = new Node;_root->_keys[0] = midKey;_root->_subs[0] = cur;_root->_subs[1] = brother;_root->_n = 1;cur->_parent = _root;brother->_parent = _root;}else{//不是根节点 处理完当前层后,继续往上处理insertKey(parent, midKey, brother);cur = parent;parent = cur->_parent;}}return true;}private:Node* _root = nullptr;
};

        B-树效率是很高的,大多数场景下,M设为1024,因此对于10亿的数据量,我们只需要3次磁盘访问即可,对比二叉平衡树的十几次的磁盘访问是很快的,大大减少了读取磁盘的次数。

📁 B+树

        B+树是B树的变形,是在B树基础上优化的多路平衡搜索树,B+树的规则跟B树基本类似,但是又在B树的基础上做了以下几点改进优化:

        1. 分支节点的子树指针与关键字个数相同
        2. 分支节点的子树指针p[i]指向关键字值大小在[k[i],k[i+1])区间之间
        3. 所有叶子节点增加一个链接指针链接在一起
        4. 所有关键字及其映射数据都在叶子节点出现

B+树的特性:
        1. 所有关键字都出现在叶子节点的链表中,且链表中的节点都是有序的。
        2. 不可能在分支节点中命中。
        3. 分支节点相当于是叶子节点的索引,叶子节点才是存储数据的数据层。

B+树的分裂:
        当一个结点满时,分配一个新的结点,并将原结点中1/2的数据复制到新结点,最后在父结点中增加新结点的指针;B+树的分裂只影响原结点和父结点,而不会影响兄弟结点,所以它不需要指向兄弟的指针。

📁 B*树

        B*树是B+树的变形,在B+树的非根和非叶子节点再增加指向兄弟节点的指针。

B*树的分裂:
        当一个结点满时,如果它的下一个兄弟结点未满,那么将一部分数据移到兄弟结点中,再在原结点插入关键字,最后修改父结点中兄弟结点的关键字(因为兄弟结点的关键字范围改变了);如果兄弟也满了,则在原结点与兄弟结点之间增加新结点,并各复制1/3的数据到新结点,最后在父结点增加新结点的指针。
        所以,B*树分配新结点的概率比B+树要低,空间使用率更高;

📁 总结

        B树:有序数组+平衡多叉树;
        B+树:有序数组链表+平衡多叉树;
        B*树:一棵更丰满的,空间利用率更高的B+树。

        此外,B-树最常见的应用就是用来做索引。MySQL官方对索引的定义为:索引(index)是帮助MySQL高效获取数据的数据结构,简单来说:索引就是数据结构


http://www.ppmy.cn/embedded/161857.html

相关文章

基于ssm的在线考试系统

一、系统架构 前端&#xff1a;jsp | bootstrap | jquery | css | ajax 后端&#xff1a;spring| springm | mybatis 环境&#xff1a;jdk1.8 | mysql | maven | tomcat 二、代码及数据 三、功能介绍 01. 登录 02. 管理员-题库-选择题查询 03. 管理员-…

瑞芯微开发板/主板Android调试串口配置为普通串口方法 深圳触觉智能科技分享

本文介绍瑞芯微开发板/主板Android调试串口配置为普通串口方法&#xff0c;不同板型找到对应文件修改&#xff0c;修改的方法相通。触觉智能RK3562开发板演示&#xff0c;搭载4核A53处理器&#xff0c;主频高达2.0GHz&#xff1b;内置独立1Tops算力NPU&#xff0c;可应用于物联…

HTML之JavaScript运算符

HTML之JavaScript运算符 1.算术运算符 - * / %除以0&#xff0c;结果为Infinity取余数&#xff0c;如果除数为0&#xff0c;结果为NaN NAN:Not A Number2.复合赋值运算符 - * / %/ 除以0&#xff0c;结果为Infinity% 如果除数为0&#xff0c;结果为NaN NaN:No…

Intellij IDEA调整栈内存空间大小详细教程,添加参数-Xss....

测试添加参数的效果代码&#xff1a; package org.example;public class Demo1 {static int count 0;public static void main (String[] args) throws InterruptedException{//为什么不写String[] args就不出现运行的标识呢&#xff1f;method1();try{method();}catch (Erro…

【PPT】PPT中通过方框、边界、文字、 颜色等组合来表达设计自己的思路

在PPT设计中&#xff0c;利用方框、边界、文字、颜色区分等元素的组合&#xff0c;能够有效地传达你的设计思路。下面是一些方法&#xff0c;帮助你理解如何通过这些元素来表达思路&#xff1a; 1. 方框的使用&#xff1a; 目的&#xff1a;方框通常用来突出或围绕重要信息&a…

哪吒闹海!SCI算法+分解组合+四模型原创对比首发!SGMD-FATA-Transformer-LSTM多变量时序预测

哪吒闹海&#xff01;SCI算法分解组合四模型原创对比首发&#xff01;SGMD-FATA-Transformer-LSTM多变量时序预测 目录 哪吒闹海&#xff01;SCI算法分解组合四模型原创对比首发&#xff01;SGMD-FATA-Transformer-LSTM多变量时序预测效果一览基本介绍程序设计参考资料 效果一览…

DeepSeek免费部署到WPS或Office

部署到WPS - 通过OfficeAI插件接入&#xff1a; - 准备工作&#xff1a;安装最新版本的WPS Office软件&#xff1b;访问DeepSeek官网&#xff0c;点击右上角的“API开放平台”&#xff0c;登录账号&#xff08;若无账号需先注册&#xff09;&#xff0c;登录成功后&#xff0c;…

《qt open3d网格拉普拉斯平滑》

qt open3d网格拉普拉斯平滑 效果展示二、流程三、代码效果展示 二、流程 创建动作,链接到槽函数,并把动作放置菜单栏 参照前文 三、代码 1、槽函数实现 void on_actionFilterLaplacian_triggered();void MainWindow::on_actionFil