[자료구조] B-트리의 개념, 삽입 및 삭제

 

B-Tree

B-Tree 는 이진 탐색 트리(BST) 를 일반화한 형태라고 볼 수 있다. 두 자료구조 간의 차이점과 관계를 살펴보자.

 

B-Tree 가 BST 를 일반화한 이유

1. BST 의 제한을 확장

- BST 는 각 노드가 최대 두 개의 자식(왼쪽, 오른쪽)을 가질 수 있지만, B-Tree 는 여러 키와 자식 노드를 허용한다.

- 이는 B-Tree 가 BST 보다 더 많은 데이터를 하나의 노드에 저장하고, 트리의 높이를 낮게 유지할 수 있음을 의미한다. 

 

2. 균형 유지

- BST 는 균형이 깨질 수 있어서 최악의 경우 트리의 깊이가 깊어지고, 시간 복잡도가 O(n) 까지 증가할 수 있다.

- 반면 B-Tree 는 설계 자체가 항상 균형을 유지하도록 되어 있다. 삽입 및 삭제 연산 시 노드를 분할(Split) 하거나

 

3. 검색 범위 확장

- BST 에서는 한 노드에 하나의 키만 존재하므로, 탐색 경로가 길어질 수 있다.

- B-Tree 는 한 노드에 여러 개의 키를 저장하므로, 노드 내부에서 이진 탐색을 활용하여 더 많은 데이터를 한 번에 검색할 수 있다.

 

4. 디스크 기반 구조로 설계 가능

- B-Tree 는 대규모 데이터를 디스크나 외부 저장소에 저장하고, 디스크 I/O 횟수를 최소화하기 위해 설계되었다.

- BST 는 일반적으로 메모리 내에서만 효과적으로 작동한다.

 

*BST 는 균형이 유지되는 경우에만 B-Tree 의 특수한 형태로 간주 될 수 있다.

- 균형이 유지된 BST 는 이진 탐색 구조를 가지며, 이 경우 m = 2 인 B-Tree 로 볼 수 있다(각 노드가 최소 1개, 최대 1개의 노드를 가지며, 2개의 자식을 가질 수 있다)

- 그러나 BST 가 균형을 잃으면 트리의 깊이가 비대칭적으로 증가하고 ,이 경우 B-Tree 의 특성을 위배한다.

 

위에서 설명했듯이, B-Tree 가 가질 수 있는 자식 노드의 개수(m 개)를 정의하는 것이 곧 B-Tree 를 사용할 때 중요한 파라미터가 된다. 한번 더 정리해보면,

 

m-차 B-Tree

m: 각 노드의 최대 자식 노드 수, 최대 m 개의 자식 노드를 가질 수 있는 B-Tree 를 m-차 B-Tree 라고 부른다.

파라미터 m 으로부터 아래의 파라미터들이 파생된다.

 

m-1: 각 노드의 최대 key 의 개수

⌈m/2⌉: 각 노드의 최소 자식 노드 수( ⌈⌉ 는 올림,  예: 3-차 B-Tree 의 경우, 최소 자식 노드 수는 2개)

           *루트 노드(출발점이 되는 노드), 리프 노드(자녀 노드가 없음)는 제외

⌈m/2⌉-1: 각 노드의 최소 key 수

           *루트 노드는 제외

 

B-Tree 의 규칙

1. 키는 항상 정렬된 상태로 존재한다.

- 각 노드 내의 키는 오름차순으로 정렬되어야 한다.

2. 내부(Internal) 노드의 키 수가 k 개라면, 자식 노드의 수는 k+1 개이다.

- 이 규칙은 트리 구조와 탐색의 기반이 되는 핵심 규칙이다.

3. 노드는 최소 한 개의 키를 가져야 한다.

- 몇 차 B-Tree 인지에 관계없이, 노드는 각 노드는 최소 ⌈m/2⌉-1 개의 키를 가져야 한다.

- 루트 노드는 예외로 최소 1개의 키만 가져도 된다.

4. Internal 노드는 최소 2개의 자식을 가져야 한다.

- 이 규칙은 내부 노드가 최소 ⌈m/2⌉ 개의 자식을 가져야 한다는 규칙의 일반화된 표현이다.

5. 루트 노드의 예외

- 루트 노드는 최소 키 수와 최소 자식 개수 규칙을 따르지 않아도 된다.

- 예: 키가 1개만 있어도 허용되며, 자식이 없어도 된다.)

6. 각 노드의 키 개수 제한

- 모든 노드는 최소  ⌈m/2⌉-1 개에서 최대 m-1 개의 키를 가질 수 있다.

- m -차 B-Tree 에서는 m-1 개의 키를 초과하면 노드가 분할(split) 된다.

- 루트 노드는 예외로, 최소 1개의 키와 최대 m-1개의 키를 가질 수 있다.

7. 각 노드의 자식 개수 제한

- 모든 노드는 최소 ⌈m/2⌉ 개에서 최대 m 개의 자식을 가질 수 있다.  

- 루트 노드는 예외로, 자식이 없어도 되며, 최대 m 개의 자식을 가질 수 있다.

8. 균형 유지

- B-Tree 는 항상 균형 상태를 유지한다.

- 트리의 모든 리프 노드는 같은 깊이에 위치한다(balanced tree).

9. 삽입 및 삭제 연산

- 키 삽입 및 삭제 후에도 트리의 균형과 B-Tree 의 규칙을 유지해야 한다.

- 삽입 시 노드가 가득 차면, 분할(split)이 발생하고, 삭제 시 노드가 최소 조건을 위반하면 병합(merge) 또는 재배치(redistribution)가 발생한다.

10. 탐색 조건

- 특정 키를 검색하려면 루트부터 리프 노드까지 내려가면서 탐색한다.

- 내부 노드에서 k(i) 와 비교하여 어느 자식 노드로 내려갈지 결정한다.

 

B-Tree 데이터 삽입

삽입의 핵심과 관련 동작이 잘 설명되어있는 유튜브 영상을 첨부한다. 

https://www.youtube.com/watch?v=bqkcoSm_rCs

- 추가는 항상 Leaf 노드에 한다

- 노드가 넘치면 가운데(median) key 를 기준으로, 좌우 key 들은 분할하고 가운데 key 는 승진한다.

 

B-Tree 데이터 삭제

삭제의 핵심과 관련 동작이 잘 설명되어있는 유튜브 영상을 첨부한다. 

https://www.youtube.com/watch?v=H_u28u0usjA

- 삭제도 항상 Leaf 노드에서 발생한다.

  만약 internal 노드에 있는 데이터를 삭제하려면, Leaf 노드에 있는 삭제할 데이터의 선임자(predecessor)나, 후임자(successor)와 위치를 바꾼 후 삭제하면 된다.

  이렇게 바꿔줘야 B-Tree 의 성질을 깨트리지 않고 삭제가 가능하다.

- 삭제 후 최소 key 수보다 적어졌다면 재조정한다. *최소 key 수는 (루트 노드를 제외하고)  ⌈m/2⌉-1 개이다.

  1) key 수가 여유있는 형제의 지원을 받는다

     1-1. 동생(왼쪽 형제)이 여유가 있으면

      - 동생의 가장 큰 key 를 부모의 나와 동생 사이에 둔다.

      - 원래 그 자리에 있던 key 는 나의 가장 왼쪽에 둔다.

     1-2. 그게 아니라 형(오른쪽 형제)이 여유가 있으면

      - 형의 가장 작은 key 를 부모의 나와 형 사이에 둔다.

      - 원래 그 자리에 있던 key 를 나의 가장 오른쪽에 둔다.

  2) 1번이 불가능하면 부모의 지원을 받고 형제 노드와 합친다.

      2-1. 동생이 있으면 동생과 나 사이의 key 를 부모로부터 받는다.

      - 그 key 와 나의 모든 key 를 차례대로 동생에게 합친다(왼쪽으로)

      - 나의 노드를 삭제한다.

      2-2. 동생이 없으면 형과 나 사이의 key 를 부모로부터 받는다.

      - 그 key 와 형의 모든 key 를 차례대로 나에게 합친다(왼쪽으로)

      - 형의 노드를 삭제한다.

  3) 2번 후 부모에 문제가 있다면 거기서 다시 재조정한다.

      3-1. 부모가 루트 노드가 아니라면

      - 그 위치에서부터 다시 1번부터 재조정을 시작

      3-2. 부모가 루트 노드고 비어있다면

      - 부모 노드를 삭제

      - 직전에 합쳐진 노드가 루트 노드가 된다.