数据结构【DS】B树

m阶B树的核心特性:

Q：根节点的子树数范围是多少？关键字数的范围是多少？

A：根节点的子树数∈[2, m],关键字数∈[1, m-1]。

Q：其他结点的子树数范围是多少？关键字数范围是多少？

• 
• 

Q：对任一结点，其所有子树高度有什么特点？

• 都相同

Q：关键字的值的大小关系是什么样的？

• 关键字的值：类比二叉查找树：左<中<右

 

Q：含 n 个关键字的 m 阶 B 树，最小高度、最大高度是多少?

• 
  • 
  • 

• 最小高度：
  • 
  • 
  • 
• 最大高度：
  • 让各层的分叉尽可能的少
  • 
  • 
  • 
  • 
  • 
  • 

Q：对于高度为 2 的 5 阶 B 树所含关键字的个数最少是多少？

A：根结点只有达到 5 个关键字时才能产生分裂, 成为高度为 2 的 B 树 ，因此高度为 2 的 5 阶 B 树所含关键字的个数最少是 5 。

B树的插入和删除

插入

• 通过“查找”确定插入位置(一定是在终端结点插入)
• 若插入后结点关键字个数未超过上限，则无需做其他处理
• 若插入后关键字个数超过上限，则需要将当前结点的中间元素放到父节点中，当前结点分裂为两个部分;
• 该操作会导致父节点关键字个数+1,若父节点关键字个数也超过了上限，则需要再向上分裂;根节点的分裂会导致B树高度+1。

Q：B树裂开的时候从哪开始裂？

删除

• 非终端结
  • 用其直接前驱或直接后继替代其位置，转化为对“终端结点”的删除点关键字.
  • 直接前驱：当前关键字左边指针所指子树中“最右下”的元素
  • 直接后继：当前关键字右边指针所指子树中“最左下”的元素
  • 删除后结点关键字个数未低于下限，无需任何处理
• 终端结点
  • 右兄弟够借，则用当前结点的后继、后继的后继依次顶替空缺
  • 左兄弟够借，则用当前结点的前驱、前驱的前驱依次顶替空缺
  • 左(右)兄弟都不够借，则需要与父结点内的关键字、左(右)兄弟进行合并。合并后导致父节点关键字数量-1，可能需要继续合并。