专栏首页老沙课堂数据结构与算法(十一)B树

数据结构与算法(十一)B树

B树

是一种平衡的多路搜索树,多用于文件系统、数据库的实现

•1个节点可以存储超过2个元素、可以拥有超过2个子节点•拥有二叉搜索树的一些特质(小的子节点在左面 大的子节点在右面)•平衡,每个节点的所有子树高度一致•比较矮

m阶B树性质

一个节点最多拥有m个子节点

•假设一个节点存储元素个数为x•根节点:1 <= x <= m-1 •非根节点:(ceiling(m/2) - 1) <= x <=m-1•如果有子节点 子节点个数为 y = x + 1•如果有子节点•根节点上的子节点:2 <= y <= m•非跟节点上的子节点:ceiling(m/2) <= x <= = m$

celing为向上取整

•如果要是m = 3 •他的子节点个数为2 <= y \<= 3,因此可称为(2,3)树、2-3树。•如果要是m = 4•他的子节点个数为2 <= y <= 4,因此可称为(2,4)树、2-3-4树。•如果要是m = 5•他的子节点个数为3 <= y <= 5,因此可称为(3,5)树、3-4-5树。

B树和二叉搜索树的关系

•B树其实适合二叉搜索树是等价的•只要把二叉搜索树和部分子节点与父节点结合就生成了b树•多代节点合并,可以获得一个超级节点•两代合并最多有4个子节点•m阶B树最多需要log{2^m}代合并

搜索

•1、现在节点内部从小到大搜索元素•2、如果命中,搜索结束•3、如果未命中,再去对应的子节点去搜索元素,重复步骤1

添加

元素必然是添加到叶子节点中

上溢

•假设3阶B树,当节点添加第三个数据的时候(最多添加两个) 叫上溢

假设B树的阶级为m, 上溢节点最中间的节点为k

•上溢的节点元素必然等于m

解决上溢

•将k位置的元素向上与父节点合并•将[0,k - 1]和[k + 1,m - 1]位置的元素分裂成两个子节点•这两个子节点的元素个数,必然都不会低于最低限制(ceiling(m/2) - 1)•一次分裂完毕后,可能导致父节点上溢,重复上述方法•最极端的情况是,一直上溢到根节点。

以4阶B树添加举例

删除

叶子节点

直接删除

非叶子节点

•找到前驱或者后继,覆盖删除所需要的元素的值。•在把前驱或者后继删掉。•非叶子节点的前驱或者后继必然在叶子节点中

下溢

•假设5阶B树,叶子节点最低个数为ceiling(m/2) - 1 = 2个 当删除后只剩下一个的时候 称为下溢

解决下溢:

•下溢的元素必然是ceiling(m/2) - 1 个•如果下溢的节点的临近兄弟节点至少有(ceiling(m/2))个元素,可以向其借一个元素(最后一个元素)•将父节点最后一个元素插入到下节点的最小位置•将借来的元素插入到父节点最小位置•如果下溢的节点的临近兄弟节点只有(ceiling(m/2)) - 1•将父节点的中间元素挪下来与左右子节点进行合并•合并后的节点元素等于ceil(m/2) + ceil(m/2) - 2; 不超过m - 1•可能导致父节点下溢,下溢可能一直向上传播。(如果根节点下溢 就和子节点合并)

以4阶B树删除举例

感兴趣的童鞋可以点击下面网址去看一下B书的操作动图

https://www.cs.usfca.edu/~galles/visualization/BTree.html

本文分享自微信公众号 - 老沙课堂(gh_f73a6b772d4f),作者:沙睿

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-10-16

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 数据结构与算法(十二) 红黑树

    •节点是有颜色的Red/Black•根节点必须是Black•叶子节点必须是Black•红黑树的叶子节点会自动将度为0 或者度为1的节点的度自动补充为2,补充的节...

    老沙
  • 数据结构与算法(六) 二叉树

    •每个节点的度最大为2。•左子树和右子树是有序的。•即使某个节点只有一颗子树,也要区分是左右子树。

    老沙
  • 数据结构与算法(九)二叉搜索树的删除操作

    •前驱节点:中序遍历时的前一个节点•如果左子树存在,从该节点的左子节点的最右的节点。•如果左子树 == null && 父节点!= null 父节点为父节点遍历...

    老沙
  • MongDB进阶系列——1.认识复制集

    从这一篇开始,我们要踏上MongoDB进阶之路啦,想想还有点小开心呢。一筐猪镇楼。

    陈琛
  • laya核心API五分钟速记

    大部分的laya UI组件都可以看做节点,可以看做web开发中,使用JavaScript对html节点进行操作。

    算法与编程之美
  • redis主从之全量复制及增量复制

    部署主从节点时需要考虑网络延迟、宽带使用率、防灾级别等因素,如要求低延迟时,建议同机房部署并关闭repl-disable-tcp-nodelay,如考虑容灾性,...

    gaobinzhan
  • 寻找红黑树的操作手册

    二叉树知识点回忆以及整理这篇文章中我们说过“二叉树是一个简单的二分查找,但其性能取决于二叉树的层数”。

    静默加载
  • Newick: tree文件格式简介

    Newick 是最常见的进化树文件格式,了解这种格式之前,有必要先掌握树状结构的构成。首先来看一个tree的示例

    生信修炼手册
  • 新手村:Redis 进阶篇三---主从复制

    前面几篇内容我们都是在一台 Redis 服务器上进行操作,包括数据的读、写以及备份操作。本篇要介绍的主从复制,是指将一台 Redis 服务器的数据,复制到其他 ...

    syy
  • 尝试手撕红黑树

    祖宗根节点必黑,允许黑连黑,不允许红连红;新增红色,爸叔通红就变色,爸红叔黑就旋。

    疯狂的KK

扫码关注云+社区

领取腾讯云代金券