비트리_B-Tree

B-Tree

• B트리는 이진트리에서 발전되어 모든 리프노드들이 같은 레벨을 가질 수 있도록 자동으로 밸런스를 맞추는 트리다. 정렬된 순서를 보장하고, 멀티 레벨 인덱싱을 통한 빠른 검색이 가능하다.
• B트리는 이진트리와 다르게 하나의 노드에 많은 수의 정보를 가지고 있을 수 있다. 최대 M개의 지식을 가질 수 있는 B트리를 M차 B트리라고하며 다음과 같은 특징을 가진다.
  • 노드는 최대 M개부터 최소 M/2개 까지의 자식을 가질 수 있다.
  • 노드에는 최대 M-1개 부터 최소 [M/2]-1개의 키가 포함 될 수 있다.
  • 노드의 키가 x라면 자식의 수는 x+1개 이다.
  • 최소차수는 자식수의 하한값을 의미, 최소차수가 t라면 M=2t-1를 만족한다.

Key 검색과정

• 루트노드에서 시작하여 하향식으로 검색을 수행한다(검색하고자 하는 key가 k)
  1. 루트노드에서 시작하여 key들을 순회하면서 검사
     1. 만일 k와 key가 같다면 검색 종료
     2. 검색하는 값과 key들의 대소 관계를 비교. 어떠한 key들 사이에 k가 들어간다면 해당 key들 사이의 자식노드로 내려간다.
  2. 해당 과정을 리프노드에 도달할 때까지 반복, 리프노드에도 k와 같은 key가 없다면 검색을 실패한다.

삽입

1. 추가는 항상 Leaf노드에서 한다.
2. 노드가 넘치면 가운데 기준으로 분할, 가운데 키를 승진시킨다.

삭제

1. 삭제도 항상 Leaf에서 한다.
2. 삭제 후 최소 key보다 작은가?
   1. 형제 노드의 지원을 받는다.
   2. 1이 안된다면 부모의 지원을 받고 형제와 합한다.
   3. 문제가 있다면 다시 1번부터 반복한다.
3. 문제가 있다면 다시 1번부터 한다.

• 인터널에서 삭제시

1. Leaf노드에서 삭제하고 필요시 재조정한다.
2. Leaf 노드 중 적절한 위치(가장 가까운) 키 값과 swap후 제거한다.
3. 삭제 과정을 반복한다.