B+트리 삽입 삭제 알고리즘 구현 및 분석

소개

B+ Tree에 대한 삽입 삭제 알고리즘을 구현하고

분석하는 과제입니다.

목차

Internet Explorer

본문내용

/*B+트리 삽입 알고리즘 */
/* 알고리즘에 사용되는 변수는 다음과 같다.
In-key : B+트리에 삽입될 키
Finished : 삽입이 완료되었음을 나타내는 플래그
P : 노드에 대한 포인터
leafnode : 리프노드
TOOBIG : 오버플로 노드를 위한 변수(분열시 분열된 키값들을 모두 저장할 작업용 노드)
N : 키 카운터(현재 노드에서 사용중인 키값들의 개수) */

/* In-key가 삽입될 리프노드를 찾는다. */
read root /* B+트리의 루트를 읽어 들인다. */
do{
N = number of keys in current node;
/* 해당노드 안에 키값들의 개수를 N이라는 키 카운터에 넣는다. */
/* 3차 B+트리 노드일 때 옆과 같은 구성을 가짐 |P0|key1|P1|key2|P2| */
i = 1; /* 노드안의 키값 순서를 나타내는 변수 */
do{
if( In-key <= keyi ) {
P = Pi-1;
break;
} else {
P = Pi;
i += 1;
}
}while( i =< N );
/* 인덱스 부분에 있는 노드의 키값과 비교하여 작다면 P에 Pi-1값 즉 비교한 값의 왼쪽에 있는 포인터 값을 저장하고 break가 있으므로 while문을 빠져나오고, 인덱스 부분에 있는 노드의 키값과 비교하여 크다면 P에 비교한 노드의 오른쪽에 있는 포인터 값인 Pi를 넣는다. 이후 다시 while문을 N까지 반복하면서 모든 노드의 키값보다 크다면 최후에 저장된 Pi값을 P포인터 값에 저장하고 while문을 빠져나오게 된다. 이때 Pi는 PN과 같다. */

참고자료

· 없음