[자료구조] 멀티웨이 탐색 트리(1)

m원 탐색 트리

m원 탐색 트리의 정의

• 트리의 노드가 m개 이하의 가지를 가질 수 있는 탐색 트리

→ 같은 수의 노드를 갖는 이진 트리보다 낮은 높이의 m원 트리

• 이진 탐색 트리의 확장된 형태임
• 탐색 트리의 제한을 따르면서, 2개 이상 ~ m 개 이하의 자식 노드를 가질 수 있음

출처) 방송통신대학교 강의

1. 노드 구조는 다음과 같다. 여기서 P0 ~ Pn 은 서브 트리에 대한 포인터 이고 K0 ~ Kn-1 은 키값이다. 또한 n ≤ m - 1 이 성립한다.
2. i = 0, …, n - 2 인 i 에 대해 Ki < Ki+1 을 만족한다.
3. i = 0, …, n - 1 인 i 에 대해 Pi 가 가리키는 서브 트리의 모든 키 값은 Ki 의 키 값 보다 작다.
4. Pn 이 가리키는 서브 트리의 모든 키 값은 Kn-1 의 키 값 보다 크다.
5. i = 0, … , n 인 i 에 대해 Pi 가 가리키는 서브 트리는 m원 탐색 트리 이다.

m원 탐색 트리 - 3원 탐색 트리

• 단말 노드는 키 값으로만 표기하고 내부 노드 중 자식이 없는 포인터들은 표시하지 않음

m원 탐색 트리의 탐색 연산

• 일반적으로 노드의 가지 개수가 많을수록 (⇒ 서브 트리가 많을수록), 최대 탐색 시간이 짧아짐 ( ⇒ 트리의 깊이가 얕으므로 더 빨리 찾을 수 있음)

B트리

• m원 탐색 트리는 서브 트리의 균형에 대해서는 특별히 제한하지 않음
• 각 노드가 자식을 많이 갖게 하여 트리의 높이를 줄이고 전체적으로 균형을 유지한다면 탐색 성능을 더욱 향상 할 수 있음
• m원 탐색 트리를 개선한 B트리는 인덱스 구조를 구현하는데 가장 일반적으로 사용 됨.
• 차수 m인 B트리의 탐색 경로 길이는 같은 개수의 키를 가지는 이상적인 m원 탐색 트리보다 길 수 있지만, 이상적인 m원 탐색 트리의 유지 비용에 비해 키 값을 삽입하거나 삭제할 때 B트리를 유지하는 것이 더 효율적임 (쉬)

B트리의 조건

• 루트와 잎 노드를 제외한 트리의 각 노드는 [m/2] 개의 서브 트리를 갖는다
• 트리의 루트는 최소한 2개의 서브 트리를 갖는다
• 트리의 모든 잎 노드는 같은 레벨에 있다.

B트리에 키를 삽입하는 알고리즘

• 삽입 할 위치를 찾기 위해 노드의 키 값을 왼쪽에서 오른쪽으로 탐색 ( B트리에서 모든 노드는 잎 노드에서 삽입이 시작됨)
• 노드에 빈자리가 있으면 삽입 후 종료한다.
• 노드가 꽉 찼으면 노드를 2개로 분리하고 키와 포인터를 새 노드에 반씩 할당 한다.

→ 잎 노드 키 값과 삽입 노드 키 값 중에서 중간 값을 선택한다.

→ 선택된 중간 값 보다 작은 키 값을 갖는 것은 왼쪽 노드에 넣고 큰 것은 오른쪽 노드에 넣는다.

→ 중간 값을 가지는 노드의 키 값과 포인터를 부모 노드에 삽입한다. 만일 부모 노드가 루트 노드면 두 노드를 가리키도록 (자식 노드가 되도록) 수정한다.

B트리에서 키를 삭제하는 알고리즘 - 잎노드에서 삭제

• 삭제할 키 값을 포함한 노드를 찾는다.
• 잎 노드에서 삭제하는 경우

→ 노드에서 키 값을 삭제한다.

→ 필요하면 재배열 한다.

B트리에서 키를 삭제하는 알고리즘 - 내부 노드에서 삭제

• 내부 노드의 키 값은 하위 노드에 대한 기준값 (중간 값)이기 때문에 삭제 시, 대체 할 수 있는 적절한 값을 찾아야 한다. 보통 왼쪽 서브트리의 가장 큰 키값 또는 오른쪽 서브트리의 가장 작은 키 값으로 대체 할 수 있다. 이들은 모두 잎 노드에 위치한다.

→ 새로운 기준값(삭제된 자리에 올 키 값) 을 선택하여 해당 (잎) 노드에서 삭제하고 그 값을 현재 키 값을 삭제한 자리로 옮긴다. 즉, 대체한 것이다.

→ 기준 값으로 대체하기 위해 키를 삭제한 잎 노드가 정해진 개수의 키 값을 갖지 않으면 트리를 재배열 한다.

B트리에서 키를 삭제하는 알고리즘 - 재배열(1)

• 키 값이 부족한 노드의 오른쪽 형제가 존재하고 키가 정해진 최소 개수보다 많다면 왼쪽으로 회전한다.

→ 부모 노드의 기준 (키) 값을 개수가 부족한 노드의 끝으로 이동한다. 즉, 기준값을 한 단계 더 아래로 내려 개수를 채운다.

→ 부모 노드의 기준값을 오른쪽 형제의 첫 번째 키로 수정해 균형을 맞춘다.

• 키 값이 부족한 노드의 왼쪽 형제가 존재하고 키가 정해진 최소 개수 보다 많다면 오른쪽으로 회전한다

→ 부모 노드의 기준(키) 값을 개수가 부족한 노드의 끝으로 이동한다. 즉, 기준 값을 한 단계 아래로 내려 개수를 채운다.

→ 부모 노드의 기준 값을 왼쪽 형제의 마지막 키로 수정해 균형을 맞춘다.

• 좌우 형제가 최소 개수의 키를 가지고 있다면, 좌우 형제를 합친다.

→ 부모 노드의 기준 (키) 값을 왼쪽 노드의 마지막에 복사한다.

→ 오른쪽 노드의 모든 키 값을 왼쪽 노드로 옮긴다 (왼쪽 노드가 최대 개수의 키를 갖는다)

→ 키를 갖지 않는 오른쪽 노드는 삭제한다.

→ 부모 노드가 루트면서 키를 더 이상 갖지 않으면 합쳐진 노드가 새로운 루트가 된다. 그렇지 않고 부모 노드의 키 개수가 정해진 최소 개수보다 작으면 부모 노드를 재 배열 한다.

B* 트리

B* 트리의 정의

• 노드의 약 2/3 이상이 채워지는 B트리
• 노드가 꽉차면 분리하지 않고, 키와 포인터를 재배치하여 다른 형제 노드로 옮김

→ B트리와 동일한 수의 노드를 갖는다면 높이가 낮고, 삽입/삭제 시 발생하는 노드 분리를 줄이려고 고안됨.

• 차수가 m인 B* 트리는 다음 조건을 만족하는 트리이다.

→ 공집합 이거나 높이가 1이상인 m원 탐색 트리

→ 루트 노드는 2개 이상 2[(2m - 2) / 3] + 1 개 이하의 자식 노드를 갖는다.

→ 내부 노드는 최소한 [(2m - 1) / 3] 개의 자식노드를 갖는다.

→ 모든 잎 노드는 동일한 레벨에 놓인다.

→ 포인터가 k개 이면서 잎 노드가 아닌 노드는 k-1 개의 키를 갖는다. (루트 노드 포함)

B* 트리의 노드 삽입(1)

• 4 삽입(i) : 형제 노드로 키 값을 이동 (형제 노드에 공간 여유가 있을 경우)
• 4 삽입(ii) : 두 개의 노드를 세 개로 분리 (형제 노드에 공간 여유가 없을 경우 : 부모 노드 공간 이용)

B+ 트리

B+ 트리의 정의

• 탐색 트리로 구성하면 매우 빠르게 탐색 할 수 있지만, 전체 데이터를 차례로 처리하기는 불편함
• 매번 왼쪽인지 오른쪽인지 비교해가면서 다음 노드를 찾아가며 처리해야함
• B+ 트리는 인덱스된 순차 파일을 구성하는데 사용됨
• B 트리와 같이 각 노드의 키가 적어도 1/2이 채워져야 하는 점은 같음.
• 잎 노드를 순차적으로 연결하는 포인터 집합이 있다는 점에서 다르다.
• 잎 노드의 마지막 포인터를 다음 키 값을 갖는 노드를 가리킴
• 순차 처리를 할 때는 이 포인터를 이용해서 (키 값을 비교하지 않고) 차례로 다음 데이터에 접근해서 처리
• 모든 키 값이 잎 노드에 있고 그 키 값에 대응하는 실제 데이터 (파일내용) 에 대한 주소를 잎 노드만이 가지고 있음
• 직접 탐색은 잎 노드에 도달해야 종료

B+트리의 노드 삽입

• 잎 노드가 2개의 노드로 분리될 때는 키 값 순서에 따라 배치하고 중간 키 값은 부모 노드에 올려놓음
• 새 노드는 순서에 맞게 잎 노드에 삽입

B+ 트리의 노드 삭제

• 키 값을 잎 노드에서 삭제 할 때, 트리의 내부 노드에서 도 삭제 할 필요x , 그 키 값이 직접 탐색을 위해 쓰이기 때문.

B+ 트리의 특징

• 모든 키 값이 잎에 있고, 그 키 값에 대응하는 실제 데이터에 대한 주소를 잎 노드만이 가지고 있음.
• 탐색은 잎 노드에 도달해야 종료
• 같은 노드의 B트리보다 레벨이 작아서 같은 차수의 B트리와 탐색 성능이 거의 같음.