§9.32B树 ■定义:一棵m(m23阶的B树是满足下述性质的m叉树: 冷性质1:每个结点至少包含下列数据域:(PonK1,PK2y…,K,P) j:keys总数,K1:关键字,P:指针 keys(Po)<K,keys(P1)<K2<.<Ki< keys(Pj) 今性质2:所有叶子在同一层上,叶子层数为树高h,叶子中的指针为空。 分性质3:每个非根结点中的关键字数目满足: 「m/21-1≤j≤m-1 即:每个非根的内部结点的子树数在m和「m/2之间 性质4:非空的B一树中,根至少有1个关键字。 即:根不是叶子时,子树数为:2~m之间2 § 9.3.2 B-树 ◼ 定义：一棵m(m≥3)阶的B-树是满足下述性质的m叉树： ❖ 性质1：每个结点至少包含下列数据域：(j,P0 , K1 , P1 , K2 , … , Kj , Pj ) j：keys总数， Ki：关键字，Pi：指针 keys(P0 ) < K1 <keys(P1 ) < K2 < … < Kj < keys(Pj ) ❖ 性质2：所有叶子在同一层上，叶子层数为树高h，叶子中的指针为空。 ❖ 性质3：每个非根结点中的关键字数目j满足： 即：每个非根的内部结点的子树数在m和 之间 ❖ 性质4：非空的B－树中，根至少有1个关键字。 即：根不是叶子时，子树数为：2～m之间  m/ 2 −1 j  m−1 m/ 2