B树和B+树脑图思维导图

生杀予夺

2023-12-07

浏览量: 3

数据结构

编程算法

数据查找

B树和B+树数据结构相关内容分解

树图思维导图提供《B树和B+树脑图》在线思维导图免费制作，点击“编辑”按钮，可对《B树和B+树脑图》进行在线思维导图编辑，本思维导图属于思维导图模板主题，文件编号是：180fc8cf3b0d01b571d349d1eb0b6594

思维导图大纲

m阶B树核心特性

根节点的子树数∈[2，m]，关键字数∈[1，m-1]

其他节点的子树数∈[⌈m/2⌉，m]，关键字数∈[⌈m/2⌉-1，m-1]

任意节点，所有子树高度均相同

满足左＜中＜右

总叶结点数 = 总关键字数 + 1

对n个关键字的m阶B树，高度h满足：

最小高度

最大高度

高度为h的m阶B树

结点最少：类似于满⌈m/2⌉叉树，但是根节点最少可以2个分支

结点最多：满m叉树

以上所说高度都不算叶子节点（失败结点）

以5阶B树为例

注意失败节点 = 叶子节点，最下层非空结点 = 终端节点

915中对B树的考查

2-3树就是3阶B树

2-3-4树就是4阶B树

B树插入和删除

插入

通过“查找”确定插入位置，一定在终端节点

插入后若关键字个数超过上限：将中间元素放入父节点中，当前结点分裂为左右2个部分

若父节点也超过上限了，继续向上分裂；根节点的分裂会导致B树高度+1

删除

非终端结点关键字

用直接前驱 or 直接后继代替其，转化为删除直接前驱 or 直接后继

直接前驱：当前关键字左边指针所指子树中“最右下”的元素

直接后继：当前关键字右边指针所指子树中“最左下”的元素

终端结点关键字

删除后检查结点数是否低于下限

低于下限

左兄弟够借：由当前节点的父节点来顶替，再由父节点的直接前驱顶替父节点

右兄弟够借：由当前节点的父节点来顶替，再由父节点的直接后继顶替父节点

左右兄弟都不够借：由当前节点、父节点中的关键字、左（右）兄弟合并成一个顶点，合并到自己这里；若父节点还是低于下限，如法炮制合并父节点

B树删除的例子

删除非终端结点：用直接前驱/后继来顶替

用直接后继来顶替

删除终端节点

右兄弟够借——上图删除38

父节点顶替被删，父节点的后继顶替父节点

左兄弟够借——上图删除90

父节点顶替被删，父节点的前驱顶替父节点

兄弟不够借——上图删除49

当前结点、父节点、兄弟节点合并到自己这里

父节点受到影响，也低于下限：继续合并父节点

m阶B+树

根节点的子树数∈[⌈m/2⌉，m]，关键字数∈[⌈m/2⌉，m]，只有1个节点是叶不是根

其他分支节点的子树数∈[⌈m/2⌉，m]，关键字数∈[⌈m/2⌉，m]

结点子树个数 = 关键字个数（与B树不同）

所有叶结点包含全部关键字及指向相应记录的指针，叶结点有序并连接起来（支持顺序查找）

所有分支节点仅包含它的各子节点中关键字的最大值及指向子节点的指针（仅起到索引作用）

4阶B+树举例

B树与B+树区别和联系

不同点和相同点

B+树用于文件索引和数据库索引，B树也可用于索引

B树不支持顺序查找，只支持随机查找；B+树都支持

B树关键字不重复；B+树重复

B树动态查找效率高

3A Unit 1 A Proper Job思维导图

U237990653

2.11

树图思维导图提供《3A Unit 1 A Proper Job》在线思维导图免费制作，点击“编辑”按钮，可对《3A Unit 1 A Proper Job》进行在线思维导图编辑，本思维导图属于思维导图模板主题，文件编号是：8d966446cda22e33b426cba15d3d981e

SpringBootWeb请求响应思维导图

U482218638

3.9

树图思维导图提供《SpringBootWeb请求响应》在线思维导图免费制作，点击“编辑”按钮，可对《SpringBootWeb请求响应》进行在线思维导图编辑，本思维导图属于思维导图模板主题，文件编号是：1c6ee1ff958a0c7c2fabdf9e9f8d755e

思维导图模板

IT互联网

产品结构

正文

相似思维导图模版

思维导图模版推荐

首页

我的文件

我的团队

个人中心

B树和B+树脑图思维导图

思维导图大纲

相关思维导图模版

﻿m阶B树核心特性

﻿B树插入和删除

﻿B树删除的例子

m阶﻿B+树