计算机知识B树及其基本操作思维导图
简单介绍B树及其基本操作的内容
树图思维导图提供 计算机知识B树及其基本操作思维导图 在线思维导图免费制作，点击“编辑”按钮，可对 计算机知识B树及其基本操作思维导图 进行在线思维导图编辑，本思维导图属于思维导图模板主题，文件编号是：b4e64390b9db14e6a2932e3c5d543926
思维导图大纲
B树及其基本操作思维导图模板大纲
又称多路平衡查找树，B树中的所有结点的最大孩子结点数称为B数的阶
m阶B树
树中每个结点至多有m棵子树、至多有m-1个关键字
若根结点不是终端结点，则至少有两棵子树
除了根结点外的所有非叶结点至少有[m/2]↓棵子树
结点n的关键字个数：[m/2]↓-1<= n <= m-1
所有叶子结点都在同一层次上
所有结点的平衡因子都为0
B树的高度
B树中的大部分操作所需的磁盘存取次数与B树的高度成正比
n>=1,对任意一棵包含n个关键字，高度为h，阶数为m的B树，有如下性质：
关键字的个数满足：n <= m^h - 1
树的高度满足：h>=logm（n+1）
若让每个结点关键字最少，则容纳同样关键字的树的高度达到最大，高度范围太复杂。看书……
基本操作
查找
①在B树中找结点 ②在结点中找关键字
B树常存储在磁盘，因此查找①在磁盘进行
找到目标结点后放入内存，在内存中找对应关键字（顺序查找/折半查找）
若结点内没有对应的关键字则查找失败
插入
②插入
插入结点后结点的关键字数小于等于m-1（m为阶数），直接插入
若结点关键字数大于m-1，必须对结点进行分裂
①定位
一定要插入树中最底层的非结点内
删除
在终端结点
直接删除
兄弟够借
兄弟不够借
不在终端结点
直接删除
删除后合并
相关思维导图模板
树图思维导图提供 RBT工作管理计划 在线思维导图免费制作，点击“编辑”按钮，可对 RBT工作管理计划 进行在线思维导图编辑，本思维导图属于思维导图模板主题，文件编号是：07511cf9c98d75f4a7a974d65f912b8f
树图思维导图提供 Li River--Beautiful Water and Mountains 在线思维导图免费制作，点击“编辑”按钮，可对 Li River--Beautiful Water and Mountains 进行在线思维导图编辑，本思维导图属于思维导图模板主题，文件编号是：690a608b69a3b300c4507d9cae90acde
沪公网安备 31011502019485号
上海工商