程序员经验分享-hwhale

算法——B树，B-树，B+树，B*树全面解析笔记

2023-11-17

算法——B树，B-树，B+树，B*树全面解析笔记

https://www.cnblogs.com/lianzhilei/p/11250589.html
http://blog.codinglabs.org/articles/theory-of-mysql-index.html
https://zhuanlan.zhihu.com/p/54102723

树的有序简单理解

该图片来源于https://www.jianshu.com/p/e136ec79235c
在这里插入图片描述
ps：中序遍历就是沿x轴从左到右扫描

索引的本质

    MySQL官方对索引的定义为：索引（Index）是帮助MySQL高效获取数据的数据结构。提取句子主干，就可以得到索引的本质：索引是数据结构。

    我们知道，数据库查询是数据库的最主要功能之一。我们都希望查询数据的速度能尽可能的快，因此数据库系统的设计者会从查询算法的角度进行优化。最基本的查询算法当然是顺序查找（linear search），这种复杂度为O(n)的算法在数据量很大时显然是糟糕的，好在计算机科学的发展提供了很多更优秀的查找算法，例如二分查找（binary search）、二叉树查找（binary tree search）等。如果稍微分析一下会发现，每种查找算法都只能应用于特定的数据结构之上，例如二分查找要求被检索数据有序，而二叉树查找只能应用于二叉查找树上，但是数据本身的组织结构不可能完全满足各种数据结构（例如，理论上不可能同时将两列都按顺序进行组织），所以，在数据之外，数据库系统还维护着满足特定查找算法的数据结构，这些数据结构以某种方式引用（指向）数据，这样就可以在这些数据结构上实现高级查找算法。这种数据结构，就是索引

ps：实际的数据库系统几乎没有使用二叉查找树或其进化品种红黑树（red-black tree）实现的，大部分数据库系统及文件系统都采用B-Tree或其变种B+Tree作为索引结构

B树 = B-树

    B-树，即为B树。因为B树的原英文名称为B-tree，而国内很多人喜欢把B-tree译作B-树

ps：比动态规划还要让人火大的译名
ps：动态规划=递归+数组缓存(一维或二维)，在数学中有个令人又爱又恨的名字——数列。已知首项a1，程序员寻找递归公式an和an-1的关系，让计算机暴力破解通项公式
ps：好像不小心跑题了，欸嘿

    B树的出现是为了弥合不同的存储级别之间的访问速度上的巨大差异，实现高效的 I/O。平衡二叉树的查找效率是非常高的，并可以通过降低树的深度来提高查找的效率。但是当数据量非常大，树的存储的元素数量是有限的，这样会导致二叉查找树结构由于树的深度过大而造成磁盘I/O读写过于频繁，进而导致查询效率低下。另外数据量过大会导致内存空间不够容纳平衡二叉树所有结点的情况。B树是解决这个问题的很好的结构。

    首先，B树不要和二叉树混淆，在计算机科学中，B树是一种自平衡树的数据结构，它维护有序数据并允许以对数时间进行搜索，顺序访问，插入和删除。B树是二叉搜索树的一般化，因为节点可以有两个以上的子节点。与其他自平衡二进制搜索树不同，B树非常适合读取和写入相对较大的数据块（如光盘）的存储系统。它通常用于数据库和文件系统

ps：Mysql使用的是B+树

B树定义

B树是一种平衡的多分树，通常我们说m阶的B树，它必须满足如下条件：
· 每个节点最多只有m个子节点
· 每个非叶子节点（除了根）具有至少⌈ m/2⌉子节点
· 如果根不是叶节点，则根至少有两个子节点
· 具有k个子节点的非叶节点包含k -1个键
· 所有叶子都出现在同一水平，没有任何信息（高度一致）

B树阶

B树中一个节点的子节点数目的最大值，用m表示，假如最大值为10，则为10阶，如图
请添加图片描述
所有节点中，节点【13,16,19】拥有的子节点数目最多，四个子节点（灰色节点），所以可以定义上面的图片为4阶B树

ps：先定义树阶，再根据树阶构建树，树的结构转换不会影响树阶。4阶表示最多4个分叉，可以小于4个，就像二叉树不一定是满二叉树

根节点

节点【10】即为根节点，特征：根节点拥有的子节点数量的上限和内部节点相同，如果根节点不是树中唯一节点的话，至少有俩个子节点（不然就变成单支了）。在m阶B树中（根节点非树中唯一节点），那么有关系式2<= M <=m，M为子节点数量；包含的元素数量 1<= K <=m-1,K为元素数量

ps：2 <= 子节点数量M <= 树阶m，1 <= 元素数量K <= 树阶m-1

内部节点

节点【13,16,19】、节点【3,6】都为内部节点，特征：内部节点是除叶子节点和根节点之外的所有节点，拥有父节点和子节点。假定m阶B树的内部节点的子节点数量为M，则一定要符合⌈ m/2⌉<= M <=m关系式，包含元素数量M-1；包含的元素数量 ⌈ m/2⌉-1<= K <=m-1,K为元素数量。m/2向上取整

ps：树阶m/2 <= 内部节点子节点数量M <= 树阶m，表示每个节点至少要装一半，树阶m/2去掉小数 <= 元素数量K <= 树阶m-1

叶子节点

节点【1,2】、节点【11,12】等最后一层都为叶子节点，叶子节点对元素的数量有相同的限制，但是没有子节点，也没有指向子节点的指针。特征：在m阶B树中叶子节点的元素符合⌈ m/2⌉-1<= K <=m-1

ps：树阶m/2去掉小数 <= 元素数量K <= 树阶m-1

B树插入

针对m阶高度h的B树，插入一个元素时，首先在B树中是否存在，如果不存在，即在叶子结点处结束，然后在叶子结点中插入该新的元素
· 若该节点元素个数小于m-1，直接插入
· 若该节点元素个数等于m-1，引起节点分裂；以该节点中间元素为分界，取中间元素（偶数个数，中间两个随机选取）插入到父节点中
· 重复上面动作，直到所有节点符合B树的规则；最坏的情况一直分裂到根节点，生成新的根节点，高度增加1

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

算法

算法——B树，B-树，B+树，B*树全面解析笔记 的相关文章

  • 循环“停止”的三种特殊语句

    对于一个初学者来说 循环的控制无疑是一个难点和重点 但是在有些时候循环是不需要执行完的 或者这个循环的这一次是不用执行的 那么我们如何来实现这些功能呢 下面通过一个例子来加以说明 1 break语句跳出就近的一层循环 while i lt

  • 渗透相关问题（3）

    1 sql注入绕过的方法 注释符号绕过 大小写绕过 内联注释绕过 双写关键字绕过 特殊编码绕过 宽字节绕过 2 WAF常用的类型 硬件设备类型 软件产品类型 基于云的WAF 3 sql注入漏洞防御方法 代码层面 对输入进行严格的转义和过滤

  • JavaSE学习总结：异常处理

    Java异常处理 1 什么是异常 2 异常的处理机制的原理 过程 3 异常的体系结构 1 java lang Throwable 2 java lang Error 3 java lang Exception 4 异常的处理机制 1 抛 2

随机推荐

  • 以太坊区块链技术开发岗位面试题集锦，附答案

    2019独角兽企业重金招聘Python工程师标准 gt gt gt 超过100道以太坊区块链开发技术岗位的面试题 附参考答案 面试题目涵盖 以太坊的基本概念 Geth客户端使用 智能合约基本概念 Solidity开发语言 去中心化 应用DA

  • 目标检测中的IOU和CIOU原理讲解以及应用（附测试代码））

    上期讲解了目标检测中的三种数据增强的方法 这期我们讲讲目标检测中用来评估对象检测算法的IOU和CIOU的原理应用以及代码实现 交并比IOU 交并比IOU Interp over union 在目标检测任务中 我们用框框来定位对象 如下图定位

  • Linux文件/proc/net/tcp

    导语 proc net tcp文件提供了tcp的连接信息 是由net ipv4 tcp ipv4 c中的tcp4 seq show 实现信息打印的 本文内容来源于linux官方文档proc net tcp txt 官方文档解释 proc n

  • 输入框不能为空格

    需求 在表单中 输入的内容要去除两端空格 技术栈 vue elementui 最简单的做法 element ui 中自带的表单必填项校验输入空格时 依然能逃过验证 required true还是可以通过 需要再 在v model 加上 tr

  • 3.Jmeter学习_线程组（Thread Group）

    xxxx

  • VS2022安装qt插件

    1 安装Qt软件 Qt下载网址 5 14之后的需要手动编译 官方不提供exe文件 2 配置环境变量 3 安装插件 vs2022 qt vsaddin插件已经更新 可以下载安装 链接 https download qt io developm

  • 【正点原子STM32连载】第十七章 通用定时器中断实验 摘自【正点原子】APM32F407最小系统板使用指南

    1 实验平台 正点原子stm32f103战舰开发板V4 2 平台购买地址 https detail tmall com item htm id 609294757420 3 全套实验源码 手册 视频下载地址 http www openedv

  • python爬虫学习笔记-jQuery

    jQuery介绍 jQuery是什么 jQuery是一个快速 简洁的JavaScript框架 jQuery设计的宗旨是 write Less Do More 即倡导写更少的代码 做更多的事情 它封装JavaScript常用的功能代码 提供一

  • C# 集合

    数组是一种指定长度和数据类型的对象 在实际应用中有局限性 集合正是为这种局限性而生的 集合的长度能根据需要更改 也允许存放任何数据类型的值 集合简介 集合和数组比较类似 都用于存放一组值 但集合中提供了特定的方法直接操作集合中的数据 并提供

  • Java接口详解

    接口 接口的概念 在现实生活中 接口的例子比比皆是 比如 笔记本上的USB口 电源插座等 电脑的USB口上 可以插 U盘 鼠标 键盘等所有符合USB协议的设备 电源插座插孔上 可以插 电脑 电视机 电饭煲等所有符合规范的设备 通过上述例子可

  • OneNote复制为默认字体大小（只复制文字，不复制原有字体格式）

    当我们从word中复制一段文字到onenote中 onenote会自动带上原有字体的格式 非常不方便 下面是只复制文字的方法 1 随便按 ctrl c 复制一段文字 2 到onenote里按下 ctrl v 粘贴 选择右下角的框 3 在弹出

  • 使用XMind解决问题？只需4个简单步骤！

    我们每天都在解决问题并做出决定 从我应该穿什么到学校的小问题到如何找工作或上大学等等的问题 我们面临的问题可能或大或小 或简单或复杂 无论它是什么 我们都必须解决它 解决问题和决策是商业和生活的重要技能 我们生活中非常重要的一部分是找到解决

  • UE4_积分相同排名显示问题

    找了一下ue4 rank 函数相关 没找到合适的 自己简单写了个 解决积分相同时名次要一样 之后顺位排序 中国式排名 蓝图实现 c 原理一样 1 2 3 4 5

  • 编译 QT4.6.3 出现 derefIfNotNull 未定义 解决

    使用高版本的编译工具编译QT4 6 3 出现错误 derefIfNotNull 未定义 找到 RefPtr h文件 在WFT 的 public 里面增加 两个函数的定义 void derefIfNotNull T ptr if LIKELY

  • CS从头配置电脑清单（软件篇）

    CS从头配置电脑清单 软件篇 假设你电脑丢了 重新搞了一台 怎么从头配置 迅速可以进行高效产出 假设你是Linux ubuntu系统 安装zoom 安装slack 进行其他设备的信息发送 自己给自己发 项目交流 安装截图软件 推荐flame

  • 【Java】QueryWrapper方法解释

    继承自 AbstractWrapper 自身的内部属性 entity 也用于生成 where 条件 及 LambdaQueryWrapper 可以通过 new QueryWrapper lambda 方法获取 queryWrapper lt

  • 加解密

    目录 一 加密基础知识 1 加密函数 密钥 反函数 2 加密 解密 3 对称加密 4 非对称加密 公钥私钥 二 非对称加密 1 大素数分解问题类 1 RSA 2 Rabin 3 Pollard s rho 素数分解算法 2 离散对数问题类

  • 论文笔记-深度估计(5)Unsupervised Monocular Depth Estimation with Left-Right Consistency

    ECCV2016 Unsupervised Monocular Depth Estimation with Left Right Consistency 本文采用无监督学习 没有ground truth 的方法来估计深度 基本思路是匹配好左

  • Graph Neural Network-Based Anomaly Detection in Multivariate Time Series 代码配置及解析

    可以在GPU上跑通的代码 含数据集 我已经放到了以下链接 链接 https pan baidu com s 1gM4KTbRNHzfbGEGgvEjXAw 提取码 e7wu 在服务器上跑 先创建一个虚拟环境 conda create n G

  • 算法——B树，B-树，B+树，B*树全面解析笔记

    算法 B树 B 树 B 树 B 树全面解析笔记 https www cnblogs com lianzhilei p 11250589 html http blog codinglabs org articles theory of mys

热门标签