程序员经验分享-hwhale

数据结构—B+树

2023-05-16

1. 约束

B+ 树的约束与 B 树类似，一棵 m m m 阶 B+ 树具有如下特点：

（1）根节点要么是一个叶节点，要么至少具有两个孩子节点；
（2）除根节点以外，每个内部节点都具有 [ ⌈ m / 2 ⌉ , m ] [\lceil m/2\rceil, m] [⌈m/2⌉,m] 个孩子节点，因此具有 [ ⌈ m / 2 ⌉ − 1 , m − 1 ] [\lceil m/2\rceil -1, m-1] [⌈m/2⌉−1,m−1] 个关键码；（有些定义中，要求关键码个数与指针个数相同）
（3）所有叶节点都处在树的同一层；
（4）每个节点都会按序存储关键码，介于关键码 k e y 1 key1 key1 和 k e y 2 key2 key2 之间的指针所指孩子节点所存储的关键码的范围为 [ k e y 1 , k e y 2 ) [key1, key2) [key1,key2)。

与 B 树不同的地方：

（1）B+ 树的内部节点只存储关键码，实际记录只存在于叶节点中；如果将 B+ 树作为纯粹的索引实现，叶节点存储关键码及指向相应记录的指针，而实际记录存储在单独的磁盘文件中。
（2）B+ 树的叶节点一般会链接起来，形成一个双链表，如此通过访问链表中的所有叶节点便可以遍历所有的记录，因此适合于范围查询。
（3）B+ 树叶节点存储的记录数可能多于或少于 m m m，只要叶节点至少达到半满即可。
（4）B+ 树的搜索过程必须一直往下直至达到相应的叶节点才可，因为只有叶节点才存储实际的记录。
（5）因为 B+ 树的内部节点只存储关键码而不存储记录，所以其内部节点可以存储更多的关键码，即拥有更多的分支（子树），所以，存储相同数量的关键码时，B+ 树会比 B 树更加“矮胖”。

通常情况下，要使 B+ 树一个节点的大小能填满一个磁盘块，节点中的“指针”实际上就是孩子节点所在的磁盘块号。

2. 搜索

（1）从根节点开始；
（2）在当前节点中对关键码进行二分搜索，然后沿着相应的分支继续往下，重复此步骤，直至到达叶节点；
（3）如果当前节点是叶节点且没有找到目标，则失败返回；否则，返回相应的记录。

3. 插入

设叶节点包含的记录数的范围为 [ ⌈ L / 2 ⌉ , L ] [\lceil L/2 \rceil, L] [⌈L/2⌉,L]。

（1）首先找到应当包含待插入关键码的叶节点 x x x；
（2）如果目标叶节点还有空闲的空间（记录数少于 L L L），则插入关键码，然后成功返回，否则继续往下执行；
（3）如果目标叶节点已经满了，则在插入关键码之后，将其等分为两个叶节点 x 1 , x 2 x1, x2 x1,x2，然后将叶节点 x 2 x2 x2 中最小的那个关键码的一个副本提升到父节点 y y y 中，如果父节点仍有空闲的空间（关键码个数少于 m − 1 m-1 m−1），则成功返回，否则继续往下执行；
（4）将父节点 y y y 分裂为两个节点 y 1 , y 2 y1,y2 y1,y2，其中 y 1 y1 y1 包含前 ⌊ m / 2 ⌋ \lfloor m/2\rfloor ⌊m/2⌋ 个关键码， y 2 y2 y2 包含后 m − ⌊ m / 2 ⌋ − 1 m-\lfloor m/2\rfloor-1 m−⌊m/2⌋−1 个关键码，然后将第 ⌈ m / 2 ⌉ \lceil m/2\rceil ⌈m/2⌉ 个关键码提升至 y y y 的父节点 z z z，如果 z z z 仍有空闲的空间，则成功返回，否则继续执行此步骤。

在这里插入图片描述

4. 删除

（1）首先找到包含待删除关键码的叶节点 x x x，然后从中删除指定的关键码，如果删除后， x x x 仍然达到半满，则成功返回，否则继续往下执行；
（2）若 x x x 的右（左）兄弟节点 y y y 包含的记录数大于 ⌈ L / 2 ⌉ \lceil L/2 \rceil ⌈L/2⌉，则将 y y y 中最小（最大）的一个关键码及相应的记录移到 x x x 中，然后使用 y y y（ x x x）中最小的关键码替换父节点中处于 x , y x,y x,y 之间的那个关键码，最后成功返回；否则继续往下执行；
（3）如果 x x x 的左右兄弟节点都没有足够的关键码可借，则将 x x x 及其兄弟节点 y y y 合并为一个节点，并删除父节点 z z z 中处于 x , y x,y x,y 之间的那个关键码，若父节点 z z z 没有发生下溢，则操作成功返回，否则继续往下执行；
（4）若节点 z z z 的右（左）兄弟节点 w w w 包含有富余的关键码，则将节点 z z z 的父节点中处于 z , w z,w z,w 之间的那个关键码 A A A 下移到节点 z z z 中，然后将 w w w 中最小（最大）的那个关键码上移到父节点并替换 A A A，然后成功返回，否则继续往下执行；
（5）若节点 z z z 的左右兄弟 w w w 皆不富余，则将节点 z , w z,w z,w 合并为一个节点，然后将父节点中介于 z , w z,w z,w 之间的那个关键码 A A A 下移到合并后的节点中；如果此操作导致父节点也发生了下溢，则继续回到步骤（4），否则成功返回。

在这里插入图片描述
图示来自 http://www.cnblogs.com/nullzx/ 。

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

数据结构—B+树 的相关文章

  • 编译器 链接 选项解释：link incrementally的作用

    What is ILT xff08 Incremental Link Table 这两天研究了一下DLL的import export原理 xff0c 看了一些资料 xff0c 无意中发现网上有一篇文章存在错误 xff0c 而这篇文章流传还甚

  • 关于涉密信息系统分级保护的几个问题

    2003年9月7日 xff0c 中共中央办公厅 国务院办公厅转发了 国家信息化领导小组关于加强国家信息安全保障工作的意见 xff0c 其中明确提出了开展信息安全等级保护的任务 xff0c 并指出涉及国家秘密的信息系统 xff08 以下简称涉

  • Launch your application in Vista under the local system account without the UAC popup

    This article describes how to launch an application from session 0 to session 1 under the local system account using a s

  • UTF8ToAnsi 和 AnsiToUTF8

    std string UTF8ToAnsi const std string amp strIn std string amp strOut WCHAR strSrc 61 NULL TCHAR szRes 61 NULL int i 61

  • TCP/IP 配置参数

    TCP IP 配置参数 Windows 2000 TCP IP 协议组件实现从注册表中获取全部配置数据 配置信息 是由安装程序写到注册表中的 一些信息也可以由动态主机配置协议 DHCP 客户 服务提供 xff08 如启用 xff09 本附录

  • ExpLookupHandleTableEntry

    wrk1 2中 ExpLookupHandleTableEntry的内部流程 1 取 Handle EXHANDLE类型 值为tHandle 并将TagBit 低两位 置0 2 取 HandleTable gt NextHandleNeed

  • C++完美转发

    1 std forawrd std forward lt T gt arg 可以实现完美转发 xff0c 即如果 arg 是一个右值引用 xff0c 则转发之后结果仍是右值引用 xff1b 反之 xff0c 如果 arg 是一个左值引用 x

  • win7 usb u盘打不开，设备管理器提示：该设备无法启动。 (代码 10)

    解决 xff1a 禁用改设备 gt 卸载 gt 重新插入u盘

  • linux netlink机制介绍与实例

    开发和维护内核是一件很繁杂的工作 xff0c 因此 xff0c 只有那些最重要或者与系统性能息息相关的代码才将其安排在内核中 其它程序 xff0c 比如GUI xff0c 管理以及控制部分的代码 xff0c 一般都会作为用户态程序 在 li

  • error LNK2038: 检测到“_ITERATOR_DEBUG_LEVEL”的不匹配项的原因及解决方案

    值 0 不匹配值 2 xff0c Debug使用了Release下的库文件 值 2 不匹配值 0 xff0c Release使用了Debug下的库文件 对于上述两种情况 xff0c 只需要在预处理定义中设定其值使其符合要调用的程序即可 VS

  • SNMP协议详解<二>

    上一篇文章讲解了SNMP的基本架构 xff0c 本篇文章将重点分析SNMP报文 xff0c 并对不同版本 xff08 SNMPv1 v2c v3 xff09 进行区别 xff01 四 SNMP协议数据单元 在SNMP管理中 xff0c 管理

  • SNMP协议详解<三>

    在上篇文章中 xff0c 说到了SNMPv3主要在安全性方面进行了增强 xff0c 采用USM xff08 基于用户的安全模型 xff09 和VACM xff08 基于视图的访问控制模型 xff09 技术 下面我们就主要讲解SNMPv3的报

  • SNMPv3的加密和认证过程

    前面的一些文章详细讲解了SNMPv3的报文内容 xff0c 下面主要的内容就是SNMPv3的加密和认证过程 xff01 USM的定义为实现以下功能 xff1a 鉴别 数据加密 密钥管理 时钟同步化 避免延时和重播攻击 1 UsmSecuri

  • H3C SNMPv3 配置

    1 xff09 H3C SNMPv3 配置 html view plain copy print snmp agent mib view included MIB 2 mib 2 snmp agent mib view included M

  • SNMPv3原理-SNMPv3协议框架

    1 SNMPv3的体系结构 SNMPv3定义了新的体系结构 xff0c 并在其中包含了对SNMPv1和SNMPv2c的兼容 xff0c 即这个新的体系结构也适用于SNMPv1及SNMPv2c xff0c 弥补了SNMP没有完整体系结构的缺点

  • MBR与GTP

    现有的PC机架构 xff0c 是沿用了数十年的主板BIOS 43 硬盘MBR分区的组合模式 随着不久的将来 xff08 2009年 xff1f xff09 硬盘容量突破2TB xff0c BIOS xff0b MBR组合估计会被主板EFI和

  • R6002-floating point not loaded 的问题解决方法 .

    最近项目的要计算浮点数据 xff0c 为了调试方便 xff0c 输出计算结果值到DEBUG信息 xff0c 结果却出现 R6002 错误 Google了一下 xff0c MSDN上对于R6002的描述信息是 xff1a 错误消息 未加载浮点

  • KVM修改虚拟机配置

    1 修改内存或 CPU 编辑虚拟机配置文件 xff1a root 64 controller virsh edit centos2 如 xff0c span class token tag span class token tag span

  • 调试笔记之观察中断

    调试笔记之观察中断 中断好比计算机系统的脉搏 xff0c 是系统生命力的源泉 在WinDBG做内核调试时该如何观察系统的中断分配和响应情况呢 xff1f WinDBG的帮助文件对此描述甚少 xff0c 已经有的几个重要扩展命令居然也没有出现

  • 活动目录域控制器端口

    活动目录域控制器端口 域成员与域控之间通讯需要开放什么端口 xff0c 除了LDAP389 139 445 DNS21 xff0c 还有其他吗 xff1f 回答 xff1a 根据您的描述 xff0c 我对这个问题的理解是 xff1a DC和

随机推荐

  • Apollo编译卡死问题

    最近在研究apollo xff0c 按照他们官方教程下载安装后 输入下面命令开启并进入docker bash docker scripts dev start sh bash docker scripts dev into sh 然后就进入

  • docker服务器的图形显示方案

    问题描述 xff1a 一般docker实操时都是作为服务器 xff0c 以字符方式交互 xff0c 非常不方便 本人尝试各种图形解决方案 xff0c 最终找到完美方案 最初本人尝试过VNC和SSH方式 xff0c 最终被否定了 1 本来do

  • Centos7下使用CMake

    在进行需要提供跨平台服务的项目时 xff0c 最好有相应的跨平台项目构建工具 本文所述的CMake即其中比较好用的跨平台构建工具之一 下文主要以C 43 43 语言为例进行使用演示 安装C 43 43 所需的环境 xff1a yum ins

  • 树莓派+神经计算棒2实时人脸检测

    树莓派配置摄像头 sudo apt get install python opencv sudo apt get install fswebcam 配置摄像头 sudo nano etc modules 查看树莓派CPU型号 cat pro

  • 学习总结-编写自己的CMakeLists.txt

    cmake minimum required span class token punctuation span VERSION span class token number 3 3 span span class token punct

  • 7.4V锂电池USB平衡充电器 串联锂电池充电器

    7 4V锂电池USB平衡充电器 串联锂电池充电器 本文介绍一种简单实用的串联锂电池充电器 大家知道 xff0c 串联电池的充电 xff0c 是一个麻烦的问题 如果直接拿7 4V来充 xff0c 可能会因为两颗电池的参数差异 xff0c 会导

  • 【Echarts】数据可视化完成大屏地图（拓展乡镇地区）的绘制

    绘制地图要素 地图边缘 地理位置 xff08 中心点或者自定义的未知 xff09 echarts绘制 实现在前 成品展示放在最后 代码太长 xff0c 参考代码可见Github Github地址 获取地图 获取精确到乡镇街道的地图JSON数

  • K8s问题【flannel一直重启问题，CrashLoopBackOff】

    kubectl describe 命令查看 Events Type Reason Age From Message Normal Scheduled 13m default scheduler Successfully assigned k

  • Python openpyxl库

    1 读写单元格 span class token keyword from span openpyxl span class token keyword import span load workbook wb span class tok

  • 子网掩码

    子网掩码 subnet mask 是每个网管必须要掌握的基础知识 xff0c 只有掌握它 xff0c 才能够真正理解TCP IP协议的设置 以下我们就来深入浅出地讲解什么是子网掩码 IP地址的结构 要想理解什么是子网掩码 xff0c 就不能

  • AS学习网址大全

    都是我在学习过程中精心收集的 xff0c 大部分为国内网站 xff0c 绝对是您学习AS最好的去处 本贴于2010年3月22日再次更新 xff0c 并新加了很多好的网站 1 同时将网址全都贴出来 xff0c 方便不想下载的朋友使用 2 附件

  • 紧耦合和松耦合有什么区别

  • 我的大一学习生活总结

    今天最后的一科英语考完了 xff0c 但此刻的我并不觉的轻松 xff0c 我知道从现在开始就标志着我的大一已经结束了 xff0c 在大学仅有的四年时光就过去了四分之一 回想起大一这一年 xff0c 自问一下我到底学到了什么 xff1f 我发

  • 阿里云导出raw文件如何还原查看及centos7系统密码破解

    1 Raw格式转换 1 1 格式介绍 目前阿里云ecs镜像文件的导出格式默认为 raw tar gz xff0c 解压后为 raw格式 raw为最原始的虚拟机镜像文件 xff0c vmdk是vmware Virtual Box的虚拟机镜像文

  • 5.33 综合案例2.0 -ESP32拍照上传阿里云OSS

    综合案例2 0 ESP32拍照上传阿里云OSS 案例说明连线功能实现1 阿里云平台连接2 OSS对象存储服务3 ESP32 CAM开发环境4 代码ESP32 CAM开发板代码HaaS506开发板代码 测试数据转图片方法 案例说明 使用ESP

  • 'grep' 不是内部或外部命令，也不是可运行的程序或批处理文件

    使用 grep 来过滤 xff1a adb shell pm list packages grep qq 然后就报了 39 grep 39 不是内部或外部命令 xff0c 也不是可运行的程序或批处理文件 xff0c 后来发现根本不是grep

  • 一个程序员的一生

    一个程序员的一生 作者 佚名 我在程序员的时候 xff0c 我一开始追逐这个API怎么用 xff0c 数据库SQL怎么写更优化 xff0c Dcom技术的细节 xff0c 然后我发现我写出来的产品为了符合客户 需求必须要大量修改 xff0c

  • 搭建Ubuntu Samba服务器（超简单）

    1 xff09 安装samba服务 sudo apt get install samba 2 xff09 配置samba sudo vim etc samba smb conf share comment 61 myshare path 6

  • Nginx-配置HTTPS证书(单向认证)

    目录 一 生成 CA 私钥 1 生成一个 CA 私钥 ca key 二 生成CA 的数字证书 1 生成一个 CA 的数字证书 ca crt 三 生成 server 端数字证书请求 1 生成 nginx 端的私钥 nginx key 2 生成

  • 数据结构—B+树

    1 约束 B 43 树的约束与 B 树类似 xff0c 一棵 m m m 阶 B 43 树具有如下特点 xff1a xff08 1 xff09 根节点要么是一个叶节点 xff0c 要么至少具有两个孩子节点 xff1b xff08 2 xff

热门标签