다원 탐색 트리

- AVL트리는 균형 이진 트리의 한 종류 이기 때문에 자료가 많아지면 트리의 높이가 높아짐

-> 다원 탐색 트리

 

<m-원 탐색 트리> (m-way Search Tree)

 

1) 각 노드는 0에서 최대 m 개의 서브 트리를 갖음

2) k개의 서브트리를 갖는 노드는 (k-1) 개의 자료를 갖음 (단, k ≤ m)

3) 각 노드 안에서 자료들은 검색 키에 의해 정렬

4) 다음 조건을 항상 만족

Key i ≤ (i번째 서브트리 내의 모든 키 값) ≤ Key (i+1)

5) 모든 서브트리는 m-원 탐색 트리

 

<B-트리> (B-tree [비 트리])

 

> m-원 탐색 트리에서 트리 균형을 유지

1) 루트 노드는 leaf 노드이거나, 2에서 m 개의 서브트리를 가짐

2) 루트 노드를 제외한 모든 내부 노드는 아래 개수만큼 서브트리를 가짐

m/2(소수이면 올림) ≤ 서브트리의 개수 ≤ m

3) leaf 노드는 아래 개수만큼 자료를 가짐

m/2(소수이면 올림) - 1 ≤ 자료의 개수 ≤ m - 1

4) 모든 leaf 노드는 같은 레벨에 있음 => 트리는 완전한 균형 상태에 있음

 

<간단한 형태의 B-트리>

 

- 2-3 트리

> 차수 m = 3

> 하나의 트리 노드에서 서브트리 개수 : 2개 혹은 3개

> 하나의 트리 노드에서 자료 개수 : 1개 혹은 2개

> 루트 노드에서는 0개의 서브 노드를 가질 수 있음

 

- 2-3-4 트리

> 차수 m = 4

> 하나의 트리 노드에서 서브트리 개수 : 2개 ~ 4개

> 하나의 트리 노드에서 자료 개수 : 1개 ~ 3개

> 루트 노드에서는 0개의 서브 노드를 가질 수 있음

 

<B-트리의 변형>

 

- B-트리는 실제 사용하기엔 제약 사항이 있음

=> 보통은 B*트리와 B+트리를 많이 사용

 

- B+ 트리 ([비 플러스 트리])

> B-트리는 순차 접근하기 위해 중위 순회를 하지만 과정이 다소 복잡

1) 모든 내부 노드는 키 값만 저장하고 데이터는 말단 노드에만 저장

=> 말단 노드에 저장된 키와 동일한 키를 저장하는 내부 노드도 있을 수 있음

2) 각 말단 노드에는 다음 형제 노드에 대한 포인터를 가지고 있어 순차적으로 접근 가능

 

- B* 트리 ([비 스타 트리])

> 현실 시스템에서 대부분 대용량의 자료를 저장하기 위해 차수 m이 5 이상인 B-트리가 주로 사용

> 이 경우 각 노드는 자료를 최대 4개 저장, 서브트리는 최대 5개 갖을 수 있음

> 반면, B-트리는 전체 노드의 약 50% 정도 비어 있을 수 있음 => 불필요한 메모리 낭비

1) 루트 노드가 아닌 노드는 최대 저장 공간의 2/3 이상의 자료가 저장

=> B-트리에서는 m/2(소수이면 올림) 조건에 의해 최소 1/2 이상의 자료가 저장되어야 했음

2) 노드에 저장되는 자료가 넘치는 경우(overflow), 일단 형제 노드들로 재분배

3) 모든 형제 노드들이 가득 찬 경우에만 분할

=> B-트리는 중간값을 가지는 자료를 부모 노드로 올려 보내고 분할