跳到主要内容

B 树和 B+ 树

B 树又称多路平衡查找树，是一种适合外存（磁盘）存取的多叉平衡树。

B 树的概念​

一棵 mm 阶 B 树满足：

  • 每个结点至多有 mm 棵子树
  • 根结点（若非叶子）至少有两棵子树
  • 除根结点外的所有非终端结点至少有 ⌈m/2⌉\lceil m/2 \rceil 棵子树
  • 终端结点（叶子结点）位于同一层

B 树中关键字按顺序排列，结点内关键字个数比子树个数少 1。

B 树的基本操作​

  • B 树的高度（决定磁盘存取次数）
  • B 树的查找
  • B 树的插入（结点分裂）
  • B 树的删除（结点合并）