B-Tree와 데이터 삭제 동작 방식

개요

리프 노드의 수는 BST와 B-Tree를 구별하는 주요 차이점 중 하나로 BST는 두 개로 고정이되는 반면, B-Tree는 차 수에 따라 말단 노드의 개 수가 결정된다.

 

만약 데이터를 삽입하는 과정을 갖는다면 항상 리프 노드에서 발생하게 되는데 이는 삭제하는 과정 역시 동일하지만 삽입을 통해 자녀 노드의 수가 기준 값 보다 커졌을 경우 승진을 통한 재조정이 발생하지만 삭제의 경우 key의 개수가 최소 key의 수보다 적어졌다면 재조정이 이루어지게된다.

B-Tree에 저장되는 데이터가 있다면 이 데이터 각각은 Key를 통해 동작하지만 여기선 데이터가 Key의 역할까지 수행하기 때문에 두 단어를 혼용해서 사용한다. 

데이터 삭제 과정

다음과 같은 3차 B-Tree가 존재한다고 했을때, 데이터 삭제 과정에서의 재조정 과정을 살펴보자

먼저 6이라는 데이터를 삭제한다면 아래와 같은 흐름으로 동작하게 된다.

 

 

• 데이터 15와 6을 비교하고 6은 15보다 작기 때문에 왼쪽으로 이동한다.
• 3과 6을 비교한다. 6은 3보다 크기 때문에 오른쪽으로 이동하지만, 7이라는 같은 레벨의 노드가 존재하기 때문에 7과 6을 비교하게되고, 7은 6보다 크기 때문에 3과 7사이 범위를 갖는 리프 노드로 이동한다.
• 5와 대소 비교를 하고 타겟 데이터를 발견하면 삭제가 이루어진다.

위와 동일한 과정을 통해 5라는 데이터를 삭제하게 되면 기존 트리는 아래와 같이 비어있는 리프 노드를 갖게 되고, 이는 3차 B-Tree가 가지는 각 노드의 최소 key수 1개 보다 작기 때문에 재조정이 필요하다.

 

데이터 재조정

B-Tree에서 데이터 삭제를 통해 재조정이 필요하다면 총 세 가지 방법을 통해 재조정 할 수 있다.

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

가장 간단한 방법으로 예시의 3차 B-Tree의 경우 5와 6을 삭제했지만, 같은 레벨의 노드의 데이터가 충분한 상태이기 때문에 형제 노드의 도움을 받아 트리 구조를 유지할 수 있다.

 

주의할 점은 B-Tree의 규칙을 준수하면서 데이터의 이동이 이루어져야 한다는 것인데 그 규칙은 다음과 같다.

 

 

삭제된 노드를 기준으로 왼쪽을 동생 노드, 오른쪽을 형 노드라고 한다면, 우선 동생 노드의 데이터가 충분한지 확인하고 충분하다면 동생 노드의 지원을, 아니라면 형 노드를 확인한다.

 

이후 곧 바로 동생 노드의 데이터 2를 옮겨오면 될 것 같지만, B-Tree의 데이터 흐름상 곧 바로 데이터를 옮기게 된다면 오름 차순 정렬이라는 규칙을 준수하지 못 하기 때문에 부모 노드의 도움을 받아 재조정이 이루어진다.

 

 

총 세 개의 노드에 변화가 발생했고, 각 노드가 최소 key 수를 만족한다면 데이터 5에 대한 삭제가 완료 된다.

 

만약 동생 노드에게 도움을 받을 수 없는 상황이라면 형 노드의 도움을 받을 수 있는지 확인하고, 위와 동일한 과정을 거쳐 트리 구조를 유지한다.

 

2. 부모의 지원을 받고 형제와 합친다.

만약 1번의 방법을 사용할 수 없다면 부모 노드의 데이터를 받고 동일 레벨의 노드와 합치는 과정을 통해 재조정 할 수 있다.

 

 

데이터 7을 삭제하게 된다면, 해당 노드는 비어있는 상태로 이루지고, 이에따라 최소 key 수를 만족할 수 없는데 형제 노드 역시 데이터가 각각 한 개로 도움을 줄 수 없는 상태이다.

 

이 경우 우선 부모 노드의 왼쪽 데이터를 받고, 동생 노드와 합치는 것으로 재조정이 이루어진다.
(정렬 조건에 따라 부모 노드의 오른쪽 데이터는 왼쪽으로 이동한다.)

 

 

이 방법은 데이터를 삽입하는 과정에서 발생할 수 있는 승진(분할)의 역순이라고 볼 수 있다.

3. 부모의 지원을 받은 후 문제가 발생한다면 그 곳에서 다시 재조정한다.

데이터 1과 2가 삭제된 상황을 예시로 본다면, 1과 2는 동일한 리프 노드에 존재고 있어 해당 노드는 비어있는 상태가 되고 형제 노드의 도움을 받을 수 없기 때문에 2번 방법을 통해 부모 노드의 지원을 받는다면 아래와 같은 구조를 가지게 된다.

 

 

부모 노드의 지원을 통해 리프 노드의 문제는 해결이 되었지만 이 구조는 밸런스 트리인 B-Tree와 맞지 않고, 최소 key 개수 또한 만족하지 못한다.

 

이 경우 부모 노드에 해당하게 되는데, 부모 노드의 지원을 통해 리프 노드의 문제가 해결되었지만 역으로 부모 노드에 문제가 발생하게되는 경우이다.

 

해결 방안은 1번과 2번을 다시 반복하는것으로 먼저 문제가 있는 노드를 기준으로 형제의 도움을 받을 수 있는지 확인하고, 도움을 받을 수 없다면 부모 노드의 도움을 받아 형제 노드와 합치는 과정을 통해 트리의 크기를 축소해 나간다.

 

 

부모 노드의 데이터를 이동하고, 형제와 합치는 과정을 통해 기존에 발생했던 문제는 해결할 수 있었다.

이 때 어떤 경우는 노드를 삭제하고 어떤 경우에는 재조정이 이루어지는지 햇갈릴 수 있는데 이는 두 가지 경우로 나누어 생각할 수 있다.

1. 부모가 root 노드가 아닌 경우
   • 그 위치에서 부터 다시 재조정을 시작한다.
2. 부모가 root 노드고 비어있는 경우
   • 부모 노드를 삭제한다.
   • 직전에 합쳐진 노드가 root 노드가 된다.

Internal 노드의 데이터 삭제

지금까지 살펴본 예시는 모두 리프 노드에서 발생한 데이터의 삭제와 재조정 과정이었는데 만약 리프 노드가 아닌 Internal 노드에서 데이터 삭제가 발생하게 된다면 어떨까?

 

Internal 노드에 있는 데이터를 삭제하기 위해선 먼저 리프 노드에 있는 데이터와 위치를 바꾸는 과정이 필요한데 리프 노드의 데이터 중 어떤 데이터와 위치를 바꿔야할지 고민할 필요가 있다.

 

결론부터 말하자면 삭제할 데이터의 선임자나 후임자와 위치를 바꿔주는것으로 기준을 세울 수 있다.

[!NOTE]
선임자(predecessor) : 나보다 작은 데이터들 중 가장 큰 데이터
후임자(successor) : 나보다 큰 데이터들 중 가장 작은 데이터

 

 

• 선임자와 후임자를 기준으로 데이터 위치를 바꾸는 것은 B-Tree의 오름차순 속성을 유지할 수 있다.

이를 통해 어떤 데이터와 위치를 변경할지에 대한 기준은 명확해졌기 때문에 다음으로 고려할 것은 위치를 변경할 선임자나 후임자가 항상 리프 노드에 있는지 확인하는 것이다.

 

사실 선임자와 후임자의 존재 여부는 B-Tree의 특성을 이해하고 있다면 간단하게 알 수 있다.

 

먼저 B-Tree는 밸런싱 트리로 항상 균형을 유지하는 트리이다.
이는 곧 트리가 좌, 우 어느 한쪽으로 치우쳐지지 않는다는 뜻으로 선임자와 후임자의 역할을 하는 무언가가 존재한다는 것을 뜻 한다.

 

다음으로 B-Tree는 항상 오름차순으로 정렬되어있다.

균형을 유지하는 트리 형태로 데이터가 오름차순 정렬되어있다는 것은 이 구조가 서브 트리의 구조를 가진다는 것을 말한다.

다시 말 해 각 노드를 기준으로 왼쪽은 부모 노드의 데이터 key 보다 작은 값들이 위치한다는 것을 뜻하고 오른쪽은 해당 key보다 큰 값들이 위치하게 된다.

 

이 특성을 통해 리프 노드가 나올때 까지 트리를 타고 내려가게 되면 결국 선임자 혹은 후임자를 발견할 수 있는것이다.

참고 사항

B-Tree에 데이터를 삽입하고 삭제하는 방식은 다른 방식도 존재한다.

 

출처 : 쉬운 코드