B Tree

특징 및 장단점

• 정렬 상태로 데이터 보존
• 모든 leaf node의 depth가 동일하다. 
• O(log n)의 시간으로 검색, 순차접근, 삽입, 삭제 가능. 특히 balanced tree이기 때문에 최악의 경우에도 검색이 log n으로 보장된다는 장점이 있다. 
• 노드가 가득차 있지 않기 때문에 일정 부분 공간의 낭비가 있음

정의

• 각 노드의 키값은 하위 트리들을 나누는 기준값이 됨
• 차수가 m인 B tree (m way B tree)는 다음의 속성들을 만족한다. 

• 모든 노드는 최대 m개의 자식들을 가진다. 
• Leaf node가 아닌 모든 노드 (root node 제외)는 최소한 m/2개의 자식을 가진다. 
• Root node는 최소한 2개의 자식을 가진다. 
• k개의 자식을 가지고 있는 leaf node가 아닌 노드는 k-1개의 키를 가진다. (키가 기준값이니까..)
• 모든 leaf node들의 level (depth)는 동일하다.

삽입 동작

• 모든 삽입은 리프노드에서 시작한다.
• 새원소를 삽입하기 위해서는 해당 원소가 삽입되어야 하는 리프노드를 찾은 다음, 아래의 단계를 따라서 진행한다.

• 노드에 빈자리가 있다면 원소 순서에 맞게 새로운 원소 삽입
• 노드가 꽉 차있다면, 노드를 2개로 분할함
• 이때 leaf node의 값들과 새로운 원소 중에서 중간값을 선택함
• 선택된 중간값보다 작은 값들은 새로 만들어진 왼쪽 노드에 넣고 큰 값들은 새로 만들어진 오른쪽 노드에 넣음
• 중간값(구분값)을 부모노드에 입력함. 이때 부모노드에 자리가 없으면 부모노드를 분할해야 한다. Root node의 경우 (부모가 없으므로) 새로운 root node를 생성한다. (즉, 이때 트리의 단계가 늘어나게 된다)

 (3-way B tree: 자식은 최대 3개, key는 2개)

삭제

• 리프노드에서 삭제

• 삭제하려는 값을 검색해서 리프노드에 있는 값이면 그냥 노드에서 해당 값을 삭제하면 된다.
• 재배열이 필요하면 재배열한다. (빈 node 발생 시 삽입 때와는 반대되는 shrink 과정을 진행)

• 내부노드에서 삭제

• 내부노드의 값들은 하위트리의 구분값으로 사용되기 때문에 대체할 수 있는 값을 찾아야 한다.
• 왼쪽 하위트리의 가장 큰 원소 또는 오른쪽 서브트리의 가장 작은 원소가 새로운 구분자 역할을 할 수 있다.
• 새로운 구분자를 선택했다면 해당 구분자가 속한 node에서 값을 제거하는데 이 과정이 recursive하게 내려간다. 최종적으로 leaf node에서 값을 삭제하게 된다.
• 역시 재배열이 필요하면 재배열한다.

• 삭제 후 재배열 (rebalancing)

• 부족한 노드의 오른쪽 형제노드가 존재하고 원소가 최소 원소개수보다 많다면 왼쪽으로 회전한다.

• 부모노드의 구분자를 부족한 노드의 끝으로 복사한다. (구분자가 한단계 아래로 내려감, 부족한 노드가 이제 최소 원소개수를 가지게 된다)
• 부모노드의 구분자를 오른쪽 형제노드의 첫번째 원소로 변경함

• 안되면, 부족한 노드의 왼쪽 형제노드가 존재하고 원소가 최소 원소개수보다 많다면 오른쪽으로 회전한다.

• 부모노드의 구분자를 부족한 노드의 첫번째로 복사한다. (구분자가 한단계 아래로 내려감, 부족한 노드가 이제 최소 원소개수를 가지게 된다)
• 부모노드의 구분자를 왼쪽 형제노드의 마지막 원소로 변경함
• 안되면, 좌우 형제노드들이 최소 개수의 원소들만 가지고 있다면 좌우 형제노드들을 합친다.
• 구분자를 왼쪽노드의 마지막에 복사한다.
• 오른쪽 노드의 모든 원소들을 왼쪽 노드로 옮긴다. (왼쪽노드가 최대 개수의 원소를 가지게 됨)
• 오른쪽 노드를 삭제한다.
• 부모노드에서 구분자를 삭제한다.
• 이때 부모노드의 원소가 부족하게 되면 recursive하게 올라가면서 재배열한다.
• 부모노드가 결국 루트면서 원소가 없게되면 기존 루트를 없애고 합쳐진 노드를 새로운 루트로 만든다.

(5-way B tree: 자식은 최대 5개, 키는 최대 4개, 최소 2개)
4 삭제 - 4의 오른쪽 트리에서 가장 작은 값과 교환

4 삭제

6에서 underflow 발생

이웃한 형제노드에서 원소를 가져온다.

9 삭제

10에서 underflow 발생, 형제노드의 원소개수 역시 최소개수인 2개

병합. 그런데 병합을 했더니 3에서 underflow

병합

(참고) B+ 트리

• B 트리와 다른 점은 트리의 최하위 레벨인 leaf node에만 데이터가 정렬되어 들어 있다.
• 즉 나머지 내부 노드들은 키값만 가지고 있다.

• 위에서 보는 바와 같이 키값마저 leaf node에 중복되어 들어있다.
• 1->2->3->4...->10순으로 각 leaf node가 linked list를 구성하고 있기 때문에 데이터의 순차적 처리에 용의하다.
• 파일시스템 같은 블록기반 스토리지에서 자장데이터의 효율적인 검색에 유용하다.