B树（多路查找树）

B树（B-tree）是一种平衡的多路查找树。节点最大的孩子数目称为B树的阶（order）

B树的结构

  • 如果根节点不是叶子节点，则其至少有两棵子树
  • 每一个非根节点的分支节点都有k-1个元素和k个孩子，其中[m/2]<= k <="m.每一个叶子节点n都有k-1个元素，其中[m/2]<= k <="m
  • 所以叶子节点都位于同一层次
  • 所有分支节点包含下列信息数据（n，A0,K1,A1,K2….,Kn，An）为关键字