[자료구조] M-Tree와 B-Tree

M-웨이 탐색 트리(M-way Search Tree)

M-웨이 탐색 트리는 각 노드가 0개에서 M개까지의 서브트리를 가질 수 있는 트리입니다. 여기서 M은 일반적으로 B-트리에서 말하는 "차수(order)"를 의미합니다.

비어 있지 않은 M-웨이 트리의 주요 특징:

1. 각 노드는 0개에서 M개의 서브트리를 가질 수 있습니다.
2. 한 노드가 K(<M)개의 서브트리를 가지면, 그 노드는 K개의 서브트리와 K-1개의 데이터 항목(키)을 가집니다.
   • 예: K = 3이면, 서브트리는 3개, 키는 2개.
3. 각 서브트리의 키 값은 다음과 같은 규칙을 따릅니다:
   • 첫 번째 서브트리의 모든 키 값은 첫 번째 키 값보다 작습니다.
   • 두 번째 서브트리는 첫 번째 키 이상이고 두 번째 키 미만인 값을 가집니다.
   • 세 번째 서브트리는 두 번째 키 이상이고 세 번째 키 미만인 값을 가집니다.
   • …
   • 마지막 M번째 서브트리는 마지막 키보다 크거나 같은 값을 가집니다.

B-트리란?

B-트리는 M-웨이 탐색 트리(M-way search tree)의 한 종류이며, 다음과 같은 추가적인 제약 조건을 갖는 트리입니다.

B-트리의 주요 특징:

1. 루트 노드(root)의 조건
   • 루트는 리프 노드(잎 노드)이거나,
   • 최소 2개 이상, 최대 M개의 서브트리를 가집니다.
2. 내부 노드(internal node)의 조건
   • 내부 노드는 최소 ⌈M/2⌉개의 서브트리를 가져야 하며, (즉, 절반 이상의 자식 노드를 반드시 가져야 함)
     
   • 최대 M개의 서브트리를 가질 수 있습니다.
3. 리프 노드(leaf node)의 균형
   • 모든 리프 노드는 같은 깊이에 존재합니다. → 즉, 트리는 완전히 균형잡힌(perfectly balanced) 구조입니다.
     
4. 리프 노드의 데이터 개수
   • 각 리프 노드는 최소 ⌈M/2⌉ - 1개의 항목(entry)을 가져야 하며,
   • 최대 M - 1개의 항목을 가질 수 있습니다.