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.