B-tree 탐색(searching or Retrieval) 알고리즘

m-원 탐색 트리와 알고리즘은 동일하다.

(이진 탐색을 사용한다.)

 

※ Searhing 알고리즘

• (1) Pointer curr를 Tree의 Root노드에 지정한다.
• (2) curr 노드에서 왼쪽부터 오른쪽으로 record를 스캔한다. => if curr==NULL, retrun with fail(만약 curr노드가 NULL이면 실패한다.)
• (3) i=0;
• (3-1) if (i >= fill_cnt) { curr = P[i]; goto 2; } // 더이상 비교하지 않고 마지막 포인터를 사용한다.
• (3-2)
• (Case1) rec.key < skey : i = i++; go to (3-1) //다음 record를 스캔한다.
• (Case2) rec.key == skey : return with success //탐색 성공
• (Case3) rec.key > skey : curr = P[i]; goto 2; //go down to a child

ex) key값 45를 탐색한다고 하자.

---

★code

 

// retrieval.c

#include "functions.h"

void retrieval(nodeptr curr, char CompName[])
{
nodeptr temp_ptr = NULL;

int level = 1;

int i = 0;

do {
for (i = 0; i < curr->fill_cnt; i++) {
if (strcmp(CompName, curr->rec[i].name) < 0) {
break;
} // if (CompName)
else if (strcmp(CompName, curr->rec[i].name) == 0) {
printf("\t%s 레코드는\n", CompName);
printf("\t레벨%d에 위치하며 이 노드의 %d번째 레코드에 존재합니다.\n", level, i+1);
return;
} // else if (CompName)

} // for (i)

temp_ptr = curr->ptr[i];

if (temp_ptr) { curr = temp_ptr; level++; }

} while (temp_ptr);

printf("%s 레코드가 존재하지 않습니다.\n", CompName);
}