[영상후기] (2부) B tree 데이터 삭제 동작 방식을 설명합니다 (DB 인덱스과 관련있는 자료 구조)

B tree 특징

• 부모 노드는 자녀 노드를 두 개 이상 가질 수 있다
  • 이진탐색트리의 일반화의 증거
• 노드가 자녀를 x개 가졌다면 key는 x-1개를 가진다
  • 자녀 3개 -> 노드의 키의 수는 2개
• 노드 내의 key들은 오름차순으로 저장된다
• 모든 leaf 노드들은 같은 레벨에 있다.

B tree 데이터 삭제 : 항상 leaf 노드에서 발생

• 삭제 후 최소 key 수 (K/2(천장) -1)보다 적어졌다면 재조정한다. (root노드 제외)
  • M/2(천장) : 각 노드의 최소 자식 노드의 수
  • Internal Node의 key가 x개라면 자식은 x+1개 규칙
• 재조정 과정
  1) key 수가 여유있는 형제의 지원을 받는다.
  - B tree 특성 유지하기 위해 부모의 것을 받아오고 형제꺼를 부모로 올림
  2) 만일 1번이 불가능하면 부모의 지원을 받고 형제와 합친다
  3) 만일 2번 후 부모의 문제가 있다면 거기서 다시 재조정한다.
  

internal 노드의 데이터를 삭제할 경우 leaf로 옮기고 삭제해줘야 함

• B Tree의 특성을 유지하며 위치를 바꿔줘야 함
  • 삭제할 데이터의 선임자(나보다 작은 데이터들 중 가장 큰 데이터, prodecessor)나 후임자(나보다 큰 데이터들 중 가장 작은 데이터, successor)와 위치를 바꿔줌
  • 선임자 혹은 후임자는 항상 leaf node이기 때문
    • B Tree는 항상 balance 맞는 Tree
• 바꿨을 당시에는 B Tree의 특징이 안맞을 수 있지만, 어차피 삭제할 노드이기에 삭제하면 B트리의 속성을 깨지 않음