0%

B-树简介

B-树简介

B-树,也称为B树,是一种平衡的多叉树(可以对比一下平衡二叉查找树),它比较适用于对外查找

  • 阶数:一个节点最多有多少个孩子节点。(一般用字母m表示)
  • 关键字:节点上的数值就是关键字
  • 度:一个节点拥有的子节点的数量

特点

  • 根结点至少有两个子女
  • 每个非根节点所包含的关键字个数 j 满足:⌈m/2⌉ - 1 <= j <= m - 1.(⌈⌉表示向上取整)
  • 有k个关键字(关键字按递增次序排列)的非叶结点恰好有k+1个孩子
  • 所有的叶子结点都位于同一层