当前位置: 首页 > news >正文

B树系列解析

在这里插入图片描述

  • 我最近开了几个专栏,诚信互三!
    ====> |||《算法专栏》::刷题教程来自网站《代码随想录》。|||
    ====> |||《C++专栏》::记录我学习C++的经历,看完你一定会有收获。|||
    ====> |||《Linux专栏》::记录我学习Linux的经历,看完你一定会有收获。|||
    ====> |||《C#专栏》::记录我复习C#的经历,深度理解查漏补缺,不定期更新。|||
    ====> |||《计算机网络专栏》::记录我学习计算机网络,看完你一定会有收获。|||

    ====> |||《mysql数据库》::记录我学习数据库,看完你一定会有收获。|||

B树系列解析

  • B树的优势
  • B树的结构
    • B树的增加
  • B+树的结构
    • B+树的插入
  • B*树了解

B树的优势

B树系列都擅长外查询,及查询磁盘中的数据,B树都是一棵多叉树,对于二叉搜索树来说,查询到一个结点的时间复杂度位logN,而一颗B树,查询都一个结点的时间复杂的位logM^N,着两者在内存级别时,差别不大,但是在磁盘级别能节约多次磁盘IO的时间,从而大大加快查询的速度。
因此,该数据结构常常用于需要大量进行磁盘IO的情况,如文件系统以及数据库的索引

B树的结构

B树满足以下几点要求,假设这是一颗M叉树。
1).B树的根结点至少有两个孩子。
2).B树的每个结点要有k个孩子和k-1个关键字,up(M/2)<=k<=M。
3).叶子结点没有孩子只有关键字。
4).B树关键字的左孩子的关键字比当前关键字都小,右孩子关键字比当前关键字大。
在这里插入图片描述
B树在设计结构的时候,我们往往会多设计一个关键字结点和孩子结点,这样好判断分裂的情况。

B树的增加

B树插入值时,是插入到叶子结点,此时有两者情况。
1).叶子结点没满,则直接插入。
2).叶子结点满了,则会进行分裂,将结点的关键字的二分之一拷贝到另一个结点,以及其所对应的孩子,同时提取第一个结点的中位数,加入到父节点,让两个结点连接到父节点的中位数下。
在这里插入图片描述
更具上述对于B树的插入描述,可知,B树是向右,向上成长的,所以B树天然平衡

B+树的结构

B+树是B树的新版本,也是mysql中索引使用的数据结构,它相较于B+树存在一些优势。
1).结构更简单,B+树有K个关键字和K个孩子,K[i]号关键字的孩子C[i]比K[i]大,C[i - 1]比K[i]小。
2).B+树的所有插入的值都在叶子结点,叶子结点通过指针相互连接起来。
3).综上,B+树的分支结点存的是索引,而不是值。
4).B+树遍历查询十分方便,所以查询某个范围的值效率高。
在这里插入图片描述
B+树也是向右向上生长,所以也天然平衡。

B+树的插入

B+树插入值时,需要先分裂一个结点,插入情况如下。
在这里插入图片描述
插入第一个结点,需要先分裂一个,随后每次插入都往叶子结点插入。
如果插入的结点小于叶子结点的最小值,则需要更新父节点的关键字,如果满了,则直接分裂一半关键字和孩子,不需要提取中位数,直接将第二个结点的最小值付给父节点的关键字。

B*树了解

B*树是对B+树的一次优化,以减少B+树的空间浪费
插入关键字导致结点满了后,将该结点给兄弟结点,如果兄弟结点也满了,则两个结点各自分出1/3给一个新结点。

http://www.lryc.cn/news/453178.html

相关文章:

  • docker 部署 WEB IDE
  • 【Android】数据存储
  • 个人网络安全的几个重点与防御
  • python爬虫 - 初识爬虫
  • tomcat版本升级导致的umask问题
  • Golang | Leetcode Golang题解之第455题分发饼干
  • vscode+stfp插件,实现远程自动同步文件代码
  • python 实现djb2哈希算法
  • 文件夹作为普通文件而非子模块管理
  • 7c结构体
  • 浅聊前后端分离开发和前后端不分离开发模式
  • RabbitMQ篇(死信交换机)
  • HBase 的 MemStore 详解
  • 【嵌入式软件-数据结构与算法】01-数据结构
  • Windows应用开发-解析AVI视频文件
  • 探索TCP协议的奥秘:Python中的网络通信
  • 每日学习一个数据结构-树
  • 简单PCL库读文件(linux vscode编译)
  • 【自动驾驶】最近计划看的论文
  • vue3学习:axios输入城市名称查询该城市天气
  • 影刀RPA实战:Excel拆分与合并工作表
  • STM32三种启动模式:【详细讲解】
  • Ray_Tracing_The_Next_Week
  • DBT hook 实战教程
  • SpringBoot整合JPA详解
  • 【微服务】springboot 实现动态修改接口返回值
  • 【前端开发入门】html快速入门
  • python配置环境变量
  • 从0到1:培训机构排课小程序开发笔记一
  • 方法重载(Overload)