B-Tree 삭제 과정

 

B-트리에서 키를 삭제하는 것은 삽입 연산과 유사하지만, 더 복잡하다.

삭제는 모든 노드에서 가능하지만, 리프(leaf) 노드가 아니라 내부(internal) 노드에서 삭제 연산을 수행한다면 

삭제 시 내부 노드의 자식들을 재정렬해야 한다.

 

 

이런 상황을 해결하기 위해, 모든 삭제 연산을 리프 노드에서 수행하도록 한다.

 

1. 내부 노드에 있는 삭제할 키를 리프 노드로 이동한다.
2. 이동 후 내부 노드에서 해당 키를 삭제한다.
3. 만약 이 과정에서 B-트리의 속성이 위배되면, 트리 구조를 재정비(fixup) 해야 한다.

 

 

 

 

 

 

 

Case 1: 삭제할 키가 리프 노드에 존재하는 경우

 

즉, 삭제할 노드가 (t-1)보다 많은 자식 노드를 가지고 있는 경우

이때는 노드에 최소 키 수를 유지하는 조건(B-트리 속성)이 위배되지 않는다.

따라서 그냥 키를 삭제하면 된다.

 

 

 

 

하지만 삭제할 키가 리프 노드에 존재해도, 그 노드가 정확히 (t-1)개의 자식만 가지고 있는 경우가 있다.

이 경우, 해당 키를 삭제하면 B-트리 속성(최소 키 수 유지)이 위배된다.

즉, 노드가 최소 키 개수(t-1개)를 유지하고는 있지만, 삭제 후 조건을 만족하지 못하게 된다.

 

 

 

이를 해결하기 위해, 형제 노드나 부모 노드에서 재분배 또는 병합(merge)을 수행한다.

 

 

 

 

여기에서도 경우의 수가 나뉘는데, 우선 형제 노드로부터 키를 빌리는 경우는

형제 노드가 최소 차수(t) 이상의 키를 가지고 있는지 확인한다.

만약 그렇다면, 이 조건을 만족하는 형제 노드에게서 키를 빌려온다. 왼쪽 형제 노드이든 오른쪽이든 상관없다.

 

 

 

만약 양쪽 형제 노드가 모두 최소 키만 보유하고 있다면, 부모 노드에 도움을 요청해야 한다.

이 경우에는 부모 노드가 개입하여 키를 재분배하거나 병합을 수행한다.

 

 

 

1. 삭제 전:
   • 삭제할 키는 31. 이 키가 포함된 노드가 최소 키 수를 위배하게 될 수 있다.
2. 삭제 후 재분배:
   • 31을 삭제한 후, 왼쪽 형제 노드에서 28을 빌려와서 부모 노드(30)의 위치를 채운다.
   • 부모 노드에서 30이 자식 노드로 내려오고 트리 구조가 조정된다.

 

 

 

 

 

 

이제 형제 노드들이 모두 최소 키 수만을 가지고 있는 경우를 알아보자.

 

이 경우는 부모 노드로부터 키를 빌리고, 현재 노드를 형제 노드와 병합(merge)한다.

이 과정에서 부모 노드의 키 개수가 1개 감소한다.

 

 

물론 이 과정에서 부모 노드도 키의 최소 개수 조건을 위반할 가능성이 생기기 때문에, 부모 노드의 키 개수를 확인해야 한다.

만약 부모 노드가 B-트리 속성을 위반하면, 각각의 경우를 부모 노드에 대해 재귀적으로 수행해야 한다.

 

 

 

 

30을 삭제하고, 부모 노드(28)에서 키를 가져와 형제 노드와 병합하여 부모 노드의 키 개수가 줄어들고 트리가 조정됐다.

 

 

 

여기서 궁금했던 점

부모 노드에서 키를 가져오는 것은 최소 노드 개수를 만족해야 하니 그 부분은 알겠는데, 형제 노드와 굳이 병합해야 하나 궁금했다.

그냥 {25} {28} {35} 상태로 두면 안되는걸까? 아니면 {25} - {28, 33} - {35} 같은 부모 자식 관계라도.

 

 

 

결론만 말하면

B-트리는 각 노드가 오름차순으로 정렬된 키를 가져야 하므로, 자식 노드들은 그에 맞게 정렬된 범위 안에 키를 가져야 한다.

그런데 위와 같은 구조같이 바뀌면 부모 노드와 자식 노드 사이의 정렬 규칙이 깨질 수 있다.

 

 

 

{25} {28} {35} 상태같이 부모 노드에서 키를 하나 가져왔을 때, 형제 노드와 병합하지 않고 작은 크기의 노드를 남겨두면 트리의 높이가 증가할 수 있기 때문에 병합으로 트리의 높이를 최소화한다.

 

{25} - {28, 33} - {35} 상태처럼 부모 노드가 자식 노드로 내려가지 않는다면, 트리의 높이가 일정하게 유지되지 않을 수 있기 때문에 향후 연산에서 안정성을 보장하지 못한다.

 

 

 

물론 위 경우가 불가능한 것은 아니다. 이처럼 노드를 병합하지 않고, 분리된 상태로 유지할 수 있지만

이 방법이 사용되려면 

 

• 노드들이 최소 키 개수 조건을 만족해야 하고
• 차수(t)에 따라 모든 자식 노드가 균형을 유지해야 사용 가능한 방법이다.

 

 

 

즉, {25} {28} {35}처럼 키를 나눈 상태로 유지하려면 모든 노드가 차수(t)에 따른 최소 키 개수 규칙을 만족해야 한다.

만약 해당 조건을 충족한다면, 병합 없이도 운영이 가능하다.

균형잡힌 트리에 대한 이해가 부족했던 것 같다.

 

 

 

 

 

 

Case 2: 키가 내부 노드에 있는 경우

 

내부 노드에서의 삭제는 직접적으로 수행되지 않고, Case 1로 변환한 후에 처리한다.

 

 

 

처리 방법 (Trick)

1. 삭제할 키의 전임자(predecessor) 또는 후임자(successor)를 찾는다.
2. 삭제할 키를 전임자나 후임자로 교체한다.
   교체되면, 삭제할 키가 리프 노드로 이동한다.
3. 리프 노드에서 키를 삭제하고, Case 1에서 설명한 대로 트리를 조정한다.

 

 

 

위의 예시 이미지는 33을 삭제하기 위해 33의 전임자인 32로 교체하고, 리프 노드에 있는 32를 삭제했다. (case 1)

내부 노드의 삭제를 리프 노드의 삭제로 변환하는 전략을 통해 복잡한 내부 노드 삭제 작업을 리프 노드에서 단순한 삭제로 해결할 수 있다.

 

 

 

 

 

 

B-트리 높이 감소

 

키를 삭제한 후, 부모 노드의 키 개수가 감소할 때 부모 노드가 B-트리 규칙을 위반할 수도 있다.

이 경우 재귀적으로 부모 노드의 상태를 확인해서 문제를 해결해야 한다.

 

 

 

만약 부모 노드가 루트 노드이고, 루트가 자식 노드를 더 이상 가지지 않는 경우

현재 노드(병합된 노드)를 새로운 루트로 재설정하고 B-트리의 높이를 감소시킨다.

 

 

위 그림에서는 10이 삭제된 후, 트리를 병합(merge)하여 새로운 루트를 만들었다.

이 때, 부모 노드의 키 개수가 부족해져 트리의 높이가 1 감소됐다.