§9.32B树 1概念 B树是一种完全平衡的多阶查找树,主要是作为磁盘文件的索引组织,用于 外部查找。 ■基本想法是增大结点来降低树高,减少访问外存的次数 棵m阶B树,每个结点最多有m个孩子,m一般为50-2000 例如,1棵1001阶B树,3层即可包含10亿以上的Keys,当根结点置于内存 时,查找任一Key至多只要访问2次外存。 1000 1个结点 1000个关键字 1001 10001000 1000 1001个结点 1,001,000个关键字 量B 1001 1000 1000 10011,002,001个结点 1,002,001,000个关键字
1 § 9.3.2 B-树 1.概念 ◼ B-树是一种完全平衡的多阶查找树，主要是作为磁盘文件的索引组织，用于 外部查找。 ◼ 基本想法是增大结点来降低树高，减少访问外存的次数 一棵m阶B-树，每个结点最多有m个孩子，m一般为50－2000 例如，1棵1001阶B-树，3层即可包含10亿以上的Keys，当根结点置于内存 时，查找任一Key至多只要访问2次外存。 1000 1000 1000 1000 1000 1000 … 1001 … 1001 … 1001 1个结点 1000个关键字 1001个结点 1,001,000个关键字 1,002,001个结点 1,002,001,000个关键字
§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
d 24 b 3334853 d e 2人10A20人1人20 f2△8人的1△国∧37人国5人 i56人 棵包含13个关键字的4阶B树
3 g f d e b c a 1 24 1 15 1 ∧ 20 ∧ 2 ∧ 28 ∧ 31 ∧ 2 ∧ 10 ∧ 20 ∧ 1 ∧ 56 ∧ 1 ∧ 37 ∧ 1 ∧ 50 ∧ 3 33 48 53 i h 一棵包含13个关键字的4阶B_树
§9.32B树 运算 ■查找 多路查找:先在结点内查找(折半或顺序),后在子结点中 查找(读盘) ■插入和生成 平衡机制:满时插入分裂结点,从叶子一根,树高可能长 层 ■删除 平衡机制:半满时删除,可能要合并结点,从叶子一根, 树高可能减一层
4 § 9.3.2 B-树 运算 ◼ 查找 多路查找：先在结点内查找（折半或顺序），后在子结点中 查找（读盘） ◼ 插入和生成 平衡机制：满时插入分裂结点，从叶子 根，树高可能长 一层 ◼ 删除 平衡机制：半满时删除，可能要合并结点，从叶子 根， 树高可能减一层
根据m阶B_树的定义,结点的类型定义如下: # define m5∧根据实际需要定义B树的阶数* typedef struct BTNode int keynum;/结点中关键字的个数 struct BTNode * parent;/指向父结点的指针 Key type key[M+1];/关键字向量keyo]未用 struct btnode*ptrM+1];/子树指针向量 RecType e recptr[M+1 /记录指针向量, recptoR0未用*/ JBTNode
5 根据m阶B_树的定义，结点的类型定义如下： #define M 5 /* 根据实际需要定义B_树的阶数 */ typedef struct BTNode { int keynum ; /* 结点中关键字的个数 */ struct BTNode *parent ; /* 指向父结点的指针 */ KeyType key[M+1] ; /* 关键字向量,key[0]未用 */ struct BTNode *ptr[M+1] ; /* 子树指针向量 */ RecType *recptr[M+1] ; /* 记录指针向量,recptr[0]未用 */ }BTNode ;