• B트리는 하나의 노드에 많은 수의 정보 저장 가능
• 최대 M개의 자식을 가질 수 있는 B-트리를 M차 B-트리라고 함
  • 트리의 노드에는 Key가 있는데, 이 키는 M - 1 개만큼 가질 수 있음
  • internal 노드의 key가 x개라면 자녀 노드의 수는 언제나 x+1 개
• 노드에 Key들은 항상 정렬된 상태로 저장됨
• 각 노드는 최소 [M/2] - 1 개의 키를 가져야 함 (루트 노드 제외)

데이터 삽입

• 항상 leaf 노드에서 일어남
• M차 트리의 노드에 M - 1개를 넘어선 Key가 들어오면 이를 ‘노드가 넘친다’라고 표현하며, 이 때 가운데 key를 기준으로 좌우 key들을 분할하고 가운데 key는 승진하여 부모 노드의 key가 된다

  • 이 승진으로 인해 부모 노드도 넘치게 되면 연속적으로 분할이 일어남

    B트리 삽입.mp4

데이터 삭제

• 항상 leaf 노드에서 일어남
• 삭제 후 최소 key 수보다 적어졌다면 재조정을 해야함

재조정

• key 수가 여유있는 형제의 지원을 받는다

  • B트리의 속성에 맞게 부모 노드엔 지원해주는 형제의 key가 들어가고 부모 노드의 키가 지워진 키의 자리에 들어간다

  B 트리 삭제 - 형제 지원.mp4

• 형제의 지원이 불가능하다면 부모의 지원을 받고 형제와 합친다

B 트리 삭제 - 부모 지원.mp4

• 위 과정에서 부모가 문제가 있다면 거기서 다시 재조정한다

  B 트리 삭제 - 부모 재조정.mp4

  • 부모가 ROOT 노드이고 비어있다면 부모 노드를 삭제하고 합쳐진 노드가 ROOT 노드가 된다

    ROOT 노드 재조정.mp4

Internal 노드에서 key를 삭제할 때

• 삭제는 항상 leaf 노드에서 발생해야 하므로 internal 노드의 키를 leaf 노드와 바꾸고 삭제
  • predecessor나 successor와 자리를 바꾸고 삭제를 진행
    • predecessor : 나보다 작은 데이터들 중 가장 큰 데이터
    • successor : 나보다 큰 데이터들 중 가장 작은 데이터

internal 노드 삭제.mp4

시간복잡도는?