Balanced Tree (B-Tree)

B-Tree는 이진트리의 문제점을 보완하기 위해 만들어짐

삽입과 삭제시 필요하다면 스스로 균형을 유지

 

항상 O(logn)의 검색 속도를 가짐

 

B-Tree란?

• 하나의 노드에 여러자료가 배치되는 트리구조
• 한 노드에 M개의 자료가 배치되면 M차 B-Tree
  • M이 짝수냐 홀수냐에 따라 알고리즘이 달라짐 (짝수가 더 어려움)

B-Tree 규칙

1. 노드의 자료수가 N이라면, 자식의 수는 N + 1 이어야 함
2. 각 노드의 자료는 정렬된 상태여야 함
3. 노드의 자료 D의 왼쪽 서브 트리는 D보다 작아야 하고, D의 오른쪽 서브 트리는 D 보다 큰 값이어야 함
4. Root 노드는 적어도 2개 이상의 자식을 가져야 함
5. Root 노드를 제외한 모든 노드는 적어도 M/2개의 자료를 가지고 있어야 함 (5차 트리라면 한 노드당 최소 2개의 자료가 필요)
6. 외부노드로 가는 경로의 길이는 모두 같다.
   • 외부노드는 모두 같은 레벨에 있음.
7. 입력 자료는 중복될 수 없음