B-트리,B+-트리 삽입 알고리즘 비교 및 알고리즘 설명

소개글

B트리와 B+트리의 삽입 알고리즘을 설명하였다.
라인 바이 라인으로 설명.

목차

■ B-Tree Insert Algorism
■ B+-Tree Insert Algorism

본문내용

■ B-Tree Insert Algorism
In-Kye : B-트리에 삽입될 키
Finished : 삽입이 완료되었음을 나타내는 플래그
Found : B-트리에서 레코드가 발견되었음을 나타내는 플래그
P : 노드에 대한 포인터
Bignode : 오버플로 노드를 위한 변수
N : 키 카운터
SPLIT : 분할되어 생성된 새로운 노드가 있는지 없는지를 나타내는 플래그

/* 노드의 주소를 스택에 저장하면서 In-Key가 삽입될 위치를 탐색한다. */
Search_Tree()
{
Found = false; //플래그를 flase로 지정
read root; //루트 노드를 읽음
do
{
N = number of keys in current node;
//노드에 저장 할 수 있는 키의 수를 N에 저장.(키 카운터)
if(In-key == key in current node) Found = true;
//현재 위치하고 있는 노드의 키 값과 삽입하려는 키가 같으면 Found를 true로 저장
else if(In-Key < key1) P = P0;
// 삽입할 키 값이 현재 위치하고 있는 노드의 첫 번째 키 값보다 작을 경우에는 P가 즉 노드 포인터가 첫 번째 키 값 왼쪽에 있는 포인터가 된다.
else if(In-Key > keyN) P = PN;
//삽입할 키 값이 현재 위치하고 있는 노드의 마지막 키 값보다 클 경우에는 P가 즉 노드 포인터가 마지막 키 값 오른쪽에 있는 포인터가 된다.
else P = Pi-1;
//현재 위치하고 있는 노드의 중간이면 그 키 위치에서 한 자리를 뺀 앞의 포인터가 P가 된다.
if(P != null) //P가 널이 아니면
{
push on to stack address of current node;
//현재 위치의 노드 주소를 스택에 저장
read node pointed to by P;
//P가 가리키는 주소의 노드를 읽음

참고 자료

파일구조론. 이석호 저