B TREE

🌳 B-Tree란?

• 데이터를 정렬된 상태로 저장하고, 검색, 삽입, 삭제를 효율적으로 수행할 수 있는 균형 트리 구조이다. 
• 자녀 노드의 최대 개수를 늘리기 위해서 부모 노드에 key를 하나 이상 저장된다.
• 부모 노드의 key들을 오름차순으로 정렬
• 정렬된 순서에 따라 자녀 노드들의 key 값의 범위가 결정된다.

➡ 탐색 속도(log n)를 유지하면서

➡ 디스크 접근 횟수를 최소화하도록 설계된 트리

➡ B tree는 BST를 일반화한 tree

 

M : 각 노드의 최대 자녀 노드 수

M-1 : 각 노드의 최대 key 수

⌈M/2⌉ : 각 노드의 최소 자녀 노드 수(root node, leaf node 제외)

⌈M/2⌉-1 : 각 노드의 최소 key 수 (root node 제외)

 

 

🌳 B-Tree 삽입

• 추가는 항상 leaf 노드에 한다.
• 노드가 넘치면 가운데 key를 기준으로 좌우 key들은 분할하고 가운데 key는 승진한다.
• 모든 leaf 노드들은 같은 레벨에 있다.

 

🌳 B-Tree 삭제

• 삭제도 항상 leaf 노드에서 발생
• 삭제 후 최소 key 수보다 적어졌다면 재조정한다.
  • key 수가 여유있는 형제의 지원을 받는다.
    • 1. 동생(왼쪽 형제)이 여유가 있으면
      ➡ 동생의 가장 큰 key를 부모 노드의 나와 동생 사이에 둔다.
      ➡ 원래 그 자리에 있던 key는 나의 가 왼쪽에 둔다.
    • 2. 그게 아니라 형(오른쪽 형제)이 여유가 있으면
      ➡ 형의 가장 작은 key를 부모 노드의 나와 형 사이에 둔다.
      ➡ 원래 그 자리에 있던 key는 나의 가장 오른쪽에 둔다.
  • 그게 불가능하면 부모의 지원을 받고 형제와 합친다.(왼쪽)
  • 위를 실행 후 부모에 문제가 있다면 거기서 다시 재조정한다.
    • 1. 부모가 root 노드가 아니라면
      ➡ 그 위치에서부터 다시 1번부터 재조정을 시작한다.
    • 2. 부모가 root 노드고 비어있다면
      ➡ 부모 노드를 삭제한다.
      ➡ 직전에 합쳐진 노드가 root노드가 된다.
• internal 노드 데이터 삭제
  • leaf 노드에서 삭제하고 필요하면 재조정
  • internal 노드에 있는 데이터를 삭제하려면 leaf 노드에 있는 데이터와 위치를 바꾼 후 삭제한다.
    ➡ 삭제할 데이터의 선임자나 후임자와 위치를 바꿔준다.