程序员经验分享-hwhale

简单理解B树和B+树

2023-11-05

前言

前面我们说了红黑树，他是一种特殊的搜索树，但是由于他只是二叉树，所以这就导致他在大量的数据面前深度过高，同时会造成大量的磁盘空间浪费，所以我们又研究出来了B树和B+树

B树

他是人们早期的一种设计，他打破了二叉树的方式，它可以有多个分支，使得磁盘空间可以重分利用，同时减少了IO操作
定义：

  1. 结点最多有M颗子树，M-1关键字
  2. 除了跟结点和叶子结点处，他的每个结点至少有（M/2）个子节点，向上取整（分裂的时候分开，则至少两颗子树）
  3. 若根结点不是叶子结点，则至少有两颗子树
    一颗标准的B树如下图
    在这里插入图片描述

B-tree的插入方式-分裂

大致可以描述过程是，首先定义一个M阶的树，之后向第一个结点里面插入数据，如果大于就插入到这个树左边，如果小于这个数就插入到这个树右边，当结点满的时候，他会发现分裂，在M/2向上取整地方分裂，然后那个结点上升分出两个结点
具体可以参考https://www.cnblogs.com/vincently/p/4526560.html

B+树

B+树是对B-树的一次升级，它主要针对的是B-树在建立索引的时候，如果出现范围查找，就会导致索引失效，同时每个结点都要带数据，会导致额外的空间浪费，所以引出了B+树
他有以下的特性

  1. 所有的叶子结点都通过双向链表连接在一起
  2. 非叶子结点不存数据
  3. 数据和结点一样多
    在这里插入图片描述
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

数据结构

BTree

简单理解B树和B+树 的相关文章

随机推荐

  • Freertos中vTaskDelay()是怎么用的

    1 常见的使用场景 void vLED Task void pvParameters while 1 Heartbeat LED vTaskDelay 1000 portTICK RATE MS 说明 上面这段代码的意思是 led翻转后经过

  • Exception in thread "main" java.lang.NoClassDefFoundError解决

    1 错误描述 Exception in thread main java lang NoClassDefFoundError HelloWorld wrong name org xuwei HelloWorld at java lang C

  • 2018年最好的8款杀毒软件

    如今 网络犯罪和欺骗和攻击电脑的病毒 特洛伊木马和网络钓鱼诈骗导致损失的事件并没有像人们想像的那么频繁发生 这意味着很多人正在使用最强大的安全软件保护自己的电脑 而其一如既往地重要 这就是为什么推出这个2018年全球最佳防病毒软件名单的原因

  • 搭建商城的微服务架构-1

    创建父项目 mall 先创建一个 父项目 mall 再在这个父项目中创建多个子项目 修改pom文件 最终mall的pom文件如下

  • 目标检测算法回顾之Anchor free篇章

    基于anchor free的目标检测方法 一 背景与定义 1 1 anchor based的特征 1 2 anchor的好处 1 3 anchor的局限 1 4 anchor free 与anchor based的区别 二 概述 三 早期探

  • 以太坊2.0 节点搭建：共识端+执行端

    1 配置 本人使用配置 共识端 prysm 版本 3 1 1 执行端 geth 版本 1 10 23 当前使用1 10 25 OS centos7 6 CPU 8核 Memory 16GB RAM Storage 3T SSD Networ

  • 算法梳理boosting\bagging\RF(1)

    LeetCode题目记录 1 集成学习概念 1 1 集成学习分类 1 2 集成学习步骤 2 个体学习器概念 3 boosting bagging 3 1 boosting 3 2 bagging 3 3 二者的区别 4 随机森林的思想 5

  • mlxtend实现简单的Apriori算法（关联算法）

    关联算法有几个重要的概念 下面以官方教程为例 Apple Beer Rice Chicken Apple Beer Rice Apple Beer Apple Bananas Milk Beer Rice Chicken Milk Beer

  • springmvc使用JSR-303进行校验

    下面提供一种springmvc的校验方案 一般没有校验或者手动写validator的话都要写好多代码好多if判断 使用JSR 303规范校验只需要在Pojo字段上加上相应的注解就可以实现校验了 1 依赖的jar包 我直接贴pom了

  • cannot find -l 问题处理

    graalvm打包最后一步 第七步 报错 主要错误简述 It appears as though libstdc a is missing Please install it cannot find lstdc 几个要点 1 l是link的

  • c++模板的概念全新解释

    文章目录 前言 一 模板的概念 强类型的严格性和灵活性 解决冲突的路径 模板的概念 一 1 函数模板 函数模板的定义 函数模板的实例化 函数模板的重载 1 函数模板的重载 2 用普通函数重载函数模板 3 用特定函数重载函数模板 类模板 类模

  • Jsch网络工具包的使用及源码简析

    一 背景 最近 导师安排了些看论文文献并整理论文至文件服务器的工作 在实验的过程中 我们知道常见的上传文件至服务器有以下方式 ftp sftp协议进行上传 ssh连接 并通过scp命令进行上传 通过xftp xshell ftplina等图

  • 【QT】Qt Creator 右击添加库无反应解决方案【转发】

    一 软件版本 Qt 5 9 0 二 问题现象 想向工程添加外部库 但点击添加库无反应 三 解决方案 1 打开 pro 文件 2 在 pro 文件界面内 右击鼠标 选择添加库 3 添加库的 UI 弹出 四 总结 Qt 5 9 0 Creato

  • c#.net常用的小函数参考

    选择自 crabapple2 的 Blog c net常用的小函数和方法集 1 DateTime 数字型 System DateTime currentTime new System DateTime 1 1 取当前年月日时分秒 curre

  • 记录JsonNode文本处理asText()和toString()的差异

    原文地址 https blog csdn net xudc0521 article details 89926158 最近使用JsonNode解析json字符串时 遇到一个与预期不一致的小问题 记录一下 先来看一个Test author x

  • log4j问题解决：log4j:WARN No appenders could be found for logger

    在resources目录下新建log4j properties文件 添加以下代码 log4j rootLogger ERROR log4j appender CONSOLE org apache log4j ConsoleAppender

  • 浙江大学 陈越_浙江大学陈越教授开展“程序设计课程建设”讲座

    12月10日下午 媒体工程学院耿卫东院长邀请了浙江大学陈越教授开展 程序设计课程建设 讲座 学院各课程群负责人 专业主任及其他专业教师共30余人聆听了讲座 并围绕 程序设计课程建设 的主题展开了深入探讨和交流 学院副院长章化冰主持讲座 代表

  • java基础学习 day25（二维数组）

    什么是二维数组 在数组中存放数组 二维数组的应用场景 当我们需要把数据分组管理的时候 就需要用二维数组 静态初始化格式 数据类型 数组名 new 数据类型 元素1 元素2 元素1 元素2 简化格式 数据类型 数组名 元素1 元素2 元素1

  • Java使用JVM工具检测问题

    1 jps 显示运行程序的进程 编码 主类目录信息 public class Demo01 jps 显示进程ID 主类名称 jps v 显示进程ID 主类名称以及详细编码信息 jps l 显示进程ID 主类目录 param args thr

  • 简单理解B树和B+树

    前言 前面我们说了红黑树 他是一种特殊的搜索树 但是由于他只是二叉树 所以这就导致他在大量的数据面前深度过高 同时会造成大量的磁盘空间浪费 所以我们又研究出来了B树和B 树 B树 他是人们早期的一种设计 他打破了二叉树的方式 它可以有多个分

热门标签