B-Tree 데이터 삭제

B-Tree의 데이터 삭제를 알아보도록 하겠다.

B-Tree의 데이터 삭제에는 다음과 같은 특징이 있습니다.

1. 삭제는 항상 leaf 노드에서 발생한다.
2. 삭제 후 노드의 key수가 최소 key 수보다 적어졌다면 재조정한다.
   1. 추가로 삭제과정에서 부모노드가 조건에 걸린다면 그 노드를 기준으로 다시 재조정한다.

각 노드의 최소 키 공식은 M차 B-Tree일때 ⌈M/2⌉-1 입니다. (루트노드 제외)

다음과 같은 케이스들을 살펴보면서 알아보도록 하겠습니다.

1. 리프노드에서 삭제하고 재조정을 할 필요가 없는 경우
2. 리프노드에서 삭제하고 재조정해야하는 경우 2가지
3. internal 노드에서 삭제하는 경우

리프노드에서 삭제하고 재조정을 할 필요가 없는 경우 #

말 그대로 노드의 데이터를 삭제했는데 key의 개수가 최소 key 이상이라면 딱히 재조정할 필요가 없다.

리프노드에서 삭제하고 재조정할 필요가 있는 경우 1 #

먼저 형제에게 지원을 요청한다. key 수가 여유있는 형제의 지원을 받을 수 있는 경우 형제에게 지원을 받는다 (보통 왼쪽에 있는 동생 노드에게 먼저 도움을 요청한다.)

아래에 그림에서 31을 삭제하면 최소한의 키 수보다 작아지기 때문에 재조정을 한다.

31의 동생 노드를 보면 키가 25와 28이 있으므로 여유가 있기 때문에 동생 노드로부터 키를 지원받는데, 바로 28을 옮기는 것이 아니라 BTree의 속성(정렬)에 맞게 28을 부모로 옮기고 30을 내린다.

리프노드에서 삭제하고 재조정이 필요한 경우 2 #

형제 노드의 key가 지원할 여유가 없는 경우에는 부모의 지원을 받고 형제와 합친다.

부모로부터 지원 방법

1. 부모의 key와 나의 key를 차례대로 왼쪽 노드로 합친다.
2. 나의 노드를 삭제한다.

만약 여기서 왼쪽 노드(동생 노드)가 존재하지 않는다면 부모 key와 오른쪽 노드(형 노드)의 key를 차례대로 나에게 합치고 오른쪽 노드를 삭제한다.

위에 그림에서 30을 삭제하면 최소한의 키 수보다 작아지기 때문에 재조정을 한다.

key 수가 여유가 있는 형제의 지원을 받으려 했으나 형제들도 최소한의 key만 가지고 있으므로 부모 노드의 28을 지원받고 왼쪽 노드와 합친다.

만약 여기서 부모노드가 지원을하여 부모노드에도 재조정을 해야하는 상황이 걸린다면 거기서 다시 재조정을 진행한다.

1. 부모가 Root 노드가 아니라면 재조정을 진행한다.
2. 부모노드가 Root고 노드가 비어있다면 부모 노드를 삭제한다. (그러면 그 직전의 합쳐진 노드가 root 노드가 된다.)

Internal 노드에서 데이터를 삭제하는 경우 #

Internal 노드를 삭제한다면 leaf 노드의 있는 데이터와 위치를 바꾼 후에 삭제를 한다.

어떤 leaf 노드의 데이터를 바꾸냐면 전임자나 후임자 중 하나를 선택해 바꾼다.

• 전임자 predecessor: 나보다 작은 데이터들 중 가장 큰 데이터
• 후임자 successor: 나보다 큰 데이터들 중 가장 작은 데이터

33을 삭제할 때, 33은 리프 노드가 아니기 때문에 33의 선임자를 찾는다.

33의 선임자는 32이기 때문에 32와 위치를 바꾸고 삭제를 진행한다.