들어가며
해당 강의를 보며 정리한 내용입니다.
B-Tree 특징
- 이진탐색트리 (BST)를 일반화한 트리이다.
- 부모 노드는 자녀 노드를 두 개 이상 가질 수 있다.
- 노드가 자녀를 x개 가졌다면, key는 x-1개를 가진다.
- 노드 내의 key들은 오름차순으로 저장된다.
- 모든 leaf 노드들은 같은 레벨에 있다
B-Tree 데이터 삭제
- 삭제도 항상 leaf 노드에서 발생
- 삭제 후 최소 key 수보다 적어졌다면 재조정한다
- key 수가 여유있는 형제의 지원을 받는다.
- 1번이 불가능하면 부모의 지원을 받고 형제와 합친다.
- 2번 후 부모에 문제가 있다면 거기서 다시 재조정한다.
B-tree에서 각 노드의 최소 key 수: (M/2 (반올림)) -1
3차 B-tree에서 각 노드의 최소 key 수: 1 (root node 제외)
3차 B-tree 삭제 예시
6, 5를 모두 삭제한 뒤, 해당 노드의 key 수는 0개이므로 최소 key 수보다 적어졌기 때문에 재조정이 필요합니다.
재조정 과정에 대해 자세히 살펴봅시다.
3차 B-tree 삭제 시 재조정 예시
1. key 수가 여유있는 형제의 지원을 받는다.
실행 순서
-
key 수가 여유있는 형제의 지원을 받는다.
1.1 동생 (왼쪽 형제)이 여유가 있으면
=> 동생의 가장 큰 key를 부모 노드의 나와 동생 사이에 둔다.
=> 원래 그 자리에 있던 key는 나의 가장 왼쪽에 둔다.1.2 동생 (왼쪽 형제)이 여유가 없고, 형 (오른쪽 형제)이 여유가 있다면,
=> 형의 가장 작은 key를 부모 노드의 나와 형 사이에 둔다.
=> 원래 그 자리에 있던 key는 나의 가장 오른쪽에 둔다.
2. 1번이 불가능하면 부모의 지원을 받고 형제와 합친다.
실행 순서
-
형제의 지원이 불가능하면 부모의 지원을 받고 형제와 합친다.
2.1 동생이 있으면 동생과 나 사이의 key를 부모로 부터 받는다.
=> 그 key와 나의 key를 차례대로 동생에게 합친다.
=> 나의 노드를 삭제한다.1.2 동생이 없으면, 형과 나 사이의 key를 부모로 부터 받는다.
=> 그 key와 형의 key를 차례대로 나에게 합친다.
=> 형의 노드를 삭제한다
3. 부모가 지원한 후 부모의 문제가 있다면 상황에 맞게 대응한다.
부모가 지원한 후 부모의 문제가 발생하면, 앞서 살펴본 순서대로 대응한다.
1번 방법으로는 현재 불가능하다. 왜냐하면 key가 여유있는 형제가 없기 때문이다.
2번 방법으로 대응한다.
해당 상황에서는 루트 노드가 아무런 key를 안가지고 있는 상황이므로 해당 문제를 해결하는 방법은 간단하다.
기존 루트 노드를 삭제하면 된다.
실행 순서
-
부모가 지원한 후 부모의 문제가 있다면 상황에 맞게 대응한다.
3.1 부모가 root 노드가 아니라면
=> 해당 위치에서부터 다시 1번부터 재조정을 시작한다.3.2 부모가 root 노드고 비어있다면
=> 부모 노드를 삭제한다
=> 직전의 합쳐진 node가 root 노드가 된다.
B-tree Internal 노드에서 데이터 삭제 방법
-
internal 노드에 있는 데이터를 삭제하려면 leaf 노드에 있는 데이터와 위치를 바꾼 후 삭제한다.
-
leaf 노드에 있는 데이터 중에 어떤 데이터와 위치를 바꿔줄 것인지가 이슈
- 삭제 할 데이터의 선임자나 후임자와 위치를 바꿔준다.
- 선임자나 후임자는 항상 leaf 노드에 있으므로 삭제 할 데이터의 선임자나 후임자와 위치를 바꿔준다.
- 선임자 (predecessor): 나보다 작은 데이터들 중 가장 큰 데이터
- 후임자 (successor): 나보다 큰 데이터들 중 가장 작은 데이터
예시 (선임자 pick)
5차 B-Tree 삭제 예시
정리
- 삭제는 항상 leaf 노드에서!!
- internal 노드의 경우 선임자와 위치 바꾼 후 삭제
- 삭제 후 최소 key 수보다 적어졌다면 재조정
- 형제 지원 -> 부모 지원 받고 형제 합침 -> 부모 도움 후 부모도 문제 시 재차 조정
