BJ.54-2 B tree 데이터 삭제 동작 방식을 설명합니다 (DB 인덱스과 관련있는 자료 구조)

8년차 백엔드 개발자가 배워서 남주려고 만든 채널이에요

알기 쉽게 설명합니다

함께 성장했으면 좋겠어요 :)


#컴공맛집 #백엔드전문채널


쉬운코드

B-트리에서 데이터 삭제는 항상 리프 노드에서 발생하며, 내부 노드의 데이터를 삭제할 경우 해당 데이터의 선임자 또는 후임자와 위치를 교환하여 리프 노드로 옮긴 후 삭제합니다.

데이터 삭제 후 노드의 키 개수가 최소 키 개수보다 적어지면 트리를 재조정해야 하며, 재조정은 형제 노드의 지원을 받거나, 불가능할 경우 부모 노드의 지원을 받아 형제 노드와 합치는 방식으로 진행됩니다.

형제 노드와의 합치기는 항상 왼쪽으로 이루어지며, 이 과정에서 부모 노드에 문제가 발생하면 해당 위치에서 다시 재조정 과정을 시작하고, 루트 노드가 비게 되면 삭제됩니다.

B-트리 삭제의 개요 및 기본 규칙

B-트리는 이진 탐색 트리를 일반화한 형태로, 키를 기준으로 왼쪽 서브트리는 작은 값, 오른쪽 서브트리는 큰 값을 가지며, 이러한 특징이 모든 데이터에 동일하게 적용됩니다. 또한, B-트리는 부모 노드가 두 개 이상의 자녀 노드를 가질 수 있으며, **노드의 자녀 노드 수가 X개라면 키의 수는 X-1개를 가집니다**. 각 노드의 키는 오름차순으로 저장되며, 모든 리프 노드는 동일한 레벨에 위치해야 합니다.

B-트리 사용의 핵심 파라미터는 **각 노드가 가질 수 있는 최대 자녀 노드 수(m)**입니다. 이 `m` 값에 따라 각 노드의 최대 키 수(`m-1`), 최소 자녀 노드 수(m을 2로 나누고 올림한 값), 그리고 가장 중요한 최소 키 수(최소 자녀 노드 수에서 1을 뺀 값)가 결정됩니다. 특히 **최소 키 수 조건은 데이터 삭제 시 매우 중요한 역할**을 합니다.

데이터 삭제의 원칙: 리프 노드에서 발생 및 재조정

B-트리에서 데이터 삭제는 항상 **리프 노드에서 발생**합니다. 데이터를 삭제한 후, 해당 노드의 키 수가 최소 키 수보다 적어지면 트리는 재조정되어야 합니다. 데이터와 키라는 용어는 혼용되지만, 실제 B-트리는 데이터의 키를 기준으로 동작합니다.

3차 B-트리(m=3)를 예로 들면, 최소 키 수는 1개입니다. 6을 삭제하는 경우, 6은 리프 노드에 있으므로 바로 삭제할 수 있으며, 삭제 후 노드의 키 수가 1개로 유지되어 **최소 키 수 조건을 만족하므로 재조정 없이 삭제가 완료**됩니다.

하지만 5를 삭제하는 경우, 리프 노드에서 5를 삭제하면 해당 노드의 키 수가 0개가 되어 **최소 키 수 조건을 위반**하게 됩니다. 이처럼 조건 위반이 발생하면 트리를 재조정해야 합니다.

재조정은 크게 세 가지 과정으로 나뉩니다. 첫 번째는 **형제 노드의 지원을 받는 것**입니다. 문제가 생긴 노드를 기준으로 좌우 형제 노드 중 키의 여유가 있는 형제로부터 키를 빌려옵니다. 이 과정에서 B-트리의 정렬 순서를 유지하기 위해 부모 노드를 경유하여 키를 이동시킵니다. 일반적으로 왼쪽(동생) 형제에게 먼저 도움을 요청합니다.

만약 양쪽 형제 모두 여유가 없어 첫 번째 방법이 불가능하다면, 두 번째로 **부모 노드의 지원을 받고 형제와 합쳐집니다**. 이 경우 부모로부터 키를 받고, 인접한 형제 노드와 합쳐져 하나의 노드가 사라지게 됩니다. 합칠 때는 항상 왼쪽으로 합치는 것을 원칙으로 합니다.

만약 부모 노드의 지원을 받고 형제와 합친 후에도 부모 노드에서 최소 키 수 조건 위반이 발생한다면, **해당 부모 노드를 기준으로 다시 재조정 과정을 시작**해야 합니다. 만약 재조정 결과 부모 노드가 루트 노드이고 비어 있다면, 해당 루트 노드는 삭제되고 합쳐졌던 노드가 새로운 루트 노드가 됩니다. 단, 루트 노드는 최소 키 수 조건의 예외이므로 비어 있지 않다면 그대로 유지될 수 있습니다.

내부 노드 삭제 처리: 선임자/후임자와의 교환

B-트리에서 데이터 삭제는 항상 리프 노드에서 발생하지만, 만약 **내부(Internal) 노드에 있는 데이터를 삭제해야 하는 경우**가 생길 수 있습니다. 이 때는 삭제하려는 데이터의 **선임자(predecessor) 또는 후임자(successor)**와 위치를 바꾼 뒤 리프 노드로 옮겨 그 위치에서 삭제를 수행합니다.

**선임자는 해당 데이터보다 작은 값들 중 가장 큰 데이터**를 의미하고, **후임자는 해당 데이터보다 큰 값들 중 가장 작은 데이터**를 의미합니다. 이들과 위치를 바꿔주는 이유는 B-트리의 핵심 속성인 정렬 상태를 깨뜨리지 않고 유지하기 위함입니다. 예를 들어, 15의 선임자는 9이며, 15와 9의 위치를 바꾸면 B-트리 속성을 유지할 수 있습니다.

삭제하려는 데이터의 선임자나 후임자는 **항상 리프 노드에 위치**합니다. 선임자를 찾기 위해서는 해당 데이터의 왼쪽 서브트리에서 가장 큰 값을 찾거나, 오른쪽으로 더 이상 내려갈 수 없을 때까지 이동해야 합니다. 이러한 특성 덕분에 내부 노드 삭제 시에도 최종적으로 삭제할 데이터는 항상 리프 노드에 놓이게 되어, 앞에서 설명한 리프 노드 삭제 및 재조정 과정을 따를 수 있습니다.

예시를 통한 B-트리 삭제 과정 상세화

3차 B-트리에서 15를 삭제하는 경우, 15는 루트 노드에 있으므로 내부 노드 삭제 방식이 적용됩니다. 15의 선임자인 9와 위치를 교환한 후, 9는 15의 위치로 올라오고 15는 9의 리프 노드 위치로 이동합니다. 이후 **리프 노드에 있는 15를 삭제하고, 남은 노드들이 최소 키 조건을 만족하는지 확인**하며, 필요한 경우 재조정을 수행합니다.

75를 삭제할 때, 75는 내부 노드이므로 선임자인 70과 위치를 바꾼 후 75를 삭제합니다. 이 과정에서 해당 노드의 키 수가 최소 키 수보다 적어지면, 형제 노드(여기서는 오른쪽 형제)의 지원을 받아 재조정합니다. 지원을 받을 때는 **부모 노드의 키와 형제의 키를 교환하여 정렬 순서를 유지**합니다.

45를 삭제하는 경우, 내부 노드이므로 선임자인 42와 위치를 바꾼 후 45를 삭제합니다. 삭제 후 노드의 키 수가 부족해지면, 동생 노드는 여유가 없으므로 부모 노드의 지원을 받아 형제 노드와 합쳐집니다. 이 과정에서 부모 노드 또한 최소 키 수 조건을 위반하게 되면, **상위 노드에서부터 재귀적으로 재조정 과정을 반복**합니다. 최종적으로 루트 노드가 비게 되면 삭제됩니다.

60을 삭제할 때도 유사하게 내부 노드이므로 선임자인 55와 위치를 바꾼 후 60을 삭제합니다. 삭제 후 키 수가 부족해지면 여유 있는 동생 노드로부터 지원을 받아 재조정을 완료합니다. 이 모든 과정을 통해 **B-트리의 속성을 유지하며 효율적인 데이터 삭제**가 이루어집니다.

B-트리에서 데이터 삭제는 항상 리프 노드에서 발생한다고 하는데, 내부 노드의 데이터를 삭제해야 할 경우 그 과정이 어떻게 되는지 설명해주세요.

B-트리에서 데이터 삭제 후 노드의 키 수가 최소 키 수보다 적어졌을 때, 문제를 해결하는 3가지 재조정 과정에 대해 자세히 설명해주세요.

내부 노드의 데이터를 삭제할 때, 해당 데이터의 선임자나 후임자와 위치를 바꿔주는 이유와 그 선임자나 후임자가 항상 리프 노드에 위치하는 원리는 무엇인가요?

B-트리의 특정 노드에서 키를 삭제한 후, 형제 노드로부터 키를 빌려와 재조정할 때 부모 노드의 키와 위치를 교환하는 방식이 어떻게 작동하는지 설명해주세요.

B-트리에서 노드들이 합쳐지면서 하나의 노드가 사라지는 과정이 데이터 삽입 시 승진하는 과정과 어떻게 유사하거나 반대되는지 궁금합니다.

B-트리는 이진 탐색 트리(바이너리 서치 트리)를 일반화한 트리이다.

키를 기준으로 왼쪽 서브 트리는 키보다 작은 값, 오른쪽 서브 트리는 키보다 큰 값을 가진다.

B-트리는 이진 탐색 트리와 달리 부모 노드가 두 개 이상의 자녀 노드를 가질 수 있다.

노드가 x개의 자녀 노드를 가지면 키의 수는 x-1개이다.

각 노드의 키는 오름차순으로 저장된다.

모든 리프 노드는 같은 레벨에 있다.

가장 중요한 파라미터는 각 노드가 가질 수 있는 최대 자녀 노드 수(m)이다.

각 노드의 최대 키 수는 m-1이다.

각 노드의 최소 자녀 노드 수는 m/2를 올림한 값이다.

각 노드의 최소 키 수는 최소 자녀 노드 수 -1이다.

데이터 삭제는 항상 리프 노드에서 발생한다.

삭제 후 노드의 키 수가 최소 키 수보다 적으면 트리를 재조정한다.

최소 키 수 조건은 B-트리의 중요한 조건이다.

3차 B-트리(m=3)에서 최소 키 수는 1이다.

6 삭제: 리프 노드에서 삭제 후 최소 키 수 조건 만족.

5 삭제: 삭제 후 노드의 키 수가 0이 되어 최소 키 수 조건 위반.

1. 형제 노드로부터 키를 빌려온다.

2. 부모 노드로부터 키를 빌려오고 형제 노드와 합친다.

3. 부모 노드에서도 문제가 발생하면 재조정을 반복한다.

인터널 노드 데이터 삭제는 리프 노드 데이터와 위치를 바꾼 후 삭제한다.

삭제하려는 데이터의 선임자 또는 후임자와 위치를 바꾼다.

선임자 또는 후임자는 항상 리프 노드에 있다.

선임자 또는 후임자와 위치를 바꾸면 B-트리 속성을 유지할 수 있다.

BJ.54-2 B tree 데이터 삭제 동작 방식을 설명합니다 (DB 인덱스과 관련있는 자료 구조)

스크립트