파일구조의 b-tree 구현

소개

안녕하세요. 카쿵입니다.
자료 내용은 파일구조의 b-tree 구현 입니다.
소스파일과 레포트 파일입니다.
본문에는 함수에 대한 자세한 설명이 포함되어 있습니다.
그럼 평가글 부탁드리구요 앞으로도 컴퓨터 언어관련 자료는 [카쿵] 많이 찾아 주세요~

목차

1. 개요

2. 작업 환경

3. 프로그램 설명
3.1 설계
3.2 구현
3.3 함수 설명
3.4 에러 처리

4. 결과 및 Discussion

본문내용

1. 개요
B-Tree를 구현하고, 삽입, 삭제 과정을 진행하며 Tree의 구조가 어떻게 바뀌는가를 확인한다. B-Tree는 empty 상태의 Tree로 시작하며 input.txt 파일을 읽어 파일 내의 key들을 차례로 B-Tree에 삽입하고, 마지막의 10개의 key를 삭제한다. 삽입과 삭제의 작업을 진행하며 각각의 작업이 수행된 후의 B-Tree의 상태를 파일에 출력한다.
Key 값을 삭제할 경우에는 left node에 있는 predecessor와 교환한 후 삭제를 수행하며, node에 underflow가 발생했을 경우에도 left sibling node를 먼저 검사하여 재분배를 처리하도록 한다. 합병의 경우에도 마찬가지로 left sibling node를 먼저 검사하여 합병을 처리하도록 한다.

B-Tree는 차수가 5인 B-Tree를 구현하는 것이 과제의 spec이나 좀더 범용적으로 사용이 가능하도록 m차 B-Tree를 구현하도록 한다. 삽입과 삭제도 input 파일에 30개의 key를 지정해서 삽입하고, 뒤의 10개의 key를 삭제하는 것이 과제의 spec이나 입력되는 key의 개수도 30개 이상의 key에 대해서도 처리가 가능하고, 마찬가지로 삭제의 경우에도 10개 이상의 key에 대한 삭제가 가능하도록 하였다. 현재 까지의 3개의 옵션은 source code의 preprocessor로 선언해놓았고, 이를 수정하면 여러가지 경우에 대한 처리가 가능하다. 즉, source code에서 아래와 같이 선언되어 있는 preprocessor의 값을 변경해 주면 된다.

#define DEGREE 5 /* b-tree의 차수 */
#define MAX_ELEMENTS 1000 /* 입력되는 key의 개수의 상한 지정 */
#define DELETE_COUNT 10 /* 삭제시 빼줄 element 개수 */

위에서 DEGREE의 값을 변경해 주면 임의의 차수의 B-Tree를 생성하여 처리하고, MAX_ELEMENTS의 값을 변경해 주면 해당 개수만큼의 입력에 대한 처리가 가능하며, 마찬가지로 DELETE_COUNT의 값을 변경해 주면 input 파일의 뒷부분에서 해당 개수만큼 삭제를 진행한다.
출력의 경우에는 Post-order를 기본으로 하여 출력하며, 각 node 간의 구분이 용이하도록 leaf node에 대해서는 node 내의 key 값 좌우에 [, ]를 표시해 주었다. [, ]로 구분된 영역 이외의 경우에는 post-fix expression을 해석하는 과정과 동일하게 해석하면 된다. 즉, 두 개의 leaf node를 묶어 바로 다음에 나오는 parent key에 연결해 주면 된다.
따라서, 다음과 같은 출력이 나왔다면

참고자료

· 없음