S9.3.2B-树 §9.3.2B-树 1景老 ■定义：一裸m(m≥3)阶的B制是清足下述性质的m叉制： ·B是一种完全平衡的多阶找，主要是作为盘文并的引组织，用于 s性质1：每个轴点至少包含下列放据媒：0，P。,K,P,K2…,K,P】 外都查找， j:keys总数，K:关输字，P:指针 ■燕本想法是增大结点来韩低树高，减少访问外存的次数 keys(Po)<K <keys(P)<K2<...<Kj<keys(P) 一操m阶B制，每个纳点量多有m个孩子，m一般为50一2000 ◆性重2所有叶子在同一展上，叶子展数为树高，叶子中的指针为空. 警宝是博二设特吃双上o音银储在于内有 ◆性质3，每个非视结点中的关输字数目满足 1个纳点 「m127-1≤j≤m-1 1000 1000个关轴字 即：每个非根的内部结点的子材数在m和「m/2之间 ◆性质4：非空的B一制中，根至少有1个关黄字。 1000 001 1000 1000 1001个结点 1,001,000个关幢字 即：根不是叶子时，子制数为：2一m之间 001 1001 1000 1000 1,002,001个结点 1,002,001,000个关字 24▣ S9.3.2B树 115 3圆334853 运算 2A10A20入 ■查找 1A20A 2A28A面囚△37△A50囚 多路查找：先在结点内查找（折半或顺序），后在子结点中查 找（读盘） d0A56 一裸包含13个关键字的阶B别 =插入和生成 平衡机制：满时插入分到结点，从叶子之根，树高可能长 一层 ■除 平衡机制：半满时测除，可能要合并结点，从叶子根 树高可能减一层 根据m阶B树的定义，结点的类型定义如下： 2B树的查找 #define M5P根据实际需要定义B树的阶数 由B树的定义可知，在其上的查找过程和二叉排序 typedef struct BTNode 树的查找相似。 {int keynum;严结点中关键字的个数*/ (1)算法思想 struct BTNode*parent;r指向父结点的指针y KeyType key[M+1];P关键字向量，key[0]床用y ①从树的根结点T开始，在T所指向的结点的关键字 向量key1..keynum]中查找给定值K(用折半查找)： struct BTNode*ptr[M+1];P子树指针向量 RecType *recptr[M+1]: 若keyd=K(1≤i≤keynum),则查找成功，返回结点 产记录指针向量，recptr[0]未用I 及关键字位置：否则，转2) ②将K与向量key[1..keynum]中的各个分量的值进 )BTNode; 行比较，以选定查找的子树： ◆若K<key1小：T-T->ptr0 11 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个关键字 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 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_树 4 § 9.3.2 B-树 运算 „ 查找 多路查找：先在结点内查找（折半或顺序），后在子结点中查 找（读盘） „ 插入和生成 平衡机制：满时插入分裂结点，从叶子 根，树高可能长 一层 „ 删除 平衡机制：半满时删除，可能要合并结点，从叶子 根， 树高可能减一层 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 ; 6 2 B_树的查找 由B_树的定义可知，在其上的查找过程和二叉排序 树的查找相似。 ⑴ 算法思想 ① 从树的根结点T开始，在T所指向的结点的关键字 向量key[1…keynum]中查找给定值K(用折半查找) ： 若key[i]=K(1≤i≤keynum)，则查找成功，返回结点 及关键字位置；否则，转⑵； ② 将K与向量key[1…keynum]中的各个分量的值进 行比较，以选定查找的子树： ◆ 若K<key[1]：T=T->ptr[0]；