B-트리는 인덱스를 조직하는 트리 구조로 가장 많이 사용되는 것으로써
Bayer와 McCreight에 의해 제안되었다.
이것은 m-원 균형 탐색 트리로서 효율적인 균형 알고리즘을 제공한다.
이어지는 내용에서 이해하기 쉽게 설명하기 위해 노력하겠지만
일단 위키피디아의 B-트리 링크를 제공하겠다. 위키피디아 B-트리 보기
특성 : m-원 탐색트리이다.
각 노드가 적어도 반 이상이 키 값으로 채워져 있어야 한다.
트리가 공백이 아닌 이상 처음부터 분기해야 한다.
트리가 균형을 유지해야 한다.
▣ 검색과 삽입
◇ 검색 : B-트리의 검색은 m-원 탐색 트리의 직접 검색과 똑같은 과정을 거치게 된다.
serchBT(key) // m-원 탐색 트리의 검색 알고리즘
// key : 키의 값
// x : 노드
// root : 루트 노드
// n : 노드에서의 키의 개수
x = root;
do{
i=1;
n=x.n;
while(i<=n && key>x.Ki)
i += 1;
if( i<=x.n && key = x.Ki)
then return A; // 레코드의 주소를 반환
} while( (x=x.Pi-1) != NULL);
return NULL; // key와 일치하는 값이 트리에 없는 경우
end searchBT()
◇ 삽입 : 새로운 키 값은 항상 리프 노드에 삽입된다.
따라서 새로운 키 값을 삽입해야 되는 리프 노드에 키 값을 삽입할 수 있는
여유 공간이 있느냐 없느냐에 따라 두 가지 경우가 발생한다.
▷ 해당 노드에 키 값이 가득 차 있지 않아 빈 공간이 있는 경우
- 새로운 키 값을 단순히 순서에 맞게 삽입하기만 하면 된다.
▷ 해당 노드가 키 값으로 만원이 되어 새로운 키 값을 삽입할 공간이 없는 경우
- 노드에서 오버플로(overflow)가 발생하였으므로
이 노드를 두 개의 노드로 분할(split)한다.
그리하여 키 값의 반은 한 쪽 노드에 들어가고, 나머지 반은 다른 노드에 들어가게
된다. 이 때 중간 키 값은 노드의 부모 노드(parent node)로 올라가서 삽입되는데,
분할된 노드들을 가리키는 포인터도 함께 첨가된다.
/* 알고리즘에서 사용되는 변수는 다음과 같다.
In-key : B-트리에 삽입될 키
Finished : 삽입이 완료되었음을 나타내는 플래그
Found : B-트리에서 레코드가 발견되었음을 나타내는 플래그
P : 노드에 대한 포인터
Bignode : 오버플로 노드를 위한 변수
N : 키 카운터
*/
/* 노드의 주소를 스택에 저장하면서 In-key가 삽입될 위치를 탐색한다 */
Found = FALSE;
read root;
do{
N = number of keys in current node;
if( In-key == key in current node)
found = TRUE;
else if( In-key < key1)
P = P0;
else if( In-key > keyN)
P = PN;
else
P = Pi-1; // for some i where keyi-1 < In-key < keyi
if( P!=NULL){
push onto stack address of current node;
read node pointed to by P;
}
}while( !Found && P is not NULL );
if(Found)
report In-key already in tree;
else{ // In-key를 B-트리에 삽입한다.
P = NULL;
Finished = FALSE;
do{
if( current node is not full ){
put In-key in current node;
// 노드 안에서 키 순서를 유지하도록 키를 정렬한다.
Finished = FALSE;
}else{
copy current node to Bignode;
insert In-key and P into Bignode;
In-key = center key of Bignode;
current node = 1st half of Bignode;
get space for new node, assign address to P;
new node = 2nd half of Bignode;
if( stack not empty ){
pop top of stack;
read node pointed to;
}else{
get space for new node;
new node = pointer to old rot, In-key and P;
Finished = TRUE;
}
}
}while( !Finished );