b 树是二叉树。1970 年,R.Bayer 和 E.mccreight 提出了一种适
用于外查找的树,它是一种平衡的多叉树,称为 B 树(或 B-树、B_
树)。在 B-树中查找给定关键字的方法是,首先把根结点取来,在
根结点所包含的关键字 K1,…,kj 查找给定的关键字(可用顺序查找
或二分查找法),若找到等于给定值的关键字,则查找成功;否则,
一定可以确定要查的关键字在某个 Ki 或 Ki+1 之间,于是取 Pi 所指
的结点继续查找,直到找到,或指针 Pi 为空时查找失败。
一棵 m 阶 B 树(balanced tree of order m)是一棵平衡的 m 路搜
索树。它或者是空树,或者是满足下列性质的树: