[자료구조] B-Tree란?

 

B-Tree(Balanced-Tree)란?

• 이진트리(Bineary Tree)를 확장해 하나의 노드가 가질 수 있는 자식 노드의 수가 최대 2보다 큰 M개를 가질 수 있는 트리를 의미합니다.
• 트리내에서 삽입과 삭제가 일어나더라도 최대한 균형있는 트리 형태를 유지하여 이진 탐색의 장점을 살린 트리이다.
  
  
• 한 노드에는 2개 이상의 데이터(key)가 들어갈 수 있으며, 항상 정렬된 상태로 저장된다.

 

 

• 노드 내에 데이터는 ceil(M/2)-1개부터 최대 M-1개까지 포함될 수 있다.
  3차 B Tree는 노드 내에 1~2개의 데이터를 가질 수 있다.

 

 

 

• 내부 노드는 ceil(M/2) ~ M개의 자식을 가질 수 있다. 최대 M개의 자식을 가질 수 있는 B Tree를 M차 B Tree라고 한다.

 

 

 

• 특정 노드의 데이터(key)가 K개라면, 자식 노드의 개수는 K+1개여야 한다.
  아래 그림을 보면 특정 노드의 데이터가 2개이면 자식노드는 3개이고, 특정 노드의 데이터가 1개면 자식 노드는 2개이다.

 

 

• 특정 노드의 왼쪽 서브 트리는 특정 노드의 key보다 작은 값들로, 오른쪽 서브트리는 큰 값으로 구성된다.
  10의 왼쪽 서브 트리는 10보다 작은 값이 위치한다. (10, 21)사이의 서브 트리는 10보다는 크지만 21보다는 작은 값들이 위치한다.

 

 

• 모든 리프 노드들이 같은 레벨에 존재한다.

 

 

 

이진 트리(Bineary Tree)란?

 

트리 중에서도 각 노드가 최대 2개의 자식노드를 가지는 트리를 뜻합니다.

 

 

 

 

 

 

B-Tree의 탐색

1. root node부터 탐색을 시작하여 하향식으로 탐색한다. 

2. K를 찾으면 탐색 종료한다.

3. K와 데이터 값을 비교하면서 leaf node까지 반복한다.

 

 

예시) 16 데이터를 찾는 과정

 

 

1. 16은 10과 21 사이여서 10과 21 사이의 자식 포인터를 타고 이동한다.

 

2. 14와 17 사의의 자식 포인터를 타고 이동한다.

 

3. 리프 노드에서 해당 값을 탐색해서 16을 찾아낸다.

 

 

 

 

 

 

B-Tree의 삽입

1. 리프 노드에서 상향식으로 탐색한다.

 

2. 트리가 비어있다면 루드 노드를 할당하고 K를 삽입한다.

 

3. 트리가 비어있지 않다면, 데이터를 넣을 적절한 리프 노드를 탐색한다.

 

4. 리프 노드가 해당 노드의 데이터 개수가 허용 범위 안에 있을 경우일 경우 리프 노드에 데이터를 넣고 종료한다.

 

5. 해당 노드의 데이터 개수가 허용 범위를 벗어날 경우 분리한다.

 

 

 

 

예시) 노드를 분리하는 경우 (9를 삽입하는 경우)

 

 

 

3차 노드일 경우 한 노드에 최대 2개의 데이터를 담을 수 있다. 그런데 위 그림에서는 3개의 데이터를 담고 있어서 분리를 진행한다.

 

 

 

다시 부적절한 상태가 되었으므로, 분리를 진행한다.

 

 

중앙값 16을 부모 노드에 삽입한다. 14는 왼쪽 자식, 18은 오른쪽 자식으로 설정한다. 다시 또 부적절한 상태가 되었으므로 분리를 진행한다.

 

 

 

16을 부모노드에 삽입할 수 없으니, 새로운 노드를 생성한다. 이제 모든 노드가 적절한 상태에 있으므로 삽입을 종료한다.

 

 

 

 

 

 

B-Tree의 삭제

리프 노드를 삭제하는 경우 위에서 살펴본 M차 트리 조건을 만족할 때까지 트리를 재구조화시켜야 한다.

• 내부 노드는 M/2 ~ M개의 자식을 가질 수 있다.
• 각 노드는 floor(M/2)-1 ~ M-1 개의 데이터(key)를 가질 수 있다.
• 노드의 key가 K개라면 자식 노드의 개수는 K+1 개여야 한다.

 

 

 

 

Case1. 리프 노드에서 삭제

 

1) 최소 유지 개수 조건을 만족하는 경우

16을 제거하더라도 최소 유지 개수를 만족하므로 바로 제거하면 된다.

 

 

2) 최소 유지 개수를 만족하지 못하지만, 바로 옆 형제 노드들에게 값을 빌려올 수 있는 경우

 

 

19의 값을 제거할 때, 자식 노드의 개수가 3개여야 하는데 2개가 되므로 조건을 위반하게 된다. 하지만 왼쪽 형제 노드에게서 값을 빌려 올 수 있다.

 

먼저, 19를 삭제 후 17을 19가 있던 자리로 옮긴다. 

 

 

그 다음 16을 17이 있던 부모 노드로 옮겨준다. 그러면 최소 유지 개수를 만족해서 삭제가 완료 되었다.

 

 

 

3) 최소 유지 개수를 만족하지 못하고 형제 노드들에게 값을 빌려올 수 있지만, 부모 노드를 분할할 수 있을 때

 

 

 

22를 삭제 후, 자식 노드의 수가 2개가 되어 최소 유지 개수를 만족하지 못한다. 하지만, 부모 노드인 23, 28을 분리할 수 있으므로 분리하여 23을 26의 형제 노드에 합치면 된다.

 

 

 

4) 리프 노드에서 값을 삭제할 때, 최소 유지 개수를 만족하지 못하고, 형제 노드들에게 값을 빌려올 수 없고, 부모 노드도 분할할 수 없을 때
Case2의 2번과 동일하므로 참고하자.

 

 

 

 

Case2. 리프 노드가 아닌 내부 노드에서 삭제

 

1) 내부 노드에서 값을 삭제할 때, 현재 노드 혹은 자식 노드의 최소 유지 개수의 최소보다 큰 경우

 

 

 

21을 삭제하면, 자식의 노드의 개수가 2개여야하는데 3개로 너무 많다. 현재 노드의 왼쪽 자식들 중 리프 노드의 최대값인 19와 바꾸거나 오른쪽 자식들 중 리프 노드의 최소값인 22와 바꾸면 된다. 변경 후 삭제를 진행한다. 

 

 

2) 내부 노드에서 값을 삭제할 때, 현재 노드와 자식 노드 모두  key의 개수가 최소인 경우

이 경우는 트리의 재구조화가 필요한다.

 

 

위와 같은 경우 4를 제거하면 현재 노드 및 자식 노드들의 최소 유지 개수를 만족할 수 없다. 

 

 

 

 

먼저, 자식 노드들을 다 합쳐준다. 그리고 부모였던 10을 형제 노드에 합쳐준다. 그 다음 10을 1, 5의 자식으로 연결해 준다.

 

 

 

 

 

 

참고

[자료구조] B-트리(B-Tree)란? B트리 그림으로 쉽게 이해하기, B트리 탐색, 삽입, 삭제 과정

 

B-Tree Visualization