[자료구조] 다원 탐색 트리(Multi-way Search Trees)

Why? 왜 m-way 탐색 트리를 사용하는가?

산술 연산/논리연산보다 메모리 접근 비용이 더 크다.

- 디스크 접근은 산술연산보다 10,000배 정도, 메모리 접근은 100정도 시간이 더 걸림

프로세서 속도와 메모리 접근 시간의 차이로 cache 사용

디스크에서 block 단위 데이터 전송

index를 이용해서 그 시간을 감소시킬 수 있음.

 

AVL, Red-Black Tree의 탐색 성능은 O(log_2(n))

노드가 모든 다른 블럭에 있으면 최악의 성능.

탐색 시간 대부분이 메모리 접근에 소비됨.

메모리 접근 횟수는 Tree 높이와 연관.

 

m-way 탐색 트리는 공백이거나 다음 성질을 만족

-1) 루트는 최대 m개의 서브 트리를 가진다.

• 구조: n, A0, (E1, A1)... (En, An)
• Ei는 원소를 의미
• 각 원소 Ei는 Ei.K 키를 가지고 있음
• Ai는 서브트리에 대한 포인터

-2) Ei.K < E(i+1).K (1<=i<=n)

-3) E0.K = -∞, E(n+1).K = ∞

-4) 0<=i<=n에 대해 서브트리 Ai 역시 m-원 탐색 트리

차수가 m이고 높이가 h인 트리에서의 최대 노드 수

∑m^i = (m^h -1)/(m-1)

최적의 성능은 트리의 균형에서.

특수한 형태: B-Tree, B+Tree

 

탐색

- 트리의 루트에서 시작

- Ei.K <= x <=E(i+1).K를 만족하는 i를 찾는다

- x = Ei.K면 탐색 완료

- x != Ei.K이고 x가 존재한다면 서브트리 Ai를 루트로 탐색 반복.

 

 

B-트리

데이터베이스와 파일 시스템에서 널리 사용되는 트리 자료구조의 일종

B의 뜻은 공식적인 답변은 없고, Balanced의 의미라는게 가장 가능성 있는 설.(Bayer의 B, 보잉 과학 연구소의 B 등등)

 

B-tree 정의

1) 루트 노드는 적어도 2개의 자식

2) 모든 노드는 적어도 m/2개(정확히는 이하의 정수 중 최대의 값)의 자식을 갖는다.(루트, 외부노드 제외)

3) 모든 외부 노드들은 같은 레벨

 

모든 외부 노드 레벨이 l+1인 차수 m의 B트리

- 최대 m^l -1개의 키를 가짐

- 최소 원소 수 N은

• level 1: root 1개, 자식 2개
• level 2: 2개의 노드는 최소 m/2개의 자식 노드-> 2* (m/2)
• level l: 2* (m/2)^(l-2)
• 외부 노드: 2* (m/2)^(l-1)
• N+1 ≥ 2*(m/2)^(l-1)

B 트리에서의 삽입은 2-3 트리에서와 동일

B 트리에서의 삭제는

- 리프 노드에서만 이루어짐

- 리프 노드가 아니라면 삭제할 노드의 후속 노드와 SWAP 후 삭제

- 삭제할 아이템이 리프 노드에 있으면

• 노드에 다른 아이템이 존재하면 단순 삭제
• 그렇지 않으면 sibling 노드에서 아이템을 빌리고 삭제
• 빌릴 수 없으면 부모와 병합

 

 

B+ Tree

B Tree와 차이점

1) 인덱스 노드와 데이터 노드의 분리

- 인덱스 노드: 키와 포인터를 저장 (element를 저장하지 않음)

- 데이터 노드: 키와 데이터를 저장(element)

2) 데이터 노드는 왼쪽에서 오른쪽 순서대로 서로 링크되어 있고 이중 연결 리스트 형성

 

정의

차수가 m인 B+ 트리

1) 모든 데이터 노드는 같은 레벨에 위치해있고 리프 노드이다.

2) 인덱스 노드는 차수가 m인 B 트리, 단 키만 있고 데이터를 갖지 않음.

3) 인덱스 노드의 형식: n, A0, (K1, A1)...(Kn, An)

• Ai (0≤i ≤n <m)가 서브트리에 대한 포인터 Ki(1 ≤i ≤n<m)는 키
• K0 = -∞, K(n+1) = ∞
• 서브트리 Ai의 모든 원소는 0 ≤i ≤n일 때, K(i+1)보다 작고, Ki보다 크다.

 

탐색

1. 정확히 일치하는 값에 대한 검색

2. 범위 검색

 

 

삽입

데이터 노드에 삽입(분할) --B 트리와의 차이점

- 데이터 노드가 완전히 차면 가장 큰 키들을 가지고 있는 원소의 절반을 새로운 노드로 옮김

- 분리된 새로운 노드에 대한 포인터와 가장 작은 키를 부모 인덱스 노드에 삽입

인덱스 노드 분할은 B 트리에서의 내부 노드 분할과 같음.

 

 

 

B+ Tree에서의 삭제

데이터 노드 최소 원소 수가 부족하지 않은 경우

- 변경된 데이터 노드는 디스크에 기록

- 인덱스 노드는 변경되지 않음

 

데이터 노드의 최소 원소 수가 부족한 경우

- 가까운 형제 노드에게 원소를 빌려옴

- 그에 따는 부모 노드(인덱스 노드)의 해당 키 값을 변경

- 형제 노드가 원소를 빌려줄 수 없는 경우 부모와 병합