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.