R* 트리
R* 트리는 다차원의 공간 데이터를 저장하는 R 트리의 최적화된 자료 구조이다. R* 트리는 R 트리에 비해 빠른 검색 속도를 제공하지만, 업데이트 속도는 매우 느리다. 비록 R 트리와 이름은 다르지만, 내부 자료 구조체는 모두 동일하며 다만 노드 분리 알고리즘 (node split)과 오버플로(overflow)를 해결하는 방법만이 다르다.
R 트리와의 차이점
[편집]최소 경계 사각형(MBR, Minimum Bounding Rectangle)의 넓이와 다른 MBR과의 겹칩(overlap) 영역의 최소화는 서로 상충하는 경우가 있다. R 트리는 MBR의 넓이만을 최소화하고자 시도한 반면 R* 트리는 겹침 영역 또한 줄이고자 시도한다. 즉, R* 트리는 꽉찬 노드가 분리되어야 하는 경우에 그 노드의 자식 노드들 중 일부를 루트 노드에 다시 삽입하는 강요된 재삽입 (forced reinsertion)을 시도하여 노드의 겹침을 최소화하고자 한다.
참고 문헌
[편집]- Norbert Beckmann, Hans-Peter Kriegel, Ralf Schneider, Bernhard Seeger: The R*-Tree: An Efficient and Robust Access Method for Points and Rectangles. SIGMOD Conference 1990: 322-331 Archived 2018년 4월 17일 - 웨이백 머신