B Tree

B Tree

이진 탐색 트리(BST)

• 모든 노드의 왼쪽 서브 트리는 해당 노드의 값보다 작은 값들만 가지고
• 모든 노드의 오른쪽 서브 트리는 해당 노드의 값보다 큰 값들만 가진다
• 자녀 노드는 최대 두 개까지 가질 수 있다.

자녀 노드를 두 개 이상 가지고 싶을 때? → B Tree

1. 부모 노드에 key를 하나 이상 저장한다. ex) 30,50
2. 부모 노드의 key들을 오름차순으로 정렬한다. ex) 40,30 → 30,40
3. 정렬된 순서에 따라 자녀 노드들의 key값의 범위가 결정된다
   ex) 부모노드(30,50) → (? < 30), (30 < ? < 50), (50 < ?)
   자녀 노드의 최대 개수를 임의로 결정해서 쓸 수 있다.

B Tree parameter

M : 각 노드의 최대 자녀 노드 수
최대 m개의 자녀를 가질 수 있는 B Tree를 M차 B Tree라 부른다.
M - 1 : 각 노드의 최대 key수
M / 2(올림 처리) : 각 노드의 최소 자녀 노드 수
[M / 2] - 1(올림 처리) : 각 노드의 최소 key 수

데이터 삽입

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

ex) 3차 B Tree 데이터 삽입

1. 1 추가 → 노드 key 1 추가
2. 15 추가 → 노드 key 15 추가 → 노드 키(1,15)
3. 2 추가 → 노드 key 2 추가 → 노드 키 (1,2,15) → 노드가 넘침 → 2 승진 후(root) 1, 15를 왼쪽, 오른쪽 자식 노드 설정
4. 5 추가 → root노드인 2 보다 큼 → 오른쪽 노드 key 5 추가 → 오른쪽 노드(5, 15) 정렬
5. 30 추가 → root노드인 2 보다 큼 → 오른쪽 노드 key 30 추가 → 오른쪽 노드가 넘침(5,15,30) → 15 부모 노드로 승진 후 5, 30 왼쪽 오른쪽 자식 노드 설정
6. 승진한 부모 노드가 넘칠 경우 정렬 후 승진 반복

B tree의 특징

모든 leaf노드들은 같은 레벨에 있다 → balanced tree 형태이다 → 검색할 시 최악의 경우에도 OlogN이다.

---

B Tree 데이터삭제

• 삭제도 항상 leaf노드에서 발생한다.
• 삭제 후 최소 key수보다 적어졌다면 재조정한다.
  1. key 수가 여유있는 형제의 지원을 받는다.
  2. 불가능하면 부모의 지원을 받고 형제와 합친다
  3. 부모에 문제가 생긴다면 거기서 다시 재조정한다.

ex) 3차 B Tree 데이터 삭제

1. a 삭제 → root노드부터 검색 → leaf노드에서 a삭제
2. b 삭제 → root노드부터 검색 → leaf노드에서 b삭제 → 해당 leaf 노드 key값이 없음
   1. 형제의 지원을 받는다 → 부모 노드의 key를 내린다 → 형제의 key를 부모 노드에 올린다
      • 왼쪽이 여유가 있으면 왼쪽의 가장 큰 key를 부모 노드로 오른쪽이 여유가 있다면 오른쪽의 가장 작은 key를 부모노드로 올린다.
   2. 형제의 지원을 못 받는다면 → 부모의 key중 작은것을 형제(왼쪽)노드의 key에 합친다 → 빈 노드를 삭제한 뒤 부모 노드를 조정한다.
   3. 부모 노드에 문제가 생겼다면 → 부모의 형제 노드에 지원을 받는다. → 부모가 root노드이고 비어 있다면 부모 노드를 삭제하고 합쳐진 노드가 root노드가 된다

internal 노드 데이터 삭제

1. leaf노드에 있는 데이터와 위치를 바꾼 후 삭제한다
2. 삭제할 데이터의 선임자나 후임자와 위치를 바꾼다
   • 선임자 : 삭제할 데이터보다 작은 데이터 중 가장 큰 데이터
   • 후임자 : 삭제할 데이터보다 큰 데이터 중 가장 작은 데이터