[File System] ::B Tree

인덱스를 조직하는 방법으로 가장 많이 사용되는 Bayer와 McCreight에 의해 제안 된 B-Tree는 균형된 m-원 탐색 트리로서 효율적인 균형 알고리즘을 제공

1) 인덱스

정의 : key,vale쌍의 주소를 체계적으로 모아놓은 것

목적 : 레코드 접근을 용이하게 하는 것

종류

- 밀집(dense) 인덱스 : 파일의 모든 레코드에 대한 키,주소쌍을 가지고 있음

- 희소(sparse) 인덱스 : 파일의 모든 레코드에 대한 키,주소쌍을 가지고 있지 않음

2) m-원 탐색 트리 : 이원탐색트리의 일반화 된 형태로 한 노드가 최고 m-1개의 키와 m개의 서브트리를 갖는다.

1) 이원탐색트리

트리 중에 가장 중요한 형태의 트리가 이진(binary) 트리로, n개의 노드를 가진 이원탐색 트리는 이진트리로서 각 노드 Ni는 레코드 키 Ki와 그 레코드가 저장되어 있는 주소를 지시하고 있다.

- 부모노드는 왼쪽 서브트리보다 항상 크고 오른쪽 서브트리보다 항상 작다.

- 탐색할때 찾아야하는 키가 K라면 K를 부모노드와 비교해서 부모노드보다 크면 오른쪽 노드로 작으면 왼쪽노드로 이동하는 식으로 탐색하면 된다.

삽입도 마찬가지.

- 삭제는 자식노드를 삭제시키면 다른 자식노드를 옆으로 이동시키면 되지만, 부모노드를 삭제하면.... ?

- 이 책에서는 과제로 남기고 하나의 예시로는 삭제하지말고 '삭제표시'를 해두도록 하는 방법을 제안함

- 노드를 만들때

1) 접근이 많은 노드는 루트에 최대한 가까이

2) 노드수를 일정하게 유지해서 균형트리가 되도록 ( 요게 단점 )

- 트리의 수를 얕게 할 수 있어 탐색시간을 줄일 수 있지만, 삽입 ,삭제가 복잡함

각 노드의 구조는 아래와 같으며 N은 포인터의 개수

B트리는 예전에 디비에서 한번 봤다. [2017/10/15 - [4학년2학기/그외] - 데이터베이스 인덱스를 알아보자]

차수가 M인 b-tree는 M-원 탐색 트리이다.

1) 루트와 리프(자식이없는 끝노드)를 제외한 모든 노드는 최소 [2/M], 최대 M개의 서브트리를 갖는다.

2) 루트는 리프가 아닌 적어도 2개의 서브 트리를 갖느다.

3) 모든 리프는 같은 레벨에 있다.

4) 리프가 아닌 노드의 키 값의 수는 그 노드의 서브트리 수보다 하나 적으며, 각 리프 노드는 최소 (M/2)-1개 최대 M-1개의 키 값을 갖는다.

5) 한 노드 안에 있는 키 값들은 오름차순을 유지

삽입

비어있는 노드에 값을 넣는것은 큰 문제가 안된다. 그러나 차있는 노드에 값을 넣으려 한다면..?

예를들어보자. 59를 넣으려면 저자리에 넣어야하는데 보면 58이 이미 자리를 차지하고 있다. 이런경우에는 어떻게 해야 할까?

1) 원래 있던 key와 새로운 key의 중간 값을 부모 노드로 올려보낸다.

2) 남은 key를 또 반으로 나누어 위로 올려보낸 key의 왼쪽, 오른쪽 서브트리가 될 수 있도록 한다

한번 더 넣어보자. 아래와 같이 54를 넣어보고 싶다. 그런데 이번에는 부모노드가 꽉 차있다. 어떻게 해야할까? 똑같이 하면 된다.

1) 기존 value 50과 57 새로운 값 54의 중간 값인 54를 부모노드로 보내준다.

2) 그런다음 원래 있던 50과 57을 두개의 노드로 쪼개 준다.

3) 58도 부모노드로 보낸다.

b트리의 삽입 슈도 코드는 아래와 같다.

1) 오버 플로된 노드를 임시 저장하기 위해 TOOBIG을 이용

2) 부모의 주소를 기억하기 위해 stack 이용

In-key : 삽입될 키

Finished : 삽입 완료를 알려주는 플래그 변수

Found : 레코드를 발견되었음을 알리는 플래그 변수

P : 노드에 대한 포인터

TOOBIG : 오버플로 노드를 위한 변수

N : 키 카운터

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 = Po;
    else if ( In-key > keyN) P = PN;
    else P = Pi-1;
    if ( P != null){ //부모의 주소를 stack에 저장
        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{
    P=nil; //null이랑 같은말
    Finished = false;
        do{ if(current node is not full) { //비어있으면 오름차순 생각해서 넣어줌
                put In-key in current node;
                Finishied =true;
            }
            else{
                copy current node to TOOBIG;
                insert In-key and P into TOOBIG;
                In-key = center key of TOOBIG; // 가운데 값을 부모노드로 ㄱㄱ
                current node = 1st half of TOOBIG; //반으로 쪼갠 노드중 1번째
                get space for new node, assign address to P;
                new node = 2nd half of TOOBIG; //반으로 쪼갠 노드중 2번째
                if(stack not empty){
                    pop top of stack 
                    read node pointed to;
                }
                else{ //트리의 level이 하나 더 증가 (부모노드가 없어서)
                    get space for new node;
                    new node = pointer to old root, In-key and P;
                    Finished = true ;
                }
            }
}while(!Finished);

삭제

삭제할 키가 리프노드에 있는게 아니라면 삭제할 키와 후행 키값이랑 자리를 바꿔치기해서 삭제한다.

삭제를 했더니 노드에 키 값이 노드가 유지해야하는 최소값인 [(M/2)]-1개 보다 적으면 언더 플로가 발생하기때문에 아래의 방법으로 키값을 유지하게 해야한다.

- 재분배 : 형제 노드중에서 최소 보다 많은 키값을 가진 노드에게 키 값을 받아 오는 것

- 합병 : 재분배가 안될 때, 형제노드에 있는 키 값과 이 두 노드의 부모노드에 있는 키값을 합병

예를 들어 아래의 노드에서 62를 삭제하면 옆에 있던 값이 이동 된다. 이것은 간단데쓰요

         

두번째 상황에서 40을 삭제한다고 해보자.

우선, 40의 후행 값인 41과 자리를 교체한다. 그리고 첫번째 상황에서 본것처럼 삭제한 뒤 옆으로 이동시킨다.

세번째 상황은 좀 복잡하다. 아래의 그림을 보자. 여기에서 16을 삭제한다고 생각해보자. ( * 나중에 안 사실인데 22가 아니라 30이다..오타 )

먼저, 16의 후행값인 18과 값을 변경한다.그리고 16을 삭제하면 원래 있던 노드는 언더플로가 발생한다.

그래서 먼저 재분배를 해보려하지만 형제노드도 키가 1개라 받아오기가 좀 그렇다 ㅠㅠ, 그렇다면 남은것은 합병!

빈 노드와 형제노드를 합체한다음에 부모노드의 값과 합병한다. 그러면 또 위의 노드가 언더플로가 발생해버린다.그럼 또 같은 과정을 반복한다.

옆에 친구를 살펴보자 또 키가 한개인 친구이다. 합병을 또 해야한다.

그럼 최상단에 있던 19와 합병하게 되면서 마무리가 이렇게 된다. 

책에서 말하는 삭제 슈도코드는 아래와 같다;; 확실히 이 슈도코드는 이해못하겟다 .

1) TWOBNODE : 재분배를 위해 사용되는 정상 노드보다 50퍼센트 큰 노드

2) A-sibling : 인접 형제 노드

3) Out-key : 삭제될 키

/*삭제할 키를 찾는것은 앞에 삽입 알고리즘과 같음*/
 
if(Out-key is not in terminal node){
    search for successor key of Out-key at terminal level( stacking node addresses);
    copy successor over Out-key;
    terminal node successor now becomes the Out-key;
}
 
Finished = false;
 
do{ /* 삭제한다음에 이제 위치 조정 * /
    remove Out-key;
    if (current node is root or is not too small) //too small이 최소한의 key값을 말하는듯
        Finished = trued;
    else if(redistribution possible){
        /*재분배*/
        copy "best" A-sibling,intermediate parent key, //intermediate 중급의
            and current (too-small) node into TWOBNODE;
 
        copy keys and pointers from TWOBNODE to "best" A-sibling, parent, 
            and current node so A-sibling and current node are roughly equal size;
 
        Finished=true;
    }
    else{
        /*합병*/
        choose "best" A-sibling to concatenate with;
        put in the leftmost of the current node and A-sibling the contents of both nodes a
            nd the intermediate key from the parent; //형제와 부모를 합친후
 
        discard rightmost of the two nodes; //비어진 노드를 삭제
        intermediate key in parent now becomes Out-key;
        
    }
}while(!Finished);
 
if(no keys in root){ // 트리의 레벨이 감소
    new root is the node pointed to by the current root;
    discard old root;
}