DB - indexing(2)

  이번 시간에는 B tree 데이터 삭제 방식에 대해서 배워보도록 하겠습니다. 

B tree

• BST를 일반화한 트리입니다. 
• 부모 노드는 자녀 노드를 두 개 이상 가질 수 있습니다.
• 노드가 자녀를 x개 가졌다면 key는 x-1개를 가집니다. 
• 노드 내의 key들은 오름차순으로 저장됩니다.
• 모든 leaf 노드들은 같은 레벨에 있습니다.

B tree parameter

• M: 각 노드의 최대 자녀 노드 수
• M - 1: 각 노드의 최대 key 수
• [M/2]: 각 노드의 최소 자녀 노드 수
• [M/2] - 1: 각 노드의 최소 key 수 *Root node제외

B tree 데이터 삭제

*데이터 == key를 의미

• 삭제도 항상 leaf 노드에서 발생
• 삭제 후 최소 key 수보다 적어졌다면 tree 재조정!

삭제도 root node에서 조회를 시작합니다. 그리고 삭제 후 최소 key 수보다 작으면 tree를 재조정해주어야 합니다. 그럼 재조정은 어떻게 해주어야할까요?

1. key 수가 여유 있는 형제의 지원을 받는다. 왼쪽은 동생, 오른쪽은 형! -> 처음에는 동생한테 먼저 도움을 요청합니다. 심적으로 덜 부담ㅎㅎ
2. 1번이 불가능하면 부모의 지원을 받고 형제와 합친다.
3. 2번 후 부모에 문제가 있다면 거기서 다시 재조정을 해야합니다.

형제로부터 지원을 받을 때 바로 넘기는 것이 아니라 B tree의 정렬을 만족하면서 key를 옮겨야 합니다! 그러기 위해서는 부모로부터 받는 것이 필요합니다. 

삭제 후 최소 키 보다 적다면

1. key 수가 여유있는 형제의 지원을 받는다. 
   1. 동생(왼쪽 형제)이 여유가 있으면 -> 동생의 가장 큰 key를 부모 노드의 나와 동생 사이에 둔다
   2. 원래 그 자리에 있던 key는 나의 가장 왼쪽에 둔다
   3. 그게 아니라 형(오른쪽 형제)이 여유가 있으면 -> 형의 가장 작은 key를 부모 노드의 나와 형 사이에 둔다
   4. 원래 그 자리에 있던 key는 나의 가장 오른쪽에 둔다.
2. 형제가 여유가 없으면 부모의 지원을 받고 형제끼리 합치는 과정을 거칩니다. 합친다 -> 왼쪽으로 옮긴다(합친다).
   1. 합치는 과정에서 노드 하나가 사라지게 된다.
   2. 부모가 지원해주면 여유가 없지만 일단은 지원하고 합친다.
3. 재조정 후 부모에 문제가 있다면 다시 재조정을 해야합니다. 
   1. 상황에 맞게 대응
   2. 만약 부모가 root node이고 아무런 데이터가 없으면(비어있으면) 삭제하고 root 노드를 직전에 합쳐진 노드로 바꿔주면 된다.

internal 노드 데이터 삭제

internal 노드에 있는 데이터를 삭제하려면 leaf 노드에 있는 데이터와 위치를 바꾼 후 삭제해주면 됩니다. 그러면 어떤 leaf노드와 바꿔주어야 할까요?! 막 바꾸면 key 정렬 조건을 위반할 수 있다.

• 삭제할 데이터의 선임자나 후임자와 위치를 바꿔준다. 즉, predecessor(나보다 작은 데이터들 중 가장 큰 데이터)나 successor(나보다 큰 데이터들 중 가장 작은 데이터)와 위치를 바꿔주면 됩니다. 이렇게 하면 B tree의 정렬 조건을 만족할 수 있습니다!
• 그리고 선임자나 후임자가 항상 leaf 노드에 있는지 확인해야 합니다. 

결국, internal node에 있는 데이터를 삭제하려면 leaf 노드에 있는 데이터와 위치를 바꾼 후 삭제하면 됩니다. 선임자나 후임자는 항상 leaf 노드에 있으르로 삭제할 데이터의 선임자나 후임자와 위치를 바꿔줍니다. 

5차 B tree 데이터 삭제 example -> 최소 key 수: 2개 (root node 제외)

• 삭제는 항상 leaf 노드에서! *internal 노드의 경우 선임자와 위치 바꾼 후 삭제!
• 삭제 후 최소 key 수보다 적어졌다면 재조정 -> 1. 형제 지원 2. 부모 지원 후 합치기 3. 부모 문제시 또 재조정

init

먼저, 90을 삭제해 보겠습니다. 삭제도 root 노드에서 조회를 시작합니다. 

이어서 75를 삭제해 보겠습니다. 75는 internal 노드 이기 때문에 leaf 노드로 옮겨 주어야 합니다. 결국 leaf node 삭제! 아래 그림에서 80이 옆으로 바로 옮기는 것이 아니라 정렬 조건을 만족하기 위해 부모를 내리고 80을 부모 노드로 옮겨줍니다.

이제, 45를 삭제해 보겠습니다. 45는 root node이기 때문에 바로 삭제할 것이 아니라 internal node라 선임자를 찾아서 바꿔서 leaf 노드 형태로 삭제를 합니다. 부모로부터 지원을 받은 후에 형제를 합쳐야 합니다. 합치는 것은 항상 왼쪽으로 진행합니다. 

이제 비어 있는 노드를 삭제해주면 됩니다. 그런데 부모 노드에 문제가 있음을 확인할 수 있습니다. 그래서 재조정이 필요합니다. 합치는 것은 항상 왼쪽으로! 그리고 pointer 들도 옮겨주어야 합니다.

그러면 최종적으로 비어있는 루트 노드역시 모두 삭제해 주면 됩니다. 그러면 root노드가 바뀌게 됩니다. 

마지막으로 60을 삭제해 보겠습니다. 60은 root 노드 이면서 internal node이기 때문에 선임자와 위치를 바꿔 leaf 노드로 옮겨가서 삭제 하면 됩니다. 

그러면 각각의 노드들이 정렬된 상태임을 확인할 수 있고 B tree 조건을 만족하는것을 알 수 있습니다.

 

지금까지 B tree의 Deletion에 대해서 배워보았습니다!