2B树的查找 由B树的定义可知,在其上的查找过程和二叉排序 树的查找相似。 (1)算法思想 ①从树的根结点T开始,在T所指向的结点的关键字 向量key1… keynum中查找给定值K(用折半查找) 若key]=K(1 <iskeynum,则查找成功,返回结点及 关键字位置;否则,转(2); ②2将K与向量key1. keynum]中的各个分量的值进 行比较,以选定查找的子树 ◆若K<key1:T=T->pt0];
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]；
◆若keyK<key+1](=1,2,… keyne-1): T=T->ptrI ◆若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]<K<key[i+1](i=1, 2, …keynum-1)： T=T->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 K<q->keyn]; 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 ; K<q->key[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)