B树

定义

B树(多路平衡查找树)就是二叉排序树的一般化, 可以理解为M叉排序树

B树非常适合读取和写入相对较大的数据块(如光盘)的存储系统；它通常用于数据库和文件系统

• m阶B树满足条件：

  • 叶子结点指查找失败的结点(NULL结点)
  • 每个节点最多只有m个子结点
  • 非叶子结点(除了根结点)至少有$\lceil m/2\rceil$$\lceil m/2 \rceil$个分叉
  • 根结点最多有m棵子树，至少2个子树
  • 具有k个子结点的非叶子结点包含k-1个键
  • 所有的叶子结点都在同一层上（子树高度相同）

• B树性质：

  • 结点的孩子个数等于该结点中关键字个数+1

    • 

  • 如果根结点没有关键字就没有子树，此时B树为空

  • 根结点子树数$\in [2,m]$$\in [2, m]$, 关键字数$\in [1,m-1]$$\in [1, m-1]$

  • 其他结点子树数$\in [\lceil m/2\rceil ,m]$$\in [\lceil m/2 \rceil, m]$, 关键字数$\in [\lceil m/2\rceil -1,m-1]$$\in [\lceil m/2 \rceil -1, m-1]$

  • 结点中关键字从左到右递增有序，关键字两侧均有指向子树的指针，左边指针所指子树的所有关键字均小于该关键字，右边指针所指子树的所有关键字均大于该关键字

  • n个关键字的B树必有n+1个叶子结点，$n+1\ge 2(\lceil m/2\rceil {)}^{h-1}$$n+1 \ge 2(\lceil m/2 \rceil)^{h-1}$, 即$h\le lo{g}_{\lceil m/2\rceil }\frac{n+1}{2}+1$$h \le log_{\lceil m/2 \rceil}\frac{n+1}2+1$

• B树的高度

  • 大多数情况不包括叶子结点（失败结点）那一层
  • 包含n个关键字，阶数为m的B树
  • 树高$h\ge lo{g}_m(n+1)$$h \ge log_m(n+1)$

查找

现在b树上查找结点，然后在结点内查找关键字

与二叉排序树的查找相似（只是多了个结点内的查找，可以顺序查找或者折半查找）

插入

先往一个结点里放，放满了就把这个结点分成3个结点，中间的关键字作为父结点，中间关键字的左右两边分别作为左右子结点

• 在插入key后，若导致愿结点的关键字数超过上限，则从中间位置($\lceil m/2\rceil$$\lceil m/2 \rceil$) 将其中的关键字分为两部分，左部分包含关键字放在原结点中，右部分包含的关键字放到新结点中，中间位置($\lceil m/2\rceil$$\lceil m/2 \rceil$) 的结点插入原结点的父结点。如果导致父结点的关键字数也超过上限，则继续进行这种分裂操作，直到传到根结点

  • 

• 新元素一定是插入到最底层“终端结点”，用“查找”来确定插入位置

  • 

• B树的失败结点只能出现在最下边一层

  • 

• 子结点插满

  • 

• 子结点插满，父结点也插满

  • 

• 插入操作的核心要求

  • 对m阶B树，除根结点外，结点关键字个数$\lceil m/2\rceil -1\le n\le m-1$$\lceil m/2 \rceil - 1 \leq n \leq m - 1$
  • 子树0 < 关键字1 < 子树1 < 关键字2 < 子树2 < ····

删除

• 被删除关键字在终端结点

  • 直接删除

  • 需要注意结点关键字是否低于下限$\lceil m/2\rceil -1$$\lceil m/2 \rceil - 1$

  • 删除后低于下限

    • 右兄弟够借就用当前结点的后继、后继的后继依次顶替空缺

    • 左兄弟够借就用当前结点的前驱、前驱的前驱依次顶替空缺

    • 都不够借酒与父结点内的关键字、左(右)兄弟进行合并，合并后导致父结点关键字数量-1，可能需要继续合并

      • 

• 被删除关键字在非终端结点

  • 用直接前驱或直接后继来代替被删除的关键字

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

      • 

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

      • 

  • 使用直接前驱或直接后继结点代替后就转化为了对终端结点的删除操作

错题集

1. 

   答案与解析：

   
   答案： B D
   解析：
   3阶B树的分支结点最少有1个关键字，最多有2个关键字
   结点数量最少时，分支结点都只有1个关键字，也就是两个子结点，类似一棵满二叉树
   所以高度为5的B树至少有2^5-1=31个结点
   结点数量最多时，分支结点都有2个关键字，也就是3个子结点，类似满三叉树
   所以高度为5的B树最多有(3^5-1)/2=121个结点，这一行的公示是等比求和公式

2. 

   答案与解析：

   
   答案： B
   解析：
   结点满了先进行分裂再插入新结点