B-트리 #1. 소개 및 검색/삽입

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 );