§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 ;
2B树的查找 由B树的定义可知,在其上的查找过程和二叉排序 树的查找相似。 (1)算法思想 ①从树的根结点T开始,在T所指向的结点的关键字 向量key1… keynum中查找给定值K(用折半查找) 若key]=K(1 pt0];
6 2 B_树的查找 由B_树的定义可知，在其上的查找过程和二叉排序 树的查找相似。 ⑴ 算法思想 ① 从树的根结点T开始，在T所指向的结点的关键字 向量key[1…keynum]中查找给定值K(用折半查找) ： 若key[i]=K(1≤i≤keynum)，则查找成功，返回结点及 关键字位置；否则，转⑵； ② 将K与向量key[1…keynum]中的各个分量的值进 行比较，以选定查找的子树： ◆ 若Kptr[0]；
◆若keyKptrI ◆若K> keylkeynum:T=T-> ptr keynum; 转①,直到T是叶子结点且未找到相等的关键字,则 查找失败。 (2)算法实现 int BT search(BTNode *T, Keytype K, BTNode * p) /在B树中查找关键字K,查找成功返回在结点中的位置 /及结点指针p;否则返回0及最后一个结点指针* i BtNode *q; int n p=g=T
7 ◆ 若key[i]ptr[i]； ◆ 若K>key[keynum]：T=T->ptr[keynum]； 转①，直到T是叶子结点且未找到相等的关键字，则 查找失败。 ⑵ 算法实现 int BT_search(BTNode *T, KeyType K, BTNode *p) /* 在B_树中查找关键字K, 查找成功返回在结点中的位置 */ /* 及结点指针p; 否则返回0及最后一个结点指针 */ { BTNode *q ; int n ; p=q=T ;
while ql=NULL p=q;q->key0]=K;/设置查找哨兵 for(n=g->keynum Kkeyn]; n-- if(n>0&&EQ(g->keyn], K))return n g=q->porn return O (3)算法分析 在B树上的查找有两中基本操作 ◆在B_树上查找结点(查找算法中没有体现)
8 while (q!=NULL) { p=q ; q->key[0]=K ; /* 设置查找哨兵 */ for (n=q->keynum ; Kkey[n] ; n--) if (n>0&&EQ(q->key[n], K) ) return n ; q=q->ptr[n] ; } return 0 ; } ⑶ 算法分析 在B_树上的查找有两中基本操作： ◆ 在B_树上查找结点(查找算法中没有体现)；
◆在结点中查找关键字:在磁盘上找到指针pt所指 向的结点后,将结点信息读入内存后再查找。因此, 磁盘上的查找次数(待查找的记录关键字在B树上的 层次数是决定B树查找效率的首要因素 根据m阶B_树的定义,第一层上至少有个结点, 第二层上至少有2个结点;除根结点外,所有非终端结 点至少有m棵子树,…,第h层上至少有m/2h2个 结点。在这些结点中:根结点至少包含1个关键字,其 它结点至少包含m211个关键字,设S=m/2,则总的 关键字数目n满足: n≥1+(-1)242=1+2(1)S1=231 S-1
9 ◆ 在结点中查找关键字：在磁盘上找到指针ptr所指 向的结点后，将结点信息读入内存后再查找。因此， 磁盘上的查找次数(待查找的记录关键字在B_树上的 层次数)是决定B_树查找效率的首要因素。 根据m阶B_树的定义，第一层上至少有1个结点， 第二层上至少有2个结点；除根结点外，所有非终端结 点至少有m/2棵子树，…，第h层上至少有m/2 h-2个 结点。在这些结点中：根结点至少包含1个关键字，其 它结点至少包含m/2-1个关键字，设s=m/2，则总的 关键字数目n满足： n≧1+(s-1)∑ 2si-2=1+ i=2 h =2sh-1 -1 s-1 s h-1 -1 2(s-1)
因此有:h三1+log(an+1)2)=1+ogm21(n)/2) 即在含有n个关键字的B树上进行查找时,从根结 点到待査找记录关键字的结点的路径上所涉及的结点数 不超过1+logm21(n+1)2)
10 因此有： h≦1+ ㏒s ((n+1)/2)=1+㏒m/2((n+1)/2) 即在含有n个关键字的B_树上进行查找时，从根结 点到待查找记录关键字的结点的路径上所涉及的结点数 不超过1+ ㏒m/2((n+1)/2)