B-tree 구현 (C언어 구현)

※B-tree 개발

B-tree.zip

0.43MB

• 내용
B-tree 프로그램을 구현하고 실험한다. 주어진 데이타를 B-tree 에 모두 저장하고, 여기의 레코드를 탐
색, 삭제 해 보는 작업을 실험해 본다. B-tree 노드의 capacity order d 는 다음처럼 상수로 선언되도록
하고 이 d 를 이용하여 모든 변수의 타입을 선언하도록 하고 프로그램에서도 이 d 를 이용토록 한다.
(capacity order d = 2 로 해서 실험 해 볼 것).
• 삽입할 데이타는 두 개의 텍스트 화일 Com_names1.txt , Com_names2.txt 에 들어 있는 업소명들
이다. 하나의 업소명은 하나의 레코드에 저장된다. 레코드는 업소명의 문자열과 업소명의 길이의 두 개
의 필드를 가지며 다른 필드는 없다. 따라서 하나의 레코드의 정의는 다음과 같다:
typedef struct _rec {
char name[COMP_NAME_LEN - 1]; // key value
int leng;
} type_rec;

• 주의: 이 과제에서 key 값은 이름 즉 문자열이다. 문자열 간의 비교는 사전식 순서에 의거하여 비교
하도록 한다 (strcmp 함수 사용).

• 작업 수행 순서:
(1) 저장 단계:
 주어진 두 개의 업소명 화일안의 모든 업소명을 B-tree 에 저장한다 (주: 중복으로 저장되지 않도
록 한다). 방법은 하나의 업소명을 저장하는 함수 B_tree_Insertion 을 작성하고 이를 반복적으로
호출하여 모든 업소명을 저장하도록 한다. 이 함수에 대한 파라메타는 문자열 변수 CompName 이
다. 문자열의 전체 길이는 51(COMP_NAME_LEN) 로 한다. 이 함수는 입력으로 받은 문자열에 대
하여 레코드를 만들고 이 레코드를 B-tree 에 삽입한다.

(2) 테스트 단계:
 프로그램을 실행하면 먼저 주어진 데이터 파일 2개 안의 모든 줄의 상호명을 b-tree 에 삽입하는
단계를 수행한다. 그 다음 단계에서는 특정 레코드의 삽입(insertion), 탐색 (retrieval), 삭제
(deletion), 순차출력(sequential printing) 에 대하여 실험한다. 
각 명령마다 함수 하나를 대응하도록 개발한다.

순차출력: 저장된 모든 레코드들은 키의 오름차순으로 모두 출력하는 것이다 (한 줄에 한 레코드 출력).
실험 예시)
명령을 넣으라는 프롬프트 "Command?" 에 대하여 해당 작업을 수행하는 루프를 반복한다.
 Command? r 기산 식당 : 해당 이름을 찾은 다음 발견된 위치(레벨 및 레코드 내의 위치) 출력.
 Command? d 기산 식당 : 해당 이름을 제거한 다음 성공 여부를 출력한다 (그리고 이 과정에서
발생한 redistribution의 총 수, merging 의 총 수도 출력한다).
 Command? sp : B-tree 안의 모든 레코드의 이름순으로 SeqData.txt 화일에 출력한다.
 Command? i 연세생협 : 주어진 상호명을 가지는 레코드를 만들어 b-tree 에 삽입한다. 출력은
삽입과정에서 발생한 split 의 총수를 출력한다.
 Command? exit : 프로그램을 종료한다.

실행 결과

SeqData.txt