# R+ 트리

### 위키백과 ― 우리 모두의 백과사전.

R+ 트리는 다차원의 공간 데이타를 저장하는 색인 자료구조이다. R 트리의 변종이나 점 데이타만 저장할 수 있는 K-D-B 트리와 다르지 않다.

## [편집] R 트리와의 차이점

R+ 트리는 R 트리와 K-D-B 트리의 중간 형태로써, 트리 노드들의 최소 경계 사각형 (MBR, Minimum Bounding Rectangle)이 서로 겹치는 것을 허용하지 않으며, 겹치는 영역이 불가피 한 경우에는 대신 데이타를 복제하여 여러 단말 노드에 저장한다.

- 그러나 데이타가 점(point)이 아닌 영역을 갖는 공간 데이타일 경우, 이러한 복제는 노드 분리(node split) 시에 무한 루프에 빠지게 되는 경우를 만들게 되므로, 실제로 R+ 트리는 점 데이타만을 저장할 수 있는 K-D-B 트리에 더 가까운 색인 구조라고 말할 수 있다.

R+ 트리는 K-D-B 트리와 모든 점에서 같으나, 다만 내부 트리 노드가 K-d 트리가 아닌 MBR 리스트로 이루어져 있다는 점만이 다르다. 이는 K-D-B 트리의 장점인 차원 독립 (dimension- independent) 자식 노드의 수 (fan-out) 마저도 잃어버리게 만드는 원인으로써, R 트리와 K-D-B 트리의 단점만을 모아놓은 색인 구조체이다.

## [편집] 참고문헌

- T. Sellis, N. Roussopoulos, and C. Faloutsos. The R+-Tree: A dynamic index for multi-dimensional objects. In VLDB, 1987.

원본 주소 ‘http://ko.wikipedia.org../../../r/%2B/_/R%2B_%ED%8A%B8%EB%A6%AC.html’

분류: 트리 구조

##### Views

- 문서
- 토론
- 현재 버전

##### 찾기

##### 다른 언어

- English