B-Tree

B-Tree

#0. 시작하기

- B-Tree는 외부 다진검색 트리 + 균형 트리이다.

- 검색 트리가 내부 메모리가 아닌 외부(디스크 등)에 있는 상태로 사용되면 '외부 검색 트리'

- 분기(자식수)가 2를 넘으면 '다진 검색 트리'

#1. 개요

º Balanced Tree란?

 - 이진 검색 트리의 문제점은 좌우 균형이 맞지 않으면 비효율적. 트리의 성능은 곧 트리의 depth인데, 좌 또는 우로 치우친 경우 O(logN) → O(n^2)까지 성능이 느려질 수 있다.

 - Balanced Tree는 삽입, 삭제 시 필요하면 스스로 균형을 유지한다.

 - ex) AVL Tree, 2-3(-4) Tree, Red-Black Tree, B-Tree 등

 - 항상 (최악의 경우에도) O(logN) 성능을 보장

º B-Tree란?

 - 하나의 노드에 여러 자료가 배치되는 트리 구조

 - 한 노드에 최대 m개의 자료가 배치되면 → 'M차 B-Tree'

   (단, 모든 노드에 항상 m개의 자료가 배치되어야 하는 것은 아님)

 - m이 짝수냐 홀수냐에 따라 알고리즘이 다르다.

 - 2-3 Tree는 2차 B-Tree와 같고, 2-3-4 Tree는 3차 B-Tree와 같다.

#2. 규칙

1. 어떤 노드의 자료 수가 N개라면, 그 노드의 자식의 수는 N+1이어야 한다. 

2. 각 노드의 자료는 정렬된 상태여야 한다.

3. 노드의 자료 Dk의 왼쪽 서브트리는 Dk보다 작은 값들이고, Dk의 오른쪽 서브트리는 Dk보다 큰 값들이어야 한다.

(설명)

- A B 노드는 C보다 작은 값이다.

- D E 노드는 C보다 크고 F보다 작은 값이다.

- G H 노드는 F보다 큰 값이다.

4. Root 노드는 자식이 있다면, 적어도 2개 이상의 자식을 가져야 한다.

5. Root 노드를 제외한 모든 노드는 적어도 m/2개의 자료를 가져야 한다.

  (5차 B-Tree라면 적어도 2개 이상)

6. 외부 노드(leaf)로 가는 경로의 길이는 모두 같다.

  (= 외부 노드는 모두 같은 레벨에 있다.

7. 자료는 중복될 수 없다.

#3. B-Tree 삽입 알고리즘

- 자료는 항상 Leaf 노드에 추가된다.

- Leaf 노드 선택은 삽입될 키의 하향 탐색에 의하여 결정된다.

- 추가될 Leaf 노드에 여유가 있다면, 그냥 삽입

- 여유가 없다면 노드를 분할한다.

- 분할을 위해서는 키 하나를 부모로 올려야 한다.

- 부모에 여유가 없다면? : 삽입을 위한 하향 탐색을 하면서 꽉 찬 노드는 미리미리 분할을 해줘야 한다.

BTree_Insert(value) {

while (currentNode is not leaf) {

if (currentNode is full) split(currentNode);

currentNode = proceedToChildNode;

}

if (currentNode is full) split(currentNode);

currentNode -> addNodeValue(value);

}

1) Root 노드의 분할

2) 일반 노드의 분할

#4. B-Tree 삭제 알고리즘

- 삭제하려는 자료가 있는 노드는 삭제 후에도 m/2 이상의 자료수를 유지해야 한다.

Case #1. 외부 노드 삭제

1) 빌리기 : 형제가 m/2보다 많은 자료를 가지고 있는 경우

2) 결합하기 : 형제에서 빌릴 수 없는 경우

Case #2. 내부 노드 삭제

- 삭제하려는 자료가 존재하는 노드가 내부 노드인 경우, 대체키를 찾아 대체해야 한다. (왼쪽 서브트리의 가장 큰 값 or 오른쪽 서브트리의 가장 작은 값)

- 삭제를 위한 하향 탐색을 하면서 자료수가 m/2 이하인 노드는 빌리기/결합하기

#5. B-Tree 성능

- M차 B-Tree의 높이는 log_m/2 N 이하이다.

- 검색 시 각 노드당 최대 M번의 순차 검색

- 삽입 / 삭제 / 검색 성능 : O(logN)

º B-Tree는 외부 검색에 적합함

  - 하나의 노드 크기를 Disk I/O 단위의 크기로

  - 순차 검색과 트리 검색의 이점을 취함