5차 B+ 트리 (B플러스 트리) 구현

소개글

5차 B+ 트리 (B플러스 트리) 구현에 대한 보고서 자료입니다.

목차

1. 과제 설명

2. 프로그램 설명
-함수 설명
-프로그램 동작 환경 및 실행 방법 설명
-프로그램 실행 캡쳐 사진 첨부

3. 프로그램 소스 분석 및 첨부

본문내용

드를 가리킨다.
if(tmpNode->parent==NULL){//인수로 받은 노드의 부모 노드가 존재하지 않는다면
tree_height++;//부모노드가 될 노드를 하나 새로 생성한다.
node_count++;
init_node(0,&node[node_count-1]);//새로 만든 노드 초기화한다.
node[node_count-1].childNode[0]=tmpNode;//새로만든 노드의 맨 왼쪽 첫번째 자식은 인수로 받은 꽉찬 노드가 된다.
BplusTree=&node[node_count-1];//새로만든 노드가 새로운 root노드가 된다.
tmpNode->parent=&node[node_count-1];//인수로 받은 꽉찬 노드와 새로 만든 leaf의 부모는
node[node_count-2].parent=&node[node_count-1];//새로만든 부모노드가 된다.
addKey(temp[2],&node[node_count-2],&node[node_count-1]);//새로만든 부모 노드는 항상 비어있으므로
}//왼쪽의 가장 큰 record를 부모노드에 삽입한다. 이때 부모 노드의 오른 자식은 새로만든 leaf노드가 된다.
else{
target=tmpNode->parent;//만약 인수로 받은 꽉찬 노드의 부모노드가 존재할때는
node[node_count-1].parent=tmpNode->parent;//새로 만든 leaf노드의 부모 역시 꽉찬 노드와 동일하고
if(isFull(tmpNode->parent))//부모노드가 꽉찼는지 비교하여
splitKey(temp[2],&node[node_count-1],target);//꽉찼다면 분할을 해주고
else
addKey(temp[2],&node[node_count-1],target);//비었다면 그대로 삽입한다.
}
}
//인수로 받은 record(key값)와 오른자식(rChild)를 가지고 주어진 꽉찬 노드를 두개의 노드로 분할하는 함수
void splitKey(int record, struct st_node* rChild, struct st_node* tmpNode){
int i,t,tmpkey[5];
struct st_node *temp[6], *tmp;
ins_splitKey_count++;
for(i=0;i<4;i++){//5개의 key값과 6개의 포인터를 저장할 임시 변수temp를 만들어
tmpkey[i]=tmpNode->key[i];//임시변수 tmpkey에 꽉찬 인덱스 노드의 key값을 저장.
temp[i]=tmpNode->childNode[i];//그리고 temp에 꽉찬 인덱스 노드의 자식 포인터를 저장.
}
temp[i]=tmpNode->childNode[i];//포인터를 키값보다 하나더 많으므로 마지막 포인터도 역시 저장.
i=0;
while(i<4)//record와 rChild의 내용도 tmpkey와 temp에 역시 저장.
if(record>tmpkey[i])//이때 크기 순으로 정렬상태를 유지해야 되므로
i++;//삽입시의 비교 저장을 해준다.
else{
t=tmpkey[i];
tmp=temp[i+1];
tmpkey[i]=record;
temp[i+1]=rChild;
record=t;
rChild=tmp;
i++;
}
tmpkey[i]=record;
temp[i+1]=rChild;
node_count++;//새로운 index노드 생성
init_node(0,&node[node_count-1]);//노드를 초기화
node[node_count-1].num=2;//새로만든 index노드에 임시로 저장한 변수의
for(i=0;i<2;i++){//뒤쪽 2개의 key와 3개의 포인터 저장
node[node_count-1].key[i]=tmpkey[i+3];
node[node_count-1].childNode[i]=temp[i+3];
temp[i+3]->parent=&node[node_count-1];//3개의 자식들의 부모노드는 새로만든 노드를 가리키도록 조정
}
node[node_count-1].childNode[i]=temp[i+3];
temp[i+3]->parent=&node[node_count-1];
tmpNode->num=2;//기존 index노드에 임시로 저장한 변수의
for(i=0;i<2;i++){//앞쪽 2개의 key와 3개의 포인터 저장
tmpNode->key[i]=tmpkey[i];
tmpNode->childNode[i]=temp[i];
temp[i]->parent=tmpNode;//저장한 3개의 자식들의 부모노드는 기존 노드를 가리키도록 조정
}
for(i=2;i<5;i++){//기존 노드에 저장되었던 나머지 내용은 초기화한다
tmpNode->key[i]=-1;
tmpNode->childNode[i]=NULL;
}
tmpNode->childNode[2]=temp[2];
if(tmpNode->parent==NULL){//기존 꽉찬 노드의 부모 노드가 없다면
tree_height++;//부모노드를 생성한다.
node_count++;
init_node(0,&node[node_count-1]);//생성한 부모노드는 초기화하고
BplusTree=&node[node_count-1];
node[node_count-1].childNode[0]=tmpNode;
tmpNode->parent=&node[node_count-1];
node[node_count-2].parent=&node[node_count-1];
addKey(tmpkey[2],&node[node_count-2],&node[node_count-1]);
}//5개의 키값중 중간 키값을 부모노드에 삽입한다.
else{
target=tmpNode->parent;//만약 기존 꽉찬 노드의 부모 노드가 존재한다면
node[node_count-1].parent=tmpNode->parent;
if(isFull(target))//부모노드가 꽉찼는지 확인하여
splitKey(tmpkey[2],&node[node_count-1],target);
else
addKey(tmpkey[2],&node[node_count-1],target);
}}

키워드

5차,   B+,   비플러스,   B플러스,   트리,   구현